Approximating Sparse Covering Integer Programs Online

DOI10.1287/moor.2014.0652zbMath1327.68338arXiv1205.0175OpenAlexW2274097845MaRDI QIDQ5247608

Anupam Gupta, Viswanath Nagarajan

Publication date: 24 April 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.0175

zbMATH Keywords

linear programmingonline algorithmscovering integer programs

Mathematics Subject Classification ID

Integer programming (90C10) Online algorithms; streaming algorithms (68W27)

Related Items (5)

Online unit clustering and unit covering in higher dimensions ⋮ Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ Bicriteria Approximation of Chance-Constrained Covering Problems ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximability of sparse integer programs
• Approximation algorithms for covering/packing integer programs
• Randomized Competitive Algorithms for Generalized Caching
• A general approach to online network optimization problems
• Online Primal-Dual Algorithms for Covering and Packing
• An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
• The Online Set Cover Problem
• On Column-Restricted and Priority Covering Integer Programs
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• A Primal-Dual Randomized Algorithm for Weighted Paging

This page was built for publication: Approximating Sparse Covering Integer Programs Online