Linear Programming in Linear Time When the Dimension Is Fixed
From MaRDI portal
Publication:3778541
DOI10.1145/2422.322418zbMath0637.90064OpenAlexW1993058867WikidataQ93581035 ScholiaQ93581035MaRDI QIDQ3778541
Publication date: 1984
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2422.322418
Related Items (only showing first 100 items - show all)
Computation of penetration between smooth convex objects in three-dimensional space ⋮ Positive Alexander Duality for Pursuit and Evasion ⋮ Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ Random linear programs with many variables and few constraints ⋮ Solving Linear Programming with Constraints Unknown ⋮ Approximating points by a piecewise linear function ⋮ Output-sensitive cell enumeration in hyperplane arrangements ⋮ On the planar piecewise quadratic 1-center problem ⋮ Algorithmic and explicit determination of the Lovász number for certain circulant graphs ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ On Computing a Largest Empty Arbitrarily Oriented Rectangle ⋮ THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ A strongly polynomial algorithm for a new class of linear inequalities1 ⋮ Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm ⋮ A combinatorial bound for linear programming and related problems ⋮ A polynomial algorithm for a continuous bilevel knapsack problem ⋮ An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search ⋮ On the 2-Center Problem Under Convex Polyhedral Distance Function ⋮ Approximate nearest neighbor for curves: simple, efficient, and deterministic ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function ⋮ Recognition of Digital Hyperplanes and Level Layers with Forbidden Points ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Geometric problems in automated manufacturing. ⋮ FREE-FORM SURFACE PARTITION IN 3-D ⋮ Two-variable linear programming in parallel ⋮ An optimal randomized algorithm for \(d\)-variate zonoid depth ⋮ A simple linear algorithm for computing rectilinear 3-centers ⋮ Rectilinear m -Center problem ⋮ Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs ⋮ COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS ⋮ Smoothing method for minimizing the sum of therlargest functions ⋮ Fuzzy versions of the covering circle problem ⋮ Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints ⋮ Two-variable linear programming in parallel ⋮ On the minimum consistent subset problem ⋮ Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance ⋮ Weighted Rectilinear Approximation of Points in the Plane ⋮ Covering convex polygons by two congruent disks ⋮ Intersecting disks using two congruent disks ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions ⋮ Intersecting disks using two congruent disks ⋮ Deepest point of a polyhedron and linear programming ⋮ APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING ⋮ On Three Constrained Versions of the Digital Circular Arc Recognition Problem ⋮ General models in min-max planar location: Checking optimality conditions ⋮ One-way and round-trip center location problems ⋮ Fixed-parameter complexity and approximability of norm maximization ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ Covering convex polygons by two congruent disks ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ Optimal Algorithms for Geometric Centers and Depth ⋮ Polyhedral Assembly Partitioning Using Maximally Covered Cells in Arrangements of Convex Polytopes ⋮ On polynomial kernels for sparse integer linear programs ⋮ Computing circular separability ⋮ Extremal polygon containment problems ⋮ Optimal algorithms for some intersection radius problems ⋮ Finding transversals for sets of simple geometric figures ⋮ Distance measures on intersecting objects and their applications ⋮ On lines missing polyhedral sets in 3-space ⋮ Layout of facilities with some fixed points ⋮ A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\) ⋮ A fast deterministic smallest enclosing disk approximation algorithm ⋮ On detecting spatial regularity in noisy images ⋮ Minmax regret 1-facility location on uncertain path networks ⋮ Fuzzy disk for covering fuzzy points ⋮ A primal algorithm for the weighted minimum covering ball problem in \(\mathbb {R}^n\) ⋮ 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 approaches to the convex hull problem in \(\mathbb{R}^ m\) ⋮ A generalization of the concept of distance based on the simplex inequality ⋮ Separation and approximation of polyhedral objects ⋮ Optimal conditions for connectedness of discretized sets ⋮ A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Linear programming, the simplex algorithm and simple polytopes ⋮ Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming ⋮ A linear-time algorithm for linear \(L_ 1\) approximation of points ⋮ Digital planarity -- a review ⋮ Space-efficient planar convex hull algorithms ⋮ On the complexity of polyhedral separability ⋮ 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 ⋮ Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints ⋮ The multi-service center problem ⋮ An optimal parallel algorithm for digital curve segmentation ⋮ 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 ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Continuous location of dimensional structures. ⋮ Efficiently testing digital convexity and recognizing digital convex polygons ⋮ On the angle restricted nearest neighbor problem ⋮ Random sampling with removal
This page was built for publication: Linear Programming in Linear Time When the Dimension Is Fixed
