The Accommodating Function: A Generalization of the Competitive Ratio
From MaRDI portal
Publication:2784450
DOI10.1137/S0097539799361786zbMath0992.68069MaRDI QIDQ2784450
Kim S. Larsen, Morten Nyhave Nielsen, Joan. Boyar
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
performance measurescompetitive analysison-line algorithmsbin packingflow timerestricted adversariesseat reservations
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial aspects of packing and covering (05B40)
Related Items (16)
Online-bounded analysis ⋮ Online Multi-Coloring with Advice ⋮ Evaluating the quality of online optimization algorithms by discrete event simulation ⋮ Online algorithms with advice for the dual bin packing problem ⋮ ON-LINE SEAT RESERVATIONS VIA OFF-LINE SEATING ARRANGEMENTS ⋮ Measuring the problem-relevant information in input ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Tight bounds for online class-constrained packing ⋮ The relative worst-order ratio applied to paging ⋮ Relative Worst-Order Analysis: A Survey ⋮ A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version ⋮ A comparison of performance measures via online search ⋮ Online Bounded Analysis ⋮ Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Online multi-coloring with advice
This page was built for publication: The Accommodating Function: A Generalization of the Competitive Ratio