Violator Spaces: Structure and Algorithms

Simple item page
dc.creatorGärtner, Bernd
dc.creatorMatousek, Jirka
dc.creatorRüst, Leo
dc.creatorSkovron, Petr
dc.date2006-06-20
dc.date2008-07-22
dc.date.accessioned2026-07-07T09:51:55Z
dc.date.available2026-07-07T09:51:55Z
dc.descriptionSharir 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).
dc.description28 pages, 5 figures, extended abstract was presented at ESA 2006; author spelling fixed
dc.identifierhttps://arxiv.org/abs/cs/0606087
dc.identifierhttp://arxiv.org/abs/cs/0606087
dc.identifierdoi:10.1007/11841036_36
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/165411
dc.subjectDiscrete Mathematics
dc.titleViolator Spaces: Structure and Algorithms
dc.typetext

Files

Collections

arXiv