A combinatorial bound for linear programming and related problems

DOI10.1007/3-540-55210-3_213zbMath1494.68276OpenAlexW1789652828MaRDI QIDQ5096811

Micha Sharir, Ermo Welzl

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_213

zbMATH Keywords

linear programmingcombinatorial optimizationcomputational geometryrandomized incremental algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items

Random sampling in computational algebra: Helly numbers and violator spaces, Helly-type theorems and generalized linear programming, Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees, On the complexity of some basic problems in computational convexity. I. Containment problems, Computing the Rectilinear Center of Uncertain Points in the Plane, On geometric optimization with few violated constraints, A short proof of an interesting Helly-type theorem, Bipartite diameter and other measures under translation, Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints, Covering points by disjoint boxes with outliers, Removing degeneracy may require unbounded dimension increase, No dimension-independent core-sets for containment under homothetics, A Meeting Scheduling Problem Respecting Time and Space, Bounding Helly Numbers via Betti Numbers, Random sampling with removal, Helly’s theorem: New variations and applications, Unnamed Item, Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function, Polynomial-time algorithms for energy games with special weight structures, Helly-type theorems for approximate covering, Violator spaces: Structure and algorithms, An optimal randomized algorithm for \(d\)-variate zonoid depth, Random edge can be exponential on abstract cubes, Some Discrete Properties of the Space of Line Transversals to Disjoint Balls, Krein-Milman spaces, A dual simplex-type algorithm for the smallest enclosing ball of balls, Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization, Clustering in Hilbert’s Projective Geometry: The Case Studies of the Probability Simplex and the Elliptope of Correlation Matrices, Output-sensitive results on convex hulls, extreme points, and related problems, Violator spaces vs closure spaces, Removing degeneracy in LP-type problems revisited, A characterization theorem and an algorithm for a convex hull problem, Optimal Algorithms for Geometric Centers and Depth, Efficient algorithms for the minimum diameter bridge problem, Combinatorial structure and randomized subexponential algorithms for infinite games

Cites Work

• Unnamed Item
• Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
• Small-dimensional linear programming and convex hulls made easy
• A randomized algorithm for fixed-dimensional linear programming
• A subexponential bound for linear programming
• Linear programming in \(O(n\times 3^{d^2})\) time
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• Las Vegas algorithms for linear and integer programming when the dimension is small
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem