Violator spaces: structure and algorithms

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00100875" target="_blank" >RIV/00216208:11320/08:00100875 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Violator spaces: structure and algorithms
Original language description
We define a new abstract framework for optimization problems, violator spaces, which is a proper generalization of the LP-type problems introduced by Sharir and Welzl. We show that Clarkson's randomized algorithm for low-dimensional linear programming works 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.
Czech name
Porušovačské prostory - struktura a algoritmy
Czech description
Zavedeme nový axiomatický rámec pro popis optimalizačních problémů, takzvané porušovačské prostory, což je pojem obecnější než problémy typu LP, zavedené Sharirem a Welzlem. Ukážeme, že Clarksonův pravděpodobnostní algoritmus pro lineární programování vmalé dimenzi se dá použít v kontextu porušovačských prostorů. Například tak dostaneme nejrychlejší známý algoritmus pro zobecněný problém lineární komplementarity s P-maticí s počtem bloků omezeným konstantou. Také podáme dvě nové charakterizace problémůtypu LP.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BD - Information theory
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)