A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
From MaRDI portal
Recommendations
- A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
- A polynomial combinatorial algorithm for generalized minimum cost flow
- scientific article; zbMATH DE number 66616
- A strongly polynomial algorithm for linear systems having a binary solution
- A new polynomial-time algorithm for linear programming
Cited in
(only showing first 100 items - show all)- 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_ 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
- A feasible flow-based iterative algorithm for the two-level hierarchical time minimization transportation problem
- FPT-algorithms for some problems related to integer programming
- Minimum-cost b-edge dominating sets on trees
- Two level hierarchical time minimizing transportation problem
- Locating tree-shaped facilities using the ordered median objective
- Optimization with additional variables and constraints
- A primal-simplex based Tardos' algorithm
- 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
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- On complexity, representation and approximation of integral multicommodity flows
- An algorithm to compute the nucleolus of shortest path games
- On the computational complexity of finding a sparse Wasserstein barycenter
- A polyhedral model for enumeration and optimization over the set of circuits
- Short simplex paths in lattice polytopes
- Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
- On dominating set of some subclasses of string graphs
- A primal-dual approximation algorithm for \textsc{minsat}
- On lattice point counting in -modular polyhedra
- On circuit diameter bounds via circuit imbalances
- On solving a non-convex quadratic programming problem involving resistance distances in graphs
- Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals
- Mobile facility location: combinatorial filtering via weighted occupancy
- A cooperative location game based on the 1-center location problem
- Vanishing of Littlewood-Richardson polynomials is in P
- Feasibility checking in Horn constraint systems through a reduction based approach
- Geometric random edge
- Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly
- A combinatorial algorithm for Horn programs
- Optimization with binet matrices
- A rounding algorithm for approximating minimum Manhattan networks
- Complexity and algorithms for nonlinear optimization problems
- A class of polynomially solvable linear complementarity problems
- Max-min sum minimization transportation problem
- Circuit walks in integral polyhedra
- A polyhedral study of lifted multicuts
- 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
- A polynomial combinatorial algorithm for generalized minimum cost flow
- The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
- Minimum-cost \(b\)-edge dominating sets on trees
- On Chubanov's Method for Linear Programming
- A strongly polynomial algorithm for generalized flow maximization
- Strongly polynomial algorithm for solving the general problem of least modules
- 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
- An iterative algorithm for two level hierarchical time minimization transportation problem
- On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
- On a quadratic programming problem involving distances in trees
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Polyhedral Combinatorics in Combinatorial Optimization
- scientific article; zbMATH DE number 4057295 (Why is no real title available?)
- scientific article; zbMATH DE number 14735 (Why is no real title available?)
- A Strongly Polynomial Algorithm for a Special Class of Linear Programs
- scientific article; zbMATH DE number 66616 (Why is no real title available?)
- On bilevel machine scheduling problems
- Cooperative location games based on the minimum diameter spanning Steiner subgraph problem
- Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
- The inverse 1-median problem on tree networks with variable real edge lengths
- A submodular optimization problem with side constraints
- Approximation algorithms for intersection graphs
- Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems
This page was built for publication: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3030579)
