Pivotování v lineární komplementaritě: dva polynomiální případy

Abstrakt

Studujeme chování jednoduchých metod hlavního pivotování pro problém lineární komplementarity s P-maticemi. Vyřešíme otevřený problém Morrise tak, že ukážeme, že Murtyho pivotovací pravidlo vede na Morrisových příkladech ke kvadratickému počtu iterací.

Dále ukážeme, že lineární komplementaritu s K-maticemi řeší libovolný pivotovací algoritmus v lineárním počtu iterací. Naším hlavním nástrojem jsou orientace hyperkrychlí s jedinečným stokem.

Klíčová slova

• Pivoting
• linear
• complementarity
• polynomial-time
• cases