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
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, 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
