Removing degeneracy may require a large dimension increase

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

Result language
angličtina
Original language name
Removing degeneracy may require a large dimension increase
Original language description
The result can be regarded as an indication that the problem of removing degeneracies in geometric computations has no simple 'abstract' solution. We consider LP-type problems, a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. We prove that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by an arbitrarily large amount.
Czech name
Odstranění degenerovanosti může vyžadovat velký vzrůst dimenze
Czech description
Výsledek naznačuje, že problém odstranění degenerovanosti v geometrických algoritmech nemá žádné jednoduché 'abstraktní' řešení. Uvažují se problémy typu LP, což je axiomatický rámec pro optimalizační problémy, zahrnující mimo jiné lineární programovánínebo hledání minimální koule obsahující dané body. Dokazuje se, že pro odstranění degenerovanosti LP=type problému je někdy nutné zvýšit dimenzi o libovolně velké číslo.

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
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)