A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
From MaRDI portal
Publication:3030579
DOI10.1287/opre.34.2.250zbMath0626.90053OpenAlexW2103985627MaRDI QIDQ3030579
Publication date: 1986
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.34.2.250
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items
Random walks, totally unimodular matrices, and a randomised dual simplex algorithm ⋮ New algorithms for generalized network flows ⋮ Geometric random edge ⋮ Minimum cost multicommodity network flow problem in time-varying networks: by decomposition principle ⋮ Minimum cost multiflows in undirected networks ⋮ On the complexity of quadratic programming in real number models of computation ⋮ Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications ⋮ Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly ⋮ Polynomial algorithms for linear programming over the algebraic numbers ⋮ On dominating set of some subclasses of string graphs ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ An iterative algorithm for two level hierarchical time minimization transportation problem ⋮ An application of simultaneous diophantine approximation in combinatorial optimization ⋮ Refined proximity and sensitivity results in linearly constrained convex separable integer programming ⋮ A fully polynomial time projective method ⋮ Totally balanced and totally unimodular matrices defined by center location problems ⋮ A nonlinear knapsack problem ⋮ On a quadratic programming problem involving distances in trees ⋮ A feasible flow-based iterative algorithm for the two-level hierarchical time minimization transportation problem ⋮ Inverse matroid intersection problem ⋮ Linear programming, the simplex algorithm and simple polytopes ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ On circuit diameter bounds via circuit imbalances ⋮ Packing directed cycles efficiently ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ Multiflows and disjoint paths of minimum total cost ⋮ Algorithms for multicommodity flows in planar graphs ⋮ A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball ⋮ A strongly polynomial algorithm for the uniform balanced network flow problem ⋮ On solving a non-convex quadratic programming problem involving resistance distances in graphs ⋮ The complexity of mean flow time scheduling problems with release times ⋮ Circuit walks in integral polyhedra ⋮ Inverse optimization in high-speed networks ⋮ Streaming graph computations with a helpful advisor ⋮ Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees ⋮ On bilevel machine scheduling problems ⋮ Cooperative location games based on the minimum diameter spanning Steiner subgraph problem ⋮ Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks ⋮ Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm ⋮ Preemptive scheduling of independent jobs with release times and deadlines on a hypercube ⋮ Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient ⋮ A least-squares minimum-cost network flow algorithm ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ A combinatorial algorithm for Horn programs ⋮ The inverse 1-median problem on tree networks with variable real edge lengths ⋮ Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals ⋮ Inapproximability and a polynomially solvable special case of a network improvement problem. ⋮ Approximation algorithms for intersection graphs ⋮ A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem ⋮ On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals ⋮ On the computational behavior of a polynomial-time network flow algorithm ⋮ Optimization with binet matrices ⋮ Bilevel time minimizing transportation problem ⋮ A rounding algorithm for approximating minimum Manhattan networks ⋮ FPT-algorithms for some problems related to integer programming ⋮ Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices ⋮ Open questions in complexity theory for numerical optimization ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ Minimum-cost \(b\)-edge dominating sets on trees ⋮ A combinatorial certifying algorithm for linear feasibility in UTVPI constraints ⋮ An algorithm to compute the nucleolus of shortest path games ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ On polynomial solvability of the high multiplicity total weighted tardiness problem ⋮ Two level hierarchical time minimizing transportation problem ⋮ Locating tree-shaped facilities using the ordered median objective ⋮ Multiflows in symmetric digraphs ⋮ A strongly polynomial algorithm for linear systems having a binary solution ⋮ Optimization with additional variables and constraints ⋮ A cooperative location game based on the 1-center location problem ⋮ On the computational complexity of finding a sparse Wasserstein barycenter ⋮ A dual version of Tardos's algorithm for linear programming ⋮ A primal-simplex based Tardos' algorithm ⋮ Max-min sum minimization transportation problem ⋮ Inverse center location problem on a tree ⋮ Integer version of the multipath flow network synthesis problem ⋮ Small Littlewood-Richardson coefficients ⋮ On the inverse problem of linear programming and its application to minimum weight perfect \(k\)-matching ⋮ The one-machine just-in-time scheduling problem with preemption ⋮ On max-flow min-cut and integral flow properties for multicommodity flows in directed networks ⋮ Multicommodity flows in certain planar directed networks ⋮ Note on inverse problem with \(l_\infty\) objective function ⋮ Vanishing of Littlewood-Richardson polynomials is in P ⋮ A polyhedral model for enumeration and optimization over the set of circuits ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Inverse problems of submodular functions on digraphs ⋮ A modified layered-step interior-point algorithm for linear programming ⋮ A characterization of minimizable metrics in the multifacility location problem ⋮ Inverse problem of minimum cuts ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ Minimizing the sum of the \(k\) largest functions in linear time. ⋮ Feasibility checking in Horn constraint systems through a reduction based approach ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Bounded isotonic median regression ⋮ On the algorithmic inversion of the discrete Radon transform ⋮ Algorithms and complexity analysis for some flow problems ⋮ Finding an interior point in the optimal face of linear programs ⋮ Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality ⋮ Short simplex paths in lattice polytopes ⋮ Extended formulations for stable set polytopes of graphs without two disjoint odd cycles ⋮ Tensors in computations ⋮ 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties ⋮ Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles ⋮ Even circuits in oriented matroids ⋮ On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs ⋮ Minimum-Cost $$b$$-Edge Dominating Sets on Trees ⋮ On genuinely time bounded computations ⋮ Polyhedral Combinatorics in Combinatorial Optimization ⋮ Generalized max flows and augmenting paths ⋮ A fast maximum flow algorithm ⋮ On the set of stable matchings in a bipartite graph ⋮ Advances on strictly \(\varDelta \)-modular IPs ⋮ On the Column Number and Forbidden Submatrices for \(\Delta\)-Modular Matrices ⋮ A strongly polynomial algorithm for the minimum maximum flow degree problem ⋮ A faster algorithm for determining the linear feasibility of systems of BTVPI constraints ⋮ On Chubanov's Method for Linear Programming ⋮ A polyhedral study of lifted multicuts ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ Unnamed Item ⋮ The Maximum Flow Problem for Oriented Flows ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ A submodular optimization problem with side constraints ⋮ Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks ⋮ Robust partial inverse network flow problems ⋮ Unnamed Item ⋮ New and simple algorithms for stable flow problems ⋮ Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem ⋮ Subdeterminants and Concave Integer Quadratic Programming ⋮ Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths ⋮ Deepest point of a polyhedron and linear programming ⋮ The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption ⋮ Ranking Functions for Linear-Constraint Loops ⋮ Newell-Littlewood numbers ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
