Violator Spaces: Structure and Algorithms

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

28 pages, 5 figures, extended abstract was presented at ESA 2006; author spelling fixed

Scientific paper

10.1007/11841036_36

Sharir and Welzl introduced an abstract framework for optimization problems, called LP-type problems or also generalized linear programming problems, which proved useful in algorithm design. We define a new, and as we believe, simpler and more natural framework: violator spaces, which constitute a proper generalization of LP-type problems. We show that Clarkson's randomized algorithms for low-dimensional linear programming work in the context of violator spaces. For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems: they are equivalent to acyclic violator spaces, as well as to concrete LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Violator Spaces: Structure and Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Violator Spaces: Structure and Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Violator Spaces: Structure and Algorithms will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-39979

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.