A subexponential bound for linear programming
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- A Subexponential Algorithm for Abstract Optimization Problems
- A Theorem Concerning the Integer Lattice
- A new polynomial-time algorithm for linear programming
- A note on approximate linear programming
- A randomized algorithm for fixed-dimensional linear programming
- An observation on the structure of production sets with indivisibilities
- Ellipsoid coverings with minimal volumina.
- Helly-type theorems and generalized linear programming
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Linear Programming in Linear Time When the Dimension Is Fixed
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- Lower bounds for a subexponential optimization algorithm
- New applications of random sampling in computational geometry
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
- Polynomial algorithms in linear programming
- Small-dimensional linear programming and convex hulls made easy
- Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
Cited in
(93)- Piercing pairwise intersecting geodesic disks
- A non-iterative algorithm for generalized pig games
- The complexity of optimization on grids
- Lower bounds for a subexponential optimization algorithm
- Geometric matching algorithms for two realistic terrains
- Optimization-based mesh correction with volume and convexity constraints
- Two-variable linear programming in parallel
- Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Quantile approximation for robust statistical estimation and \(k\)-enclosing problems
- Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints
- Optimal Triangulation with Steiner Points
- A friendly smoothed analysis of the simplex method
- Analysis of incomplete data and an intrinsic-dimension Helly theorem
- Largest bounding box, smallest diameter, and related problems on imprecise points
- Stabbing pairwise intersecting disks by four points
- A randomized algorithm for fixed-dimensional linear programming
- A characterization of Delsarte's linear programming bound as a ratio bound
- Optimizing squares covering a set of points
- Random sampling in computational algebra: Helly numbers and violator spaces
- A combinatorial bound for linear programming and related problems
- The complexity of all-switches strategy improvement
- The Theory of Universal Graphs for Infinite Duration Games
- A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane
- Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints
- Algorithms for bivariate zonoid depth
- Cyclic games and linear programming
- A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
- Network essence: PageRank completion and centrality-conforming Markov chains
- On the smallest enclosing information disk
- Exact primitives for smallest enclosing ellipses
- Sectorial coverage control with load balancing in non-convex hollow environments
- On the -exponential trajectory of linear programming
- Violator spaces: Structure and algorithms
- APPROXIMATING 3D POINTS WITH CYLINDRICAL SEGMENTS
- A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
- Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls
- A Subexponential Algorithm for Abstract Optimization Problems
- Helly-type theorems and generalized linear programming
- Randomized combinatorial algorithms for linear programming when the dimension is moderately high
- Optimal algorithms for geometric centers and depth
- Cospanning characterizations of violator and co-violator spaces
- Optimal location of transportation devices
- THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
- The domination heuristic for LP-type problems
- Sublinear exaves
- COMPUTING ROUNDNESS IS EASY IF THE SET IS ALMOST ROUND
- Unique sink orientations of grids
- Constraint satisfaction problems over numeric domains
- Constant-factor approximation for TSP with disks
- Combinatorial redundancy detection
- Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function
- Algorithms for polytope covering and approximation
- Clarkson's algorithm for violator spaces
- Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
- Numerical representations of a universal subspace flow for linear programs
- Random sampling with removal
- An exponential lower bound for Zadeh's pivot rule
- A simple linear algorithm for computing rectilinear 3-centers
- The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
- On geometric optimization with few violated constraints
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- The Random‐Facet simplex algorithm on combinatorial cubes
- The 2-center problem in three dimensions
- Random edge can be exponential on abstract cubes
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Simple linear time algorithms for piercing pairwise intersecting disks
- Helly’s theorem: New variations and applications
- Small-dimensional linear programming and convex hulls made easy
- Geometric random edge
- Upper and lower bounds on the smoothed complexity of the simplex method
- Two-variable linear programming in parallel
- OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS
- No dimension-independent core-sets for containment under homothetics
- On the planar piecewise quadratic 1-center problem
- Exponential lower bounds for history-based simplex pivot rules on abstract cubes
- An exponential lower bound for Cunningham's rule
- Streaming algorithms for extent problems in high dimensions
- Removing degeneracy may require unbounded dimension increase
- Randomized MWU for positive LPs
- Deterministic algorithms for unique sink orientations of grids
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
- A characterization theorem and an algorithm for a convex hull problem
- Efficient piecewise-linear function approximation using the uniform metric
- Voronoi diagrams with respect to criteria on vision information
- Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
- Violator spaces vs closure spaces
- scientific article; zbMATH DE number 1775049 (Why is no real title available?)
- Solving linear programming with constraints unknown
- A faster deterministic exponential time algorithm for energy games and mean payoff games
- Markov incremental constructions
- Combinatorial structure and randomized subexponential algorithms for infinite games
This page was built for publication: A subexponential bound for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923862)
