Linear Time Algorithms for Two- and Three-Variable Linear Programs
From MaRDI portal
Publication:3315272
DOI10.1137/0213003zbMath0532.90063OpenAlexW2078908612MaRDI 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
convexitypolynomial time algorithmgeometric algorithmarithmetic atomic operationsdominance of linear functionslinear-time median finding algorithmspolynomiality in the number of constraints and variablesthree-variable problemtwo-variable problems
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)
Related Items
Computing circular separability, Optimal algorithms for some intersection radius problems, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, A new bound and an \(O(mn)\) algorithm for the undesirable 1-median problem (maxian) on networks, Approximating points by a piecewise linear function, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Distribution-sensitive algorithms, Minimum polygonal separation, Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon, Efficient piecewise-linear function approximation using the uniform metric, On the detection of a common intersection of k convex subjects in the plane, THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Group centre and group median of a network, A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times, The minmax regret gradual covering location problem on a network with incomplete information of demand weights, On the angle restricted nearest neighbor problem, An optimal parallel algorithm for linear programming in the plane, Algorithms for high dimensional stabbing problems, Minimum-sum dipolar spanning tree in \(\mathbb R^3\), Small-dimensional linear programming and convex hulls made easy, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, Efficient algorithms for the one-dimensional \(k\)-center problem, Geometric orderings of intersecting translates and their applications, On Anstreicher's combined phase I-phase II projective algorithm for linear programming, The double pivot simplex method, FREE-FORM SURFACE PARTITION IN 3-D, Outlier respecting points approximation, Robust location problems with pos/neg weights on a tree, Two-variable linear programming in parallel, Open questions in complexity theory for numerical optimization, Seven fingers allow force-torque closure grasps on any convex polyhedron, Cutting hyperplanes for divide-and-conquer, On simplex method with most-obtuse-angle rule and cosine rule, Minmax earliness-tardiness costs with unit processing time jobs, Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs, Scheduling with a common due-window: polynomially solvable cases, Linear updates for a single-phase projective method, Computing the geodesic center of a simple polygon, Minimax regret 1-median problem in dynamic path networks, Two-variable linear programming in parallel, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case, Constructing the convex hull of a partially sorted set of points, On the ball spanned by balls, Computing shortest transversals, Robust economic order quantity models, A linear programming approach to highly precise clock synchronization over a packet network, Locational optimization problems solved through Voronoi diagrams, A randomized algorithm for fixed-dimensional linear programming, On computing the closest boundary point on the convex hull, Algorithms for the robust 1-center problem on a tree, General models in min-max planar location: Checking optimality conditions, A geometrical solution for quadratic bicriteria location models, Assigning weights to minimize the covering radius in the plane, The Location of Undesirable Facilities, Efficient algorithm for transversal of disjoint convex polygons., Transversal of disjoint convex polygons.
