{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:18:53Z","timestamp":1767140333554,"version":"build-2238731810"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T00:00:00Z","timestamp":1590019200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T00:00:00Z","timestamp":1590019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In online optimization, input data is revealed sequentially. Optimization problems in practice often exhibit this type of information disclosure as opposed to standard offline optimization where all information is known in advance. We analyze the performance of algorithms for online optimization with lookahead using a holistic distributional approach. To this end, we first introduce the performance measurement method of counting distribution functions. Then, we derive analytical expressions for the counting distribution functions of the objective value and the performance ratio in elementary cases of the online bin packing and the online traveling salesman problem. For bin packing, we also establish a relation between algorithm processing and the Catalan numbers. The paper shows that an exact analysis is strongly interconnected to the combinatorial structure of the problem and algorithm under consideration. Results further indicate that the value of lookahead heavily relies on the problem itself. The analysis also shows that exact distributional analysis could be used in order to discover key effects and identify related root causes in relatively simple problem settings. These insights can then be transferred to the analysis of more complex settings where the introduced performance measurement approach has to be used on an approximative basis (e.g., in a simulation-based optimization).<\/jats:p>","DOI":"10.1007\/s10288-020-00442-1","type":"journal-article","created":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T09:02:47Z","timestamp":1590051767000},"page":"199-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Exact distributional analysis of online algorithms with lookahead"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4805-9576","authenticated-orcid":false,"given":"Fabian","family":"Dunke","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Nickel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,21]]},"reference":[{"issue":"3","key":"442_CR1","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/PL00009158","volume":"18","author":"S Albers","year":"1997","unstructured":"Albers S (1997) On the influence of lookahead in competitive paging algorithms. Algorithmica 18(3):283\u2013305","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"442_CR2","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0304-3975(97)00026-1","volume":"197","author":"S Albers","year":"1998","unstructured":"Albers S (1998) A competitive analysis of the list update problem with lookahead. Theor Comput Sci 197(1\u20132):95\u2013109","journal-title":"Theor Comput Sci"},{"issue":"2\u20133","key":"442_CR3","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2008.08.003","volume":"408","author":"L Allulli","year":"2008","unstructured":"Allulli L, Ausiello G, Bonifaci V, Laura L (2008) On the power of lookahead in on-line server routing problems. Theor Comput Sci 408(2\u20133):116\u2013128","journal-title":"Theor Comput Sci"},{"key":"442_CR4","doi-asserted-by":"crossref","unstructured":"Angelopoulos S, Schweitzer P (2013) Paging and list update under bijective analysis. J ACM 60(2):Article no. 7","DOI":"10.1145\/2450142.2450143"},{"key":"442_CR5","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/3-540-60220-8_63","volume-title":"Algorithms and data structures","author":"G Ausiello","year":"1995","unstructured":"Ausiello G, Feuerstein E, Leonardi S, Stougie L, Talamo M (1995) Competitive algorithms for the on-line traveling salesman. In: Akl S, Dehne F, Sack J, Santoro N (eds) Algorithms and data structures. Springer, Berlin, pp 206\u2013217"},{"issue":"1","key":"442_CR6","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David S, Borodin A (1994) A new measure for the study of on-line algorithms. Algorithmica 11(1):73\u201391","journal-title":"Algorithmica"},{"key":"442_CR7","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge"},{"issue":"1\u20132","key":"442_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(98)00118-2","volume":"209","author":"D Breslauer","year":"1998","unstructured":"Breslauer D (1998) On competitive on-line paging with lookahead. Theor Comput Sci 209(1\u20132):365\u2013375","journal-title":"Theor Comput Sci"},{"key":"442_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BFb0029568","volume-title":"Online algorithms: the state of the art","author":"J Csirik","year":"1998","unstructured":"Csirik J, Woeginger G (1998) On-line packing and covering problems. In: Fiat A, Woeginger G (eds) Online algorithms: the state of the art. Springer, Berlin, pp 147\u2013177"},{"issue":"1\u20133","key":"442_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0012-365X(98)00371-9","volume":"204","author":"E Deutsch","year":"1999","unstructured":"Deutsch E (1999) Dyck path enumeration. Discrete Math 204(1\u20133):167\u2013202","journal-title":"Discrete Math"},{"issue":"1\u20133","key":"442_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0012-365X(01)00121-2","volume":"241","author":"E Deutsch","year":"2001","unstructured":"Deutsch E, Shapiro L (2001) A survey of the fine numbers. Discrete Math 241(1\u20133):241\u2013265","journal-title":"Discrete Math"},{"key":"442_CR12","unstructured":"Dorrigiv R (2010) Alternative measures for the analysis of online algorithms. Ph.D. Thesis, University of Waterloo"},{"issue":"38\u201340","key":"442_CR13","doi-asserted-by":"publisher","first-page":"3694","DOI":"10.1016\/j.tcs.2009.04.023","volume":"410","author":"R Dorrigiv","year":"2009","unstructured":"Dorrigiv R, L\u00f3pez-Ortiz A, Munro J (2009) On the relative dominance of paging algorithms. Theor Comput Sci 410(38\u201340):3694\u20133701","journal-title":"Theor Comput Sci"},{"key":"442_CR14","unstructured":"Dunke F (2014) Online optimization with lookahead. Ph.D. Thesis, Karlsruhe Institute of Technology"},{"key":"442_CR15","first-page":"405","volume-title":"Simulation in produktion und logistik: entscheidungsunterst\u00fctzung von der planung bis zur steuerung","author":"F Dunke","year":"2013","unstructured":"Dunke F, Nickel S (2013) Simulative algorithm analysis in online optimization with lookahead. In: Dangelmaier W, Laroque C, Klaas A (eds) Simulation in produktion und logistik: entscheidungsunterst\u00fctzung von der planung bis zur steuerung. HNI-Verlagsschriftenreihe, Paderborn, pp 405\u2013416"},{"key":"442_CR16","volume-title":"Online algorithms: the state of the art","year":"1998","unstructured":"Fiat A, Woeginger G (eds) (1998) Online algorithms: the state of the art. Springer, Berlin"},{"key":"442_CR17","unstructured":"Grove E (1995) Online bin packing with lookahead. In: Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, pp 430\u2013436"},{"key":"442_CR18","unstructured":"Hiller B (2009) Online Optimization: probabilistic analysis and algorithm engineering. Ph.D. Thesis, Technische Universit\u00e4t Berlin"},{"key":"442_CR19","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-540-74456-6_27","volume-title":"Mathematical foundations of computer science 2007","author":"C Imreh","year":"2007","unstructured":"Imreh C, N\u00e9meth T (2007) On time lookahead algorithms for the online data acknowledgement problem. In: Kucera L, Kucera A (eds) Mathematical foundations of computer science 2007. Springer, Berlin, pp 288\u2013297"},{"issue":"2","key":"442_CR20","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/trsc.1060.0147","volume":"40","author":"P Jaillet","year":"2006","unstructured":"Jaillet P, Wagner M (2006) Online routing problems: value of advanced information as improved competitive ratios. Transp Sci 40(2):200\u2013210","journal-title":"Transp Sci"},{"issue":"4","key":"442_CR21","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1103\/PhysRev.106.620","volume":"106","author":"E Jaynes","year":"1957","unstructured":"Jaynes E (1957a) Information theory and statistical mechanics. Phys Rev 106(4):620\u2013630","journal-title":"Phys Rev"},{"issue":"2","key":"442_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1103\/PhysRev.108.171","volume":"108","author":"E Jaynes","year":"1957","unstructured":"Jaynes E (1957b) Information theory and statistical mechanics II. Phys Rev 108(2):171\u2013190","journal-title":"Phys Rev"},{"key":"442_CR23","unstructured":"Johnson D (1973) Near-optimal bin packing algorithms. Ph.D. Thesis, Massachusetts Institute of Technology"},{"issue":"3","key":"442_CR24","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D Johnson","year":"1974","unstructured":"Johnson D (1974) Fast algorithms for bin packing. J Comput Syst Sci 8(3):272\u2013314","journal-title":"J Comput Syst Sci"},{"issue":"1\u20134","key":"442_CR25","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A Karlin","year":"1988","unstructured":"Karlin A, Manasse M, Rudolph L, Sleator D (1988) Competitive snoopy caching. Algorithmica 3(1\u20134):79\u2013119","journal-title":"Algorithmica"},{"key":"442_CR26","unstructured":"Kenyon C (1996) Best-fit bin-packing with random order. In: Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, pp 359\u2013364"},{"issue":"1","key":"442_CR27","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias E, Papadimitriou C (2000) Beyond competitive analysis. SIAM J Comput 30(1):300\u2013317","journal-title":"SIAM J Comput"},{"key":"442_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97890-6","volume-title":"Analysis 1","author":"K K\u00f6nigsberger","year":"2001","unstructured":"K\u00f6nigsberger K (2001) Analysis 1, 5th edn. Springer, Berlin","edition":"5"},{"issue":"4","key":"442_CR29","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1057\/jors.1975.151","volume":"26","author":"J Lenstra","year":"1975","unstructured":"Lenstra J, Rinnooy Kan A (1975) Some simple applications of the travelling salesman problem. Oper Res Q 26(4):717\u2013733","journal-title":"Oper Res Q"},{"issue":"47\u201349","key":"442_CR30","doi-asserted-by":"publisher","first-page":"5182","DOI":"10.1016\/j.tcs.2009.07.056","volume":"410","author":"W Li","year":"2009","unstructured":"Li W, Yuan J, Cao J, Bu H (2009) Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead. Theor Comput Sci 410(47\u201349):5182\u20135187","journal-title":"Theor Comput Sci"},{"issue":"4","key":"442_CR31","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10951-010-0192-y","volume":"14","author":"M Mandelbaum","year":"2011","unstructured":"Mandelbaum M, Shabtay D (2011) Scheduling unit length jobs on parallel machines with lookahead information. J Sched 14(4):335\u2013350","journal-title":"J Sched"},{"key":"442_CR32","volume-title":"Applications of discrete mathematics","author":"J Michaels","year":"1991","unstructured":"Michaels J, Rosen K (1991) Applications of discrete mathematics. McGraw-Hill, New York"},{"key":"442_CR33","volume-title":"Comparison methods for stochastic models and risks","author":"A M\u00fcller","year":"2002","unstructured":"M\u00fcller A, Stoyan D (2002) Comparison methods for stochastic models and risks. Wiley, New York"},{"issue":"5","key":"442_CR34","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1515\/integers-2012-0014","volume":"12","author":"A Regev","year":"2012","unstructured":"Regev A (2012) A proof of Catalan\u2019s convolution formula. Integers 12(5):929\u2013934","journal-title":"Integers"},{"key":"442_CR35","doi-asserted-by":"crossref","unstructured":"Sgall J (2014) Online bin packing: old algorithms and new results. In: Beckmann A, Csuhaj-Varj\u00fa E, Meer K (eds), Proceedings of the 10th conference on computability in Europe, CiE 2014 (Lecture Notes in Computer Science 8493). Springer, pp 362\u2013372","DOI":"10.1007\/978-3-319-08019-2_38"},{"issue":"1","key":"442_CR36","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0012-365X(76)90009-1","volume":"14","author":"L Shapiro","year":"1976","unstructured":"Shapiro L (1976) A Catalan triangle. Discrete Math 14(1):83\u201390","journal-title":"Discrete Math"},{"issue":"2","key":"442_CR37","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D Sleator","year":"1985","unstructured":"Sleator D, Tarjan R (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202\u2013208","journal-title":"Commun ACM"},{"key":"442_CR38","unstructured":"Souza A (2006) Average performance analysis. Ph.D. Thesis, Eidgen\u00f6ssische Technische Hochschule Z\u00fcrich"},{"key":"442_CR39","unstructured":"Tinkl M (2011) Online-optimierung der rundreise auf der Kreislinie mit informationsvorlauf. Ph.D. Thesis, Universit\u00e4t Augsburg"},{"key":"442_CR40","unstructured":"Young N (1991) Competitive paging and dual-guided on-line weighted caching and matching algorithms. Ph.D. Thesis, Princeton University"},{"issue":"1","key":"442_CR41","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.cor.2012.06.003","volume":"40","author":"F Zheng","year":"2013","unstructured":"Zheng F, Cheng Y, Liu M, Xu Y (2013) Online interval scheduling on a single machine with finite lookahead. Comput Oper Res 40(1):180\u2013191","journal-title":"Comput Oper Res"}],"updated-by":[{"DOI":"10.1007\/s10288-021-00479-w","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,6,11]],"date-time":"2021-06-11T00:00:00Z","timestamp":1623369600000}}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00442-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-020-00442-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00442-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T21:41:33Z","timestamp":1627681293000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-020-00442-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,21]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["442"],"URL":"https:\/\/doi.org\/10.1007\/s10288-020-00442-1","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,21]]},"assertion":[{"value":"2 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10288-021-00479-w","URL":"https:\/\/doi.org\/10.1007\/s10288-021-00479-w","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}