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