Linear Programming in Linear Time When the Dimension Is Fixed

Recommendations

A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
Las Vegas algorithms for linear and integer programming when the dimension is small
Parallel linear programming in fixed dimension almost surely in constant time
scientific article; zbMATH DE number 1182931
Small-dimensional linear programming and convex hulls made easy

Cited in

(only showing first 100 items - show all)

Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications
On the 2-center problem under convex polyhedral distance function
Transversal of disjoint convex polygons.
Open questions in complexity theory for numerical optimization
Measure of circularity for parts of digital boundaries and its fast computation
Approximate maximum rank aggregation: beyond the worst-case
Space-efficient planar convex hull algorithms
Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices
Linear Time Algorithms for Two- and Three-Variable Linear Programs
Using separation algorithms in fixed dimension
An optimal parallel algorithm for digital curve segmentation
Two-variable linear programming in parallel
Sorting weighted distances with applications to objective function evaluations in single facility location problems.
Quantitative Steinitz's theorems with applications to multifingered grasping
A fast deterministic smallest enclosing disk approximation algorithm
Linear time algorithms for Euclidean 1-center in $\mathfrak {R}^d$ with non-linear convex constraints
Linear time algorithms for Euclidean 1-center in $\mathfrak {R}^d$ with non-linear convex constraints
Rectilinear m -Center problem
Recognition of digital hyperplanes and level layers with forbidden points
Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions
On the angle restricted nearest neighbor problem
A parallel algorithm for approximate regularity.
Faster algorithms for next breakpoint and max value for parametric global minimum cuts
Randomized geometric algorithms and pseudorandom generators
COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
On polynomial kernels for sparse integer linear programs
Derandomizing an output-sensitive convex hull algorithm in three dimensions
Assigning weights to minimize the covering radius in the plane
Output-sensitive cell enumeration in hyperplane arrangements
APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
Weighted Rectilinear Approximation of Points in the Plane
A randomized algorithm for fixed-dimensional linear programming
A new O(n \,n) algorithm for computing the intersection of convex polygons
Finding effective ``Force targets for two-dimensional, multifinger frictional grips
Extremal polygon containment problems
Covering convex polygons by two congruent disks
Covering convex polygons by two congruent disks
Multi-dimensional dynamic facility location and fast computation at query points
A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane
Efficient algorithms for the one-dimensional $k$-center problem
Polynomial algorithms for linear programming over the algebraic numbers
Fixed-parameter complexity and approximability of norm maximization
A linear algorithm for integer programming in the plane
Piercing intersecting convex sets
A combinatorial bound for linear programming and related problems
Smoothing method for minimizing the sum of therlargest functions
Digital planarity -- a review
Constructing the convex hull of a partially sorted set of points
Minimizing the error of linear separators on linearly inseparable data
Approximating points by a piecewise linear function
Deepest point of a polyhedron and linear programming
Free-form surface partition in 3-d
Inverse p-median problems with variable edge lengths
A linear-time algorithm for linear $L_ 1$ approximation of points
Efficient randomized algorithms for some geometric optimization problems
Reconstructing polygons from scanner data
Linear programming in $O(n\times 3^{d^2})$ time
Positive Alexander duality for pursuit and evasion
Fuzzy versions of the covering circle problem
Algorithms for weak and wide separation of sets
Linear programming with variable matrix entries
An optimal randomized algorithm for $d$-variate zonoid depth
On detecting spatial regularity in noisy images
Minmax regret 1-facility location on uncertain path networks
On the complexity of polyhedral separability
A polynomial algorithm for a continuous bilevel knapsack problem
Geometric problems in automated manufacturing.
Static and streaming data structures for Fréchet distance queries
Cutting hyperplanes for divide-and-conquer
Efficiently testing digital convexity and recognizing digital convex polygons
A primal algorithm for the weighted minimum covering ball problem in $\mathbb {R}^n$
Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
On lines missing polyhedral sets in 3-space
A generalization of the concept of distance based on the simplex inequality
Applications of random sampling in computational geometry. II
A faster FPTAS for knapsack problem with cardinality constraint
A faster FPTAS for knapsack problem with cardinality constraint
Optimal algorithm for the planar two-center problem
Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
Optimal algorithms for geometric centers and depth
Linear time algorithms for linear programming
Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
The k-center problem of uncertain points on graphs
Output-sensitive results on convex hulls, extreme points, and related problems
Fast integer programming in fixed dimension
Separation and approximation of polyhedral objects
Opaque sets
Geometric pattern matching for point sets in the plane under similarity transformations
A dual algorithm for the minimum covering ball problem in $\mathbb R^n$
THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
Point location in zones of $k$-flats in arrangements
A faster dual algorithm for the Euclidean minimum covering ball problem
Optimal conditions for connectedness of discretized sets
Optimization with additional variables and constraints
Stability radius and an upgrading model of median location on trees
Constraint satisfaction problems over numeric domains
Linear time algorithms for some separable quadratic programming problems
The inverse Fermat-Weber problem
Algorithms and complexity analysis for some flow problems
Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function

This page was built for publication: Linear Programming in Linear Time When the Dimension Is Fixed

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3778541)