Approximability of Sparse Integer Programs

DOI10.1007/978-3-642-04128-0_8MaRDI QIDQ3639237zbMATH OpenOpenAlexFDO

Authors

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_8

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Integer programming (90C10)

Recommendations

• Approximability of sparse integer programs
• Approximation algorithms for covering/packing integer programs
• On k-column sparse packing programs
• On approximating (sparse) covering integer programs
• \(\ell_1\)-sparsity approximation bounds for packing integer programs

Cited in

(24)

• Approximability of sparse integer programs
• Sparsity of integer solutions in the average case
• New class of 0-1 integer programs with tight approximation via linear relaxations
• Compact representation of near-optimal integer programming solutions
• Algorithms to approximate column-sparse packing problems
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• Approximation algorithms for covering/packing integer programs
• Sparsity of integer formulations for binary programs
• Approximation Bounds for Sparse Programs
• Parameterized complexity of sparse linear complementarity problems
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• Using structural properties for integer programs
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• Approximate fixed-rank closures of covering problems
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• A primal-dual approximation algorithm for min-sum single-machine scheduling problems
• Some lower bounds on sparse outer approximations of polytopes
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
• Approximating integer programs with positive right-hand sides
• Iterative packing for demand and hypergraph matching
• Distributed algorithms for covering, packing and maximum weighted matching
• On k-column sparse packing programs
• Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance

This page was built for publication: Approximability of Sparse Integer Programs

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