Monotonizing linear programs with up to two nonzeroes per column
From MaRDI portal
Publication:1433661
DOI10.1016/S0167-6377(03)00074-9zbMath1056.90105MaRDI QIDQ1433661
Publication date: 1 July 2004
Published in: Operations Research Letters (Search for Journal in Brave)
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Related Items
Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, Approximability of sparse integer programs, The two variable per inequality abstract domain, Tightness of sensitivity and proximity bounds for integer linear programs, Incremental closure for systems of two variables per inequality, Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem, An analytical approach to the inference of summary data of additive type, A Strongly Polynomial Algorithm for Generalized Flow Maximization
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