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
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, Algorithms for high dimensional stabbing problems, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Prune-and-search with limited workspace, 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, Weighted search in the plane, An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles, Efficient algorithms for the one-dimensional \(k\)-center problem, Distributed predictive control with minimization of mutual disturbances, Opaque sets, Outlier respecting points approximation, Algorithms for weak and wide separation of sets, Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices, Open questions in complexity theory for numerical optimization, Linear time algorithms for some separable quadratic programming problems, Inverse \(p\)-median problems with variable edge lengths, Linear programming in \(O(n\times 3^{d^2})\) time, 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, Reconstructing polygons from scanner data, Multi-dimensional dynamic facility location and fast computation at query points, The inverse Fermat-Weber problem, A linear algorithm for integer programming in the plane, Simultaneous scheduling and location (ScheLoc): The planar ScheLoc makespan problem, 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, Computing the geodesic center of a simple polygon, Geometric pattern matching for point sets in the plane under similarity transformations, Robust self-triggered control for time-varying and uncertain constrained systems via reachability analysis, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Measure of circularity for parts of digital boundaries and its fast computation, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, Constructing the convex hull of a partially sorted set of points, Efficient algorithms for approximate smooth selection, On the ball spanned by balls, The \(C^m\) norm of a function with prescribed jets. II, Piecewise linear valued constraint satisfaction problems with fixed number of variables, State feedback for set stabilization of Markovian jump Boolean control networks, Efficient randomized algorithms for some geometric optimization problems, Output-sensitive results on convex hulls, extreme points, and related problems, A dual approach to detect polyhedral intersections in arbitrary dimensions, Applications of random sampling in computational geometry. II, A randomized algorithm for fixed-dimensional linear programming, Assigning weights to minimize the covering radius in the plane, Strongly polynomial FPTASes for monotone dynamic programs, A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources, Efficient algorithm for transversal of disjoint convex polygons., Transversal of disjoint convex polygons., Minimizing the sum of the \(k\) largest functions in linear time., The traveling salesmanpProblem for lines in the plane, Algorithms and complexity analysis for some flow problems, Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements, A parallel algorithm for approximate regularity.
