Linear Time Algorithms for Two- and Three-Variable Linear Programs
From MaRDI portal
Publication:3315272
DOI10.1137/0213003zbMath0532.90063MaRDI QIDQ3315272
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213003
convexity; polynomial time algorithm; geometric algorithm; arithmetic atomic operations; dominance of linear functions; linear-time median finding algorithms; polynomiality in the number of constraints and variables; three-variable problem; two-variable problems
68Q25: Analysis of algorithms and problem complexity
65K05: Numerical mathematical programming methods
90C05: Linear programming
Related Items
THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS, Minmax earliness-tardiness costs with unit processing time jobs, Two-variable linear programming in parallel, Computing the geodesic center of a simple polygon, Geometric orderings of intersecting translates and their applications, Open questions in complexity theory for numerical optimization, Computing shortest transversals, On the angle restricted nearest neighbor problem, An optimal parallel algorithm for linear programming in the plane, Algorithms for high dimensional stabbing problems, A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case, Computing circular separability, Minimum polygonal separation, Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon, On the detection of a common intersection of k convex subjects in the plane, Group centre and group median of a network, Small-dimensional linear programming and convex hulls made easy, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, On Anstreicher's combined phase I-phase II projective algorithm for linear programming, Seven fingers allow force-torque closure grasps on any convex polyhedron, Cutting hyperplanes for divide-and-conquer, On the ball spanned by balls, Robust economic order quantity models, Locational optimization problems solved through Voronoi diagrams, A geometrical solution for quadratic bicriteria location models, Optimal algorithms for some intersection radius problems, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Algorithms for the robust 1-center problem on a tree, Constructing the convex hull of a partially sorted set of points, A randomized algorithm for fixed-dimensional linear programming, On computing the closest boundary point on the convex hull, Efficient algorithm for transversal of disjoint convex polygons., Transversal of disjoint convex polygons., A new bound and an \(O(mn)\) algorithm for the undesirable 1-median problem (maxian) on networks, Efficient piecewise-linear function approximation using the uniform metric, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Linear updates for a single-phase projective method, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs, General models in min-max planar location: Checking optimality conditions, Robust location problems with pos/neg weights on a tree
