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

An online trading problem with an increasing number of available products

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

Abstract

In this paper, we study a multiple time series search problem in which at the first n periods, one product is produced in each period and becomes sellable. The total length of the trading horizon N (\(N>n\)), i.e., the total number of trading periods (which includes the first n periods when the products are produced), is unknown beforehand. All the n products are homogeneous. At each period, a price is observed and the player must decide immediately the number of available products to sell at this period, without the knowledge of future prices and when the trading horizon ends. The objective is to maximize the total revenue from selling the n products. We present an online algorithm ON for this problem and prove its competitive ratio. A lower bound on the competitive ratio for this online problem is also proved. Numerical results for the theoretical competitive ratio of algorithm ON and the lower bound are also reported.

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

Similar content being viewed by others

References

  • Chen GH, Kao MY, Lyuu YD, Wong HK (2001) Optimal buy-and-hold strategies for financial markets with bounded daily returns. SIAM J Comput 31(2):447–459

    Article  MathSciNet  Google Scholar 

  • Chin FYL, Fu B, Guo J et al (2015) Competitive algorithms for unbounded one-way trading. Theor Comput Sci 607:35–48

    Article  MathSciNet  Google Scholar 

  • Copil K, Worbelauer M, Meyr H, Tempelmeier H (2017) Simultaneous lotsizing and scheduling problems: a classification and review of models. OR Spectr 39:1–64

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Drexl A, Kimms A (1997) Lot sizing and scheduling—survey and extensions. Eur J Oper Res 99(2):221–235

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Hasegawa S, Itoh T (2018) Optimal online algorithms for the multi-objective time series search problem. Theor Comput Sci 718:58–66

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Manasse M, McGeoch LA, Sleator D (1988) Competitive algorithms for on-line problems. In: Proceedings of 20th annual ACM symposium on theory of computing. ACM, New York, pp 322–333

  • Mohr E, Ahmad I, Schmidt G (2014) Online algorithms for conversion problems: a survey. Surv Oper Res Manag Sci 19(2):87–104

    MathSciNet  Google Scholar 

  • Savage LJ (1951) The theory of statistical decision. J Am Stat Assoc 46(253):55–67

    Article  Google Scholar 

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

    Article  MathSciNet  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  Google Scholar 

  • Schroeder P, Kacem I (2020) Optimal solutions for online conversion problems with interrelated prices. Int J Oper Res 1–26

  • 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:559–576

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Tiedemann M, Ide J, Schöbel A (2015) Competitive analysis for multi-objective online algorithms. In: Rahman MS, Tomita E (eds) WALCOM: algorithms and computation. WALCOM 2015. Lecture notes in computer science, vol 8973. Springer, Cham, pp 210–221

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  • Zhang W, Xu Y, 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  Google Scholar 

  • Zhang W, Xu Y, Zheng F, Dong Y (2012) Online algorithms for the multiple time series search problem. Comput Oper Res 39(5):929–938

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Zhang W, Zhang E, Zheng F (2015) Online (J, K)-search problem and its competitive analysis. Theor Comput Sci 593:139–145

    Article  MathSciNet  Google Scholar 

  • Zhang W, Zhang E, Zheng F (2016) Online two stage \(k\)-search problem and its competitive analysis. Int J Found Comput Sci 27(6):653–663

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

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

Funding

This work was partially supported by the Natural Science Basic Research Program of Shaanxi Province (Program No. 2021 JM-317), the National Natural Science Foundation of China under Grant No. 11771346, and the Major Projects of National Natural Science Foundation of China under Grant No. 72192834.

Author information

Authors and Affiliations

  1. School of Economics and Management, Northwest University, Xi’an, 710127, China

    Wenming Zhang & Ye Zhang

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

    Yongxi Cheng

  3. Beijing Interstellar Glory Space Technology Co., Ltd., Beijing, 100176, China

    Shankui Zheng

Authors
  1. Wenming Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ye Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yongxi Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shankui Zheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yongxi Cheng.

Ethics declarations

Conflict of interest

The authors have no conflicts of interest to declare that are relevant to the content of this article.

Availability of data and materials

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Code availability

Not applicable.

Ethics approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, W., Zhang, Y., Cheng, Y. et al. An online trading problem with an increasing number of available products. J Comb Optim 44, 518–531 (2022). https://doi.org/10.1007/s10878-021-00841-y

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-021-00841-y

Keywords

Search

Navigation