A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
From MaRDI portal
Publication:3030579
DOI10.1287/opre.34.2.250zbMath0626.90053MaRDI 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
68Q25: Analysis of algorithms and problem complexity
65K05: Numerical mathematical programming methods
90C06: Large-scale problems in mathematical programming
90C05: Linear programming
90C27: Combinatorial optimization
Related Items
Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, Robust partial inverse network flow problems, A dual version of Tardos's algorithm for linear 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, Inverse center location problem on a tree, Multicommodity flows in certain planar directed networks, Bounded isotonic median regression, Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications, Packing directed cycles efficiently, The complexity of mean flow time scheduling problems with release times, 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, Bilevel time minimizing transportation problem, Integer version of the multipath flow network synthesis problem, The one-machine just-in-time scheduling problem with preemption, New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems, An application of simultaneous diophantine approximation in combinatorial optimization, A fully polynomial time projective method, Totally balanced and totally unimodular matrices defined by center location problems, Algorithms for multicommodity flows in planar graphs, 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, On polynomial solvability of the high multiplicity total weighted tardiness problem, On max-flow min-cut and integral flow properties for multicommodity flows in directed networks, Note on inverse problem with \(l_\infty\) objective function, A modified layered-step interior-point algorithm for linear programming, Inverse problem of minimum cuts, 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, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, New algorithms for generalized network flows, Minimum cost multiflows in undirected networks, On the complexity of quadratic programming in real number models of computation, Polynomial algorithms for linear programming over the algebraic numbers, A primal-dual interior point method whose running time depends only on the constraint matrix, Inverse matroid intersection problem, Linear programming, the simplex algorithm and simple polytopes, A polynomial time primal network simplex algorithm for minimum cost flows, Multiflows and disjoint paths of minimum total cost, 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, Inverse optimization in high-speed networks, Inapproximability and a polynomially solvable special case of a network improvement problem., Inverse problems of submodular functions on digraphs, A characterization of minimizable metrics in the multifacility location problem, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, On the algorithmic inversion of the discrete Radon transform, Two level hierarchical time minimizing transportation problem, Locating tree-shaped facilities using the ordered median objective, Optimization with additional variables and constraints, On the inverse problem of linear programming and its application to minimum weight perfect \(k\)-matching, Some aspects of studying an optimization or decision problem in different computational models, Minimizing the sum of the \(k\) largest functions in linear time., Refined proximity and sensitivity results in linearly constrained convex separable integer programming, A nonlinear knapsack problem, On complexity, representation and approximation of integral multicommodity flows, Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly, Optimization with binet matrices, A rounding algorithm for approximating minimum Manhattan networks, Complexity and algorithms for nonlinear optimization problems, Max-min sum minimization transportation problem, Polyhedral Combinatorics in Combinatorial Optimization
