k-violation linear programming

DOI10.1016/0020-0190(94)00134-0MaRDI QIDQ1336744zbMATH OpenOpenAlexFDO

Authors Thomas Roos, Peter Widmayer

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

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

Recommendations

• Low-Dimensional Linear Programming with Violations
• On geometric optimization with few violated constraints
• Approximation algorithms for the covering-type \(k\)-violation linear program
• Violator spaces: Structure and algorithms
• Violator Spaces: Structure and Algorithms

Cites work

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

Cited in

(12)

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

This page was built for publication: \(k\)-violation linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336744)