The accommodating function: A generalization of the competitive ratio

DOI10.1137/S0097539799361786MaRDI QIDQ2784450zbMATH OpenFDO

Authors Kim S. Larsen, Morten N. Nielsen, Joan Boyar

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539799361786

zbMATH Keywords

bin packingcompetitive analysisflow timeon-line algorithmsperformance measuresrestricted adversariesseat reservations

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Extending the accommodating function
• scientific article; zbMATH DE number 2089963
• The relative worst order ratio for online algorithms
• scientific article; zbMATH DE number 2011845
• Comparing online algorithms for bin packing problems

Cited in

(17)

• Online-bounded analysis
• Evaluating the quality of online optimization algorithms by discrete event simulation
• Online algorithms with advice for the dual bin packing problem
• Stochastic dominance and the bijective ratio of online algorithms
• Online multi-coloring with advice
• Approximation and online algorithms for multidimensional bin packing: a survey
• A comparison of performance measures via online search
• Online Multi-Coloring with Advice
• A simple PTAS for the dual bin packing problem and advice complexity of its online version
• ON-LINE SEAT RESERVATIONS VIA OFF-LINE SEATING ARRANGEMENTS
• Measuring the problem-relevant information in input
• Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis
• Online bounded analysis
• Tight bounds for online class-constrained packing
• Relative Worst-Order Analysis: A Survey
• A survey of online knapsack problems
• The relative worst-order ratio applied to paging

This page was built for publication: The accommodating function: A generalization of the competitive ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784450)