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 algorithms (68W25) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

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)

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

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)