Monotonizing linear programs with up to two nonzeroes per column

DOI10.1016/S0167-6377(03)00074-9MaRDI QIDQ1433661zbMATH OpenFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 468799
• Solving globally the linear multiplicative programming problem via monotonic functions
• Strict monotonicity in Todd's low-complexity algorithm for linear programming
• On monotonicity in the scaled potential algorithm for linear programming
• Solving strongly monotone linear complementarity problems
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• Matroid optimization problems with monotone monomials in the objective
• Monotone variable-metric algorithm for linearly constrained nonlinear programming
• An integer optimality condition for column generation on zero-one linear programs
• scientific article; zbMATH DE number 3939102

Cites work

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

Cited in

(11)

• Approximability of sparse integer programs
• Tightness of sensitivity and proximity bounds for integer linear programs
• Incremental closure for systems of two variables per inequality
• An analytical approach to the inference of summary data of additive type
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• A strongly polynomial algorithm for generalized flow maximization
• Reducing a monotone horizontal LCP to an LCP
• scientific article; zbMATH DE number 468799 (Why is no real title available?)
• The two variable per inequality abstract domain
• On the simplex algorithm for networks and generalized networks
• Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem

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

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