Violator Spaces: Structure and Algorithms
<|reference_start|>Violator Spaces: Structure and Algorithms: 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).<|reference_end|>
@article{gärtner2006violator,
    title={Violator Spaces: Structure and Algorithms},
    author={Bernd G"artner and Jirka Matousek and Leo R"ust and Petr Skovron},
    journal={arXiv preprint arXiv:cs/0606087},
    year={2006},
    doi={10.1007/11841036_36},
    archivePrefix={arXiv},
    eprint={cs/0606087},
    primaryClass={cs.DM}
}