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