[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Online multiple one way non-preemptive time series search with interrelated prices

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

This paper studies the online multiple time series search problem with interrelated prices (MTSS-ip). This perspective narrows the distance between the problem and the reality of market prices with limited variation. In MTSS-ip, the products arrive periodically, and the decision maker has a limited storage size without knowing future prices. The prices of two adjacent periods are interrelated. This study proposes an online zero-inventory algorithm (ZIA) and proves an upper bound of \(K+1-\frac{K}{\theta _2}\) on the competitive ratio of ZIA. In addition, a lower bound on the competitive ratio of problem MTSS-ip for any deterministic online algorithm is established. For the case with a large storage size K, a lower bound of \(\frac{K}{48\log _{\theta _2} K}\) on the competitive ratio for MTSS-ip is proved.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Data availability

Data sharing is not applicable to this article as no new data were created or analyzed in this study.

References

  • Chen G-H, Kao M-Y, Lyuu Y-D, Wong H-K (2002) Optimal buy-and-hold strategies for financial markets with bounded daily returns. SIAM J Comput 31(2):447–459

    Article  MathSciNet  MATH  Google Scholar 

  • Chin FYL, Bin F, Guo J, Han S, Jueliang H, Jiang M, Lin G, Ting H-F, Zhang L, Zhang Y et al (2015) Competitive algorithms for unbounded one-way trading. Theoret Comput Sci 607:35–48

    Article  MathSciNet  MATH  Google Scholar 

  • Damaschke P, Ha PH, Tsigas P (2009) Online search with time-varying price bounds. Algorithmica 55(4):619–642

    Article  MathSciNet  MATH  Google Scholar 

  • El-Yaniv R, Fiat A, Karp RM, Turpin G (2001) Optimal search and one-way trading online algorithms. Algorithmica 30:101–139

    Article  MathSciNet  MATH  Google Scholar 

  • Fujiwara H, Iwama K, Sekiguchi Y (2011) Average-case competitive analyses for one-way trading. J Comb Optim 21(1):83–107

    Article  MathSciNet  MATH  Google Scholar 

  • Fung SPY (2019) Optimal online two-way trading with bounded number of transactions. Algorithmica 81:4238–4257

    Article  MathSciNet  MATH  Google Scholar 

  • Lorenz J, Panagiotou K, Steger A (2009) Optimal algorithms for k-search with application in option pricing. Algorithmica 55(2):311–328

    Article  MathSciNet  MATH  Google Scholar 

  • Schmidt G (2017) Competitive analysis of bi-directional non-preemptive conversion. J Comb Optim 34:1096–1113

    Article  MathSciNet  MATH  Google Scholar 

  • Schroeder P, Dochow R, Schmidt G (2018) Optimal solutions for the online time series search and one-way trading problem with interrelated prices and a profit function. Comput Ind Eng 119:465–471

    Article  MATH  Google Scholar 

  • Schroeder P, Kacem I (2022) Optimal solutions for online conversion problems with interrelated prices. Oper Res Int J 22(1):423–448

    Article  MATH  Google Scholar 

  • Schroeder P, Kacem I, Schmidt G (2019) Optimal online algorithms for the portfolio selection problem, bi-directional trading and-search with interrelated prices. RAIRO-Oper Res 53(2):559–576

    Article  MathSciNet  MATH  Google Scholar 

  • Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202–208

    Article  MathSciNet  MATH  Google Scholar 

  • Wang W, Wang L, Lan Y, Zhang J (2016) Competitive difference analysis of the one-way trading problem with limited information. Eur J Oper Res 252(3):879–887

    Article  MathSciNet  MATH  Google Scholar 

  • Yinfeng X, Zhang W, Zheng F (2011) Optimal algorithms for the online time series search problem. Theoret Comput Sci 412(3):192–197

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang W, Yinfeng X, Zheng F, Dong Y (2012) Optimal algorithms for online time series search and one-way trading with interrelated prices. J Comb Optim 23(2):159–166

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang W, Yinfeng X, Zheng F, Liu M (2011) Online algorithms for the general k-search problem. Inf Process Lett 111(14):678–682

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang W, Zhang Y, Cheng Y, Zheng S (2022) An online trading problem with an increasing number of available products. J Comb Optim 44(1):518–531

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang Y, Chin FYL, Lau FCM, Tan H, Ting H-F (2018) Constant competitive algorithms for unbounded one-way trading under monotone hazard rate. Math Found Comput 1(4):383–392

    Article  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the two anonymous referees for their helpful comments and suggestions.

Funding

No funding was received for this research.

Author information

Authors and Affiliations

  1. School of Management, Xi’an Jiaotong University, Xi’an, 710049, China

    Jinghan Zhao, Yongxi Cheng & Haodong Liu

  2. The State Key Lab for Manufacturing Systems Engineering, Xi’an, 710049, China

    Yongxi Cheng

  3. University of Bonn, Bonn, Germany

    Jan Eube

Authors
  1. Jinghan Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yongxi Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jan Eube
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Haodong Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jinghan Zhao.

Ethics declarations

Conflict of interest

The authors received no research support/consulting fees from any organization. No potential Conflict of interest relevant to this article exist.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhao, J., Cheng, Y., Eube, J. et al. Online multiple one way non-preemptive time series search with interrelated prices. J Comb Optim 49, 12 (2025). https://doi.org/10.1007/s10878-024-01247-2

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10878-024-01247-2

Keywords

Search

Navigation