Polynomial algorithms in linear programming
From MaRDI portal
Publication:3910301
DOI10.1016/0041-5553(80)90061-0zbMath0459.90047OpenAlexW2033040247MaRDI QIDQ3910301
Publication date: 1980
Published in: USSR Computational Mathematics and Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0041-5553(80)90061-0
Related Items
Randomized strategies for robust combinatorial optimization with approximate separation, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, Learning lyapunov functions for hybrid systems, Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries, A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations, Robust vertex enumeration for convex hulls in high dimensions, \(k\)-violation linear programming, Minimum cost multiflows in undirected networks, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Interactive decision making: Equivalence of modified formulations, The mixed evacuation problem, SOS Is Not Obviously Automatizable, Even Approximately, Largest \(j\)-simplices in \(n\)-polytopes, Recognizing one-dimensional Euclidean preference profiles, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, Objective functions and the complexity of policy design, On integer programming with bounded determinants, The width and integer optimization on simplices with bounded minors of the constraint matrices, Simulating cardinal preferences in Boolean games: a proof technique, Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration, The \(p\)-hub center allocation problem, Fuzzy linear programming problems: models and solutions, An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming, Pivoting in linear complementarity: Two polynomial-time cases, A relaxed version of Karmarkar's method, A polynomial-time algorithm, based on Newton's method, for linear programming, On lattice point counting in \(\varDelta\)-modular polyhedra, The computational complexity of dominating set problems for instances with bounded minors of constraint matrices, Optimal priorities in GI|Gn|1 queue, The Gap Function: Evaluating Integer Programming Models over Multiple Right-Hand Sides, Multiflows and disjoint paths of minimum total cost, Optimal multi-unit mechanisms with private demands, “More(Same)-for-Less” Paradox In Minimal Cost Network Flow Problem, A subexponential bound for linear programming, Bin packing under linear constraints, Distributionally Robust Linear and Discrete Optimization with Marginals, Lower bounds for a subexponential optimization algorithm, Robust scheduling with budgeted uncertainty, Removing algorithmic discrimination (with minimal individual error), Joint robust optimization of bed capacity, nurse staffing, and care access under uncertainty, An exponential lower bound for Zadeh's pivot rule, Polynomial-time algorithms for multimarginal optimal transport problems with structure, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Unified representation of the classical ellipsoid method, Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods, Shortest path and maximum flow problems in networks with additive losses and gains, Min Sum Edge Coloring in Multigraphs Via Configuration LP, From Duels to Battlefields: Computing Equilibria of Blotto and Other Games, The Mixed Evacuation Problem, Unnamed Item, Polynomial-time data reduction for weighted problems beyond additive goal functions, Quantifying dynamical total coherence in a resource non-increasing framework, Convergence and Correctness of Max-Product Belief Propagation for Linear Programming, Unnamed Item, Shortest paths and convex hulls in 2D complexes with non-positive curvature, The problem of identifying the model of substitution of production factors, An extension of Chubanov's algorithm to symmetric cones, Detecting matrices of combinatorial rank three, Unique sink orientations of grids, Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling, A new mixed integer programming approach for optimization over the efficient set of a multiobjective linear programming problem, On the frontiers of polynomial computations in tropical geometry, The diagonalizability of quadratic functions and the arbitrariness of shadow prices, Improving a primal–dual simplex-type algorithm using interior point methods, An approach to characterize graded entailment of arguments through a label-based framework, Circumscribed ellipsoid algorithm for fixed-point problems, A natural randomization strategy for multicommodity flow and related algorithms, FPT-algorithms for some problems related to integer programming, Projection algorithms for linear programming, A utility theory based interactive approach to robustness in linear optimization, Unnamed Item, Relaxations of mixed integer sets from lattice-free polyhedra, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Optimization with additional variables and constraints, Minimum constellation covers: hardness, approximability and polynomial cases, A formalization of convex polyhedra based on the simplex method, Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm, Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates, Reasoning within fuzzy OWL 2 EL revisited, Computing Walrasian equilibria: fast algorithms and structural properties, Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes, Complexity, exactness, and rationality in polynomial optimization, Linear programming using limited-precision oracles, Complexity, exactness, and rationality in polynomial optimization, Integer program with bimodular matrix, Two design principles of geometric algorithms in finite-precision arithmetic, On the complexity of stable fractional hypergraph matching, Computational complexity of norm-maximization, FPT-algorithm for computing the width of a simplex given by a convex hull, Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games, Techniques of linear programming based on the theory of convex cones, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, An exterior-point method for linear programming problems, Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method, Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming, On the recognition of \(S\)-systems, The ellipsoid algorithm using parallel cuts, The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point, A Survey on Analog Models of Computation, Interior-point methods for linear programming: a review, A tool for deciding the satisfiability of continuous-time metric temporal logic, The computational complexity of three graph problems for instances with bounded minors of constraint matrices
