Solving packing integer programs via randomized rounding with alterations

DOI10.4086/TOC.2012.V008A024MaRDI QIDQ3191563zbMATH OpenOpenAlexFDO

Authors N. Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2012.v008a024

zbMATH Keywords

approximation algorithmspacking integer programssubmodular functions

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25) Integer programming (90C10)

Recommendations

• On k-column sparse packing programs
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• _1-sparsity approximation bounds for packing integer programs
• scientific article; zbMATH DE number 6850331
• Improved Approximation Guarantees for Packing and Covering Integer Programs

Cites work

• Improved approximations for k-exchange systems (extended abstract)
• Optimal approximation for the submodular welfare problem in the value oracle model

Cited in

(13)

• Primal beats dual on online packing LPs in the random-order model
• Scheduling split intervals with non-uniform demands
• Approximating sparse covering integer programs online
• Network pollution games
• New results for network pollution games
• Algorithms to approximate column-sparse packing problems
• scientific article; zbMATH DE number 1830719 (Why is no real title available?)
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• _1-sparsity approximation bounds for packing integer programs
• Streaming algorithms for submodular function maximization
• Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints
• On k-column sparse packing programs
• Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

This page was built for publication: Solving packing integer programs via randomized rounding with alterations

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