Abstrakt
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í v malé 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.