A subexponential bound for linear programming

DOI10.1007/BF01940877zbMath0857.68119OpenAlexW2152479402WikidataQ54309309 ScholiaQ54309309MaRDI QIDQ1923862

Micha Sharir, Ji{ří} Matoušek, Ermo Welzl

Publication date: 18 February 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940877

zbMATH Keywords

combinatorial optimization randomized incremental algorithms

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Random sampling in computational algebra: Helly numbers and violator spaces, Geometric random edge, The Theory of Universal Graphs for Infinite Duration Games, Helly-type theorems and generalized linear programming, Exact primitives for smallest enclosing ellipses, Solving Linear Programming with Constraints Unknown, The Random‐Facet simplex algorithm on combinatorial cubes, Optimization-based mesh correction with volume and convexity constraints, On the planar piecewise quadratic 1-center problem, On the smallest enclosing information disk, OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS, COMPUTING ROUNDNESS IS EASY IF THE SET IS ALMOST ROUND, On geometric optimization with few violated constraints, Efficient piecewise-linear function approximation using the uniform metric, Bounds on the complexity of halfspace intersections when the bounded faces have small dimension, Combinatorial redundancy detection, THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, Linear time algorithms for Euclidean 1-center in $\mathfrak {R}^d$ with non-linear convex constraints, A combinatorial bound for linear programming and related problems, Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls, An exponential lower bound for Zadeh's pivot rule, Sectorial coverage control with load balancing in non-convex hollow environments, Removing degeneracy may require unbounded dimension increase, Clarkson's algorithm for violator spaces, Simple linear time algorithms for piercing pairwise intersecting disks, Stabbing pairwise intersecting disks by four points, No dimension-independent core-sets for containment under homothetics, Constant-Factor Approximation for TSP with Disks, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, The 2-center problem in three dimensions, Random sampling with removal, Helly’s theorem: New variations and applications, A Friendly Smoothed Analysis of the Simplex Method, QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS, Constraint Satisfaction Problems over Numeric Domains, Optimal Triangulation with Steiner Points, Unique sink orientations of grids, The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs, Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function, Algorithms for bivariate zonoid depth, Piercing pairwise intersecting geodesic disks, Polynomial-time algorithms for energy games with special weight structures, Markov incremental constructions, Violator spaces: Structure and algorithms, Cyclic games and linear programming, Optimal location of transportation devices, Voronoi diagrams with respect to criteria on vision information, A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games, A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane, An exponential lower bound for Cunningham's rule, Optimizing squares covering a set of points, Geometric matching algorithms for two realistic terrains, Two-variable linear programming in parallel, Analysis of incomplete data and an intrinsic-dimension Helly theorem, APPROXIMATING 3D POINTS WITH CYLINDRICAL SEGMENTS, A simple linear algorithm for computing rectilinear 3-centers, Unnamed Item, Largest bounding box, smallest diameter, and related problems on imprecise points, Random edge can be exponential on abstract cubes, On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes, Unnamed Item, Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints, Two-variable linear programming in parallel, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Unnamed Item, Deterministic Algorithms for Unique Sink Orientations of Grids, Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games, Violator spaces vs closure spaces, The complexity of optimization on grids, A non-iterative algorithm for generalized pig games, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, A characterization theorem and an algorithm for a convex hull problem, Streaming algorithms for extent problems in high dimensions, Optimal Algorithms for Geometric Centers and Depth, Combinatorial structure and randomized subexponential algorithms for infinite games

Cites Work