Odstranění degenerovanosti může vyžadovat velký vzrůst dimenze

Abstrakt

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.

Klíčová slova

• Removing
• degeneracy
• require
• large
• dimension
• increase