Monotonizing linear programs with up to two nonzeroes per column

DOI10.1016/S0167-6377(03)00074-9zbMath1056.90105MaRDI QIDQ1433661

Dorit S. Hochbaum

Publication date: 1 July 2004

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

Approximation algorithmsGeneralize flowHalf integral solutionsMonotone constraints

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (8)

Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Approximability of sparse integer programs ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ The two variable per inequality abstract domain ⋮ An analytical approach to the inference of summary data of additive type ⋮ Incremental closure for systems of two variables per inequality ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial algorithm for b-matchings: An alternative approach
• An approximation algorithm for the generalized assignment problem
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• New algorithms for generalized network flows
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• New approaches for optimizing over the semimetric polytope
• Combinatorial Approximation Algorithms for Generalized Flow Problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Sensitivity theorems in integer linear programming
• Node-Deletion Problems on Bipartite Graphs
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Some Properties of Graphs with Multiple Edges
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow

This page was built for publication: Monotonizing linear programs with up to two nonzeroes per column