Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
From MaRDI portal
Publication:4327416
DOI10.1137/S0097539793251876zbMath0831.90089MaRDI QIDQ4327416
Dorit S. Hochbaum, Joseph (Seffi) Naor
Publication date: 6 April 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (46)
Relaxation-based algorithms for minimax optimization problems with resource allocation applications ⋮ Deciding probabilistic automata weak bisimulation: theory and practice ⋮ Optimal length resolution refutations of difference constraint systems ⋮ On approximation algorithms for the minimum satisfiability problem ⋮ The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes ⋮ The Linear Complementarity Problems with a Few Variables per Constraint ⋮ On a generalization of Horn constraint systems ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ A linear programming primer: from Fourier to Karmarkar ⋮ A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints ⋮ Local and global relational consistency ⋮ Minimum shared‐power edge cut ⋮ Applications and efficient algorithms for integer programming problems on monotone constraints ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ Improved algorithms for optimal length resolution refutation in difference constraint systems ⋮ A faster algorithm for determining the linear feasibility of systems of BTVPI constraints ⋮ A certifying algorithm for lattice point feasibility in a system of UTVPI constraints ⋮ Analyzing fractional Horn constraint systems ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The two variable per inequality abstract domain ⋮ A set partitioning reformulation of a school bus scheduling problem ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ Incremental closure for systems of two variables per inequality ⋮ On a decision procedure for quantified linear programs ⋮ Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints ⋮ Cyclic games and linear programming ⋮ Relaxing the strong triadic closure problem for edge strength inference ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ Tractability conditions for numeric CSPs ⋮ Finding a bounded mixed-integer solution to a system of dual network inequalities ⋮ A polynomial time algorithm for Zero-Clairvoyant scheduling ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem ⋮ Approximability of clausal constraints ⋮ A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations ⋮ On integer closure in a system of unit two variable per inequality constraints ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints ⋮ On memoryless provers and insincere verifiers ⋮ Inverse generalized minimum cost flow problem under the Hamming distances ⋮ Introduction to the Maximum Solution Problem ⋮ Querying temporal and spatial constraint networks in PTIME ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ An efficient algorithm for a class of constraint satisfaction problems ⋮ Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
This page was built for publication: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
