k-violation linear programming

DOI10.1016/0020-0190(94)00134-0zbMATH Open0816.90103OpenAlexW2074818189MaRDI QIDQ1336744FDOQ1336744

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

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

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)

Cites Work

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

Cited In (12)

• Computing Shortest Paths in the Plane with Removable Obstacles
• Title not available (Why is that?)
• Approximation algorithms for the covering-type \(k\)-violation linear program
• Low-Dimensional Linear Programming with Violations
• Approximating points by a piecewise linear function
• Minimizing the error of linear separators on linearly inseparable data
• 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
• Geometric path problems with violations
• Outlier respecting points approximation

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)