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)

A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane
The C^m norm of a function with prescribed jets. II
Computing circular separability
Finding transversals for sets of simple geometric figures
Layout of facilities with some fixed points
A new O(n \,n) algorithm for computing the intersection of convex polygons
A linear-time algorithm for linear $L_ 1$ approximation of points
On the complexity of polyhedral separability
Convex hulls of samples from spherically symmetric distributions
Small-dimensional linear programming and convex hulls made easy
Quantitative Steinitz's theorems with applications to multifingered grasping
Finding effective ``Force targets for two-dimensional, multifinger frictional grips
Description of the optimal solution set of the linear programming problem and the dimension formula
Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under $l_ \infty$-distance
Cutting hyperplanes for divide-and-conquer
On the ball spanned by balls
A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources
Algorithms and complexity analysis for some flow problems
Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements
Extremal polygon containment problems
Optimal algorithms for some intersection radius problems
Distance measures on intersecting objects and their applications
On lines missing polyhedral sets in 3-space
Formulation of linear problems and solution by a universal machine
Polynomial algorithms for linear programming over the algebraic numbers
On the complexity of some basic problems in computational convexity. I. Containment problems
Derandomizing an output-sensitive convex hull algorithm in three dimensions
Linear programming, the simplex algorithm and simple polytopes
An optimal parallel algorithm for digital curve segmentation
Continuous location of dimensional structures.
Sorting weighted distances with applications to objective function evaluations in single facility location problems.
The traveling salesmanpProblem for lines in the plane
A parallel algorithm for approximate regularity.
A generalization of the concept of distance based on the simplex inequality
The multi-service center problem
A linear algorithm for integer programming in the plane
Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications
Facility location problems with uncertainty on the plane
Optimization with additional variables and constraints
Constructing the convex hull of a partially sorted set of points
Efficient randomized algorithms for some geometric optimization problems
Output-sensitive results on convex hulls, extreme points, and related problems
Applications of random sampling in computational geometry. II
A randomized algorithm for fixed-dimensional linear programming
Efficient algorithm for transversal of disjoint convex polygons.
Transversal of disjoint convex polygons.
Minimizing the sum of the $k$ largest functions in linear time.
Fuzzy disk for covering fuzzy points
Linear programming approaches to the convex hull problem in $\mathbb{R}^ m$
Separation and approximation of polyhedral objects
Efficient piecewise-linear function approximation using the uniform metric
Point location in zones of $k$-flats in arrangements
$\varepsilon$-approximation minimization of convex functions in fixed dimension
Randomized geometric algorithms and pseudorandom generators
A subexponential bound for linear programming
A practical but rigorous approach to sum-of-ratios optimization in geometric applications
A dual algorithm for the minimum covering weighted ball problem in ${\mathbb{R}^n}$
Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
Linear time algorithms for linear programming
Linear programming in $O(n\times 3^{d^2})$ time
Efficient algorithms for approximate smooth selection
Piecewise linear valued constraint satisfaction problems with fixed number of variables
State feedback for set stabilization of Markovian jump Boolean control networks
Strongly polynomial FPTASes for monotone dynamic programs
Optimal conditions for connectedness of discretized sets
Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
Linear time algorithms for Euclidean 1-center in $\mathfrak {R}^d$ with non-linear convex constraints
Efficiently testing digital convexity and recognizing digital convex polygons
Random sampling with removal
Simultaneous scheduling and location (ScheLoc): The planar ScheLoc makespan problem
Robust self-triggered control for time-varying and uncertain constrained systems via reachability analysis
Assigning weights to minimize the covering radius in the plane
Fixed-parameter complexity and approximability of norm maximization
A characterization theorem and an algorithm for a convex hull problem
Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
Approximating points by a piecewise linear function
On the planar piecewise quadratic 1-center problem
Algorithmic and explicit determination of the Lovász number for certain circulant graphs
Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
A polynomial algorithm for a continuous bilevel knapsack problem
Geometric problems in automated manufacturing.
An optimal randomized algorithm for $d$-variate zonoid depth
A simple linear algorithm for computing rectilinear 3-centers
Linear programming with variable matrix entries
Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs
General models in min-max planar location: Checking optimality conditions
One-way and round-trip center location problems
On polynomial kernels for sparse integer linear programs
Approximate nearest neighbor for curves: simple, efficient, and deterministic
Linear time algorithms for Euclidean 1-center in $\mathfrak {R}^d$ with non-linear convex constraints
On detecting spatial regularity in noisy images
On the 2-center problem under convex polyhedral distance function
Minmax regret 1-facility location on uncertain path networks
Recognition of digital hyperplanes and level layers with forbidden points
A primal algorithm for the weighted minimum covering ball problem in $\mathbb {R}^n$
Rectilinear m -Center problem
Towards a Genuinely Polynomial Algorithm for Linear Programming
Linear Time Algorithms for Two- and Three-Variable Linear Programs
Solving linear programming with constraints unknown
APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING

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)