Odstraňování degenerovaností v problémech typu LP může vyžadovat růst dimenze

Abstrakt

Zkonstruujeme příklad problému typu LP dimenze 4, jehož každé nedegenerované zjemnění má dimenzi alespoň 6. Ukážeme souvislost s problémem pokrývání jisté částečně uspořádané množiny Booleovými algebrami.

Klíčová slova

• Removing
• degeneracies
• LP-type
• problems
• increase
• dimension