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)- Complexity and algorithms for nonlinear optimization problems
- Multicommodity network flows: a survey. I: Applications and formulations
- Open questions in complexity theory for numerical optimization
- A strongly polynomial algorithm for linear systems having a binary solution
- On the computational complexity of finding a sparse Wasserstein barycenter
- Small Littlewood-Richardson coefficients
- scientific article; zbMATH DE number 14735 (Why is no real title available?)
- Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices
- On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
- On some geometric optimization problems with segments
- A submodular optimization problem with side constraints
- A strongly polynomial algorithm for the minimum maximum flow degree problem
- New algorithms for generalized network flows
- Minimum cost multicommodity network flow problem in time-varying networks: by decomposition principle
- Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals
- A primal-dual approximation algorithm for \textsc{minsat}
- On polynomial solvability of the high multiplicity total weighted tardiness problem
- Algorithms and complexity for the almost equal maximum flow problem
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
- Optimization with binet matrices
- Minimizing convex functions with rational minimizers
- Locating tree-shaped facilities using the ordered median objective
- A polynomial combinatorial algorithm for generalized minimum cost flow
- On circuit diameter bounds via circuit imbalances
- On the set of stable matchings in a bipartite graph
- On the Column Number and Forbidden Submatrices for -Modular Matrices
- A fully polynomial time projective method
- A class of polynomially solvable linear complementarity problems
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- An algorithm to compute the nucleolus of shortest path games
- On bilevel machine scheduling problems
- Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
- A fast maximum flow algorithm
- Short simplex paths in lattice polytopes
- Polyhedral Combinatorics in Combinatorial Optimization
- The inverse 1-median problem on tree networks with variable real edge lengths
- What Tropical Geometry Tells Us about the Complexity of Linear Programming
- A strongly polynomial algorithm for bimodular integer linear programming
- Polynomial algorithms for linear programming over the algebraic numbers
- 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
- A combinatorial bound for linear programming and related problems
- Tensors in computations
- Cost allocation for set covering: the happy nucleolus
- scientific article; zbMATH DE number 4057295 (Why is no real title available?)
- Cooperative location games based on the minimum diameter spanning Steiner subgraph problem
- On Chubanov's Method for Linear Programming
- Multiflows in symmetric digraphs
- Deepest point of a polyhedron and linear programming
- Advances on strictly \(\varDelta \)-modular IPs
- Note on inverse problem with l_ objective function
- scientific article; zbMATH DE number 66616 (Why is no real title available?)
- A network flow approach to a common generalization of Clar and Fries numbers
- Inverse matroid intersection problem
- Max-min sum minimization transportation problem
- Inverse problem of minimum cuts
- Finding an interior point in the optimal face of linear programs
- FPT-algorithms for some problems related to integer programming
- Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
- A polynomial time primal network simplex algorithm for minimum cost flows
- Ranking functions for linear-constraint loops
- Strongly polynomial algorithm for solving the general problem of least modules
- A dual version of Tardos's algorithm for linear programming
- Near-linear time algorithm for n-fold ILPs via color coding
- 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
- Matchings under distance constraints. II.
- Two level hierarchical time minimizing transportation problem
- Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
- The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
- Hive-type polytopes for quiver multiplicities and the membership problem for quiver moment cones
- On the algorithmic inversion of the discrete Radon transform
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Advances on strictly -modular IPs
- Decomposition of probability marginals for security games in max-flow/min-cut systems
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- A faster algorithm for determining the linear feasibility of systems of BTVPI constraints
- A nonlinear knapsack problem
- The Maximum Flow Problem for Oriented Flows
- On dominating set of some subclasses of string graphs
- Integer programs with bounded subdeterminants and two nonzeros per row
- Subdeterminants and concave integer quadratic programming
- A first order method for linear programming parameterized by circuit imbalance
- Minimum-cost b-edge dominating sets on trees
- Polynomial algorithms to minimize 2/3-submodular functions
- Minimum-cost \(b\)-edge dominating sets on trees
- An iterative algorithm for two level hierarchical time minimization transportation problem
- A combinatorial algorithm for Horn programs
- A strongly polynomial algorithm for generalized flow maximization
- On complexity, representation and approximation of integral multicommodity flows
- Inverse center location problem on a tree
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Generalized max flows and augmenting paths
- A first order method for linear programming parameterized by circuit imbalance
- On circuit diameter bounds via circuit imbalances
- An application of simultaneous diophantine approximation in combinatorial optimization
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Weakly polynomial-time algorithms to minimize 2/3-submodular functions
- Optimization with additional variables and constraints
- A primal-simplex based Tardos' algorithm
- On the computational behavior of a polynomial-time network flow algorithm
- Constraint satisfaction problems over numeric domains
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)
