\(k\)-violation linear programming

DOI10.1016/0020-0190(94)00134-0zbMath0816.90103OpenAlexW2074818189MaRDI QIDQ1336744

Peter Widmayer, Thomas Roos

Publication date: 13 July 1995

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00134-0

zbMATH Keywords

computational geometry\(k\)-violation linear programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Approximating points by a piecewise linear function ⋮ Covering Linear Programming with Violations ⋮ Shortest paths in the plane with obstacle violations ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Geometric path problems with violations ⋮ Outlier respecting points approximation ⋮ Unnamed Item ⋮ Computing the least quartile difference estimator in the plane ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Approximation algorithms for the covering-type \(k\)-violation linear program ⋮ Computing Shortest Paths in the Plane with Removable Obstacles

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• On levels in arrangements and Voronoi diagrams
• Randomized optimal algorithm for slope selection
• An upper bound on the number of planar \(K\)-sets
• Applications of random sampling in computational geometry. II
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• On k-Hulls and Related Problems
• An Optimal-Time Algorithm for Slope Selection
• Polynomial algorithms in linear programming
• Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
• Constructing Belts in Two-Dimensional Arrangements with Applications
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION