Randomized online algorithms for set cover leasing problems

DOI10.1007/978-3-319-12691-3_3MaRDI QIDQ2942379zbMATH OpenOpenAlexFDO

Authors Sebastian Abshoff, Christine Markarian, Friedhelm Meyer auf der Heide

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-12691-3_3

zbMATH Keywords

leasingmulticoveronline algorithmsrandomized algorithmsset cover

Mathematics Subject Classification ID

Extremal set theory (05D05) Online algorithms; streaming algorithms (68W27) Stochastic programming (90C15) Combinatorial optimization (90C27)

Recommendations

• Towards the price of leasing online
• Towards flexible demands in online leasing problems
• Towards Flexible Demands in Online Leasing Problems
• The online set cover problem
• The online set cover problem

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A primal-dual algorithm for online non-uniform facility location
• A threshold of ln n for approximating set cover
• Admission control to minimize rejections and online set cover with repetitions
• Algorithmic construction of sets for k -restrictions
• Algorithms – ESA 2005
• Approximating the online set multicover problems via randomized winnowing
• Approximation algorithms for combinatorial problems
• scientific article; zbMATH DE number 1256771 (Why is no real title available?)
• scientific article; zbMATH DE number 2038744 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 6469194 (Why is no real title available?)
• Infrastructure Leasing Problems
• Offline and Online Facility Leasing
• On the ratio of optimal integral and fractional covers
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• The online set cover problem

Cited in

(6)

• Towards flexible demands in online leasing problems
• Approximating the online set multicover problems via randomized winnowing
• Admission control to minimize rejections and online set cover with repetitions
• Towards Flexible Demands in Online Leasing Problems
• Towards the price of leasing online
• scientific article; zbMATH DE number 7651147 (Why is no real title available?)

This page was built for publication: Randomized online algorithms for set cover leasing problems

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