Orientovaný matroid - Oriented matroid - Wikipedia

Teorie orientovaných matroidů umožňuje kombinatorický přístup k věta o maximálním toku o minimálním řezu. Síť s hodnotou toku rovnou kapacitě s-t řezu

An orientovaný matroid je matematický struktura který abstrahuje vlastnosti řízené grafy, vektor uspořádání nad objednanými poli a uspořádání nadroviny přes seřazená pole.^[1] Pro srovnání, obyčejný (tj. Neorientovaný) matroid abstrakty závislost vlastnosti, které jsou společné oběma grafy, které nemusí být nutně režie, a uspořádání vektorů nad pole, které nemusí být nutně objednal.^[2][3]

Všechny orientované matroidy mají podklad matroid. Výsledky na běžných matroidech lze tedy použít na orientované matroidy. Nicméně konverzovat je nepravdivé; některé matroidy se nemohou stát orientovaným matroidem orientace podkladová struktura (např. obvody nebo nezávislé sady).^[4]Rozdíl mezi matroidy a orientovanými matroidy je popsán dále níže.

Matroidy jsou často užitečné v oblastech, jako je teorie dimenzí a algoritmy Z důvodu zahrnutí dalších podrobností o orientované povaha struktury, její užitečnost sahá dále do několika oblastí včetně geometrie a optimalizace.

Pozadí

Za účelem abstrakce pojmu orientace na okrajích grafu k množinám potřebujete schopnost přiřadit „směr“ prvkům množiny. Toho bylo dosaženo pomocí následující definice podepsané sady.

• A podepsaná sada, ${ displaystyle X}$kombinuje sadu objektů ${ displaystyle { podtržení {X}}}$ s oddílem této sady do dvou podmnožin: ${ displaystyle X ^ {+}}$ a ${ displaystyle X ^ {-}}$.

Členové ${ displaystyle X ^ {+}}$ se nazývají pozitivní prvky; Členové ${ displaystyle X ^ {-}}$ jsou negativní prvky.

• Sada ${ displaystyle { podtržení {X}} = X ^ {+} pohár X ^ {-}}$ se nazývá Podpěra, podpora z ${ displaystyle X}$.
• The prázdná podepsaná sada, ${ displaystyle emptyset}$, je definována jako prázdná množina ${ displaystyle { underline { emptyset}}}$ v kombinaci s jeho „oddílem“ do dvou prázdných sad: ${ displaystyle emptyset ^ {+}}$ a ${ displaystyle emptyset ^ {-}}$.
• Podepsaná sada ${ displaystyle Y}$ je naproti z ${ displaystyle X}$, tj., ${ displaystyle Y = -X}$, právě když ${ displaystyle Y ^ {+} = X ^ {-}}$ a ${ displaystyle Y ^ {-} = X ^ {+}}$

Vzhledem k prvku podpory ${ displaystyle x}$, budeme psát ${ displaystyle x}$ pro pozitivní prvek a ${ displaystyle -x}$ pro negativní prvek. Tímto způsobem podepsaná sada právě přidává záporná znaménka k rozlišujícím prvkům. To bude mít smysl jako „směr“, pouze když vezmeme v úvahu orientace větších struktur. Znaménko každého prvku pak zakóduje jeho směr vzhledem k této orientaci.

Axiomatizace

Stejně jako běžné matroidy, několik ekvivalentů soustavy axiomů existovat. (Takové struktury, které mají několik ekvivalentních axiomatizací, se nazývají kryptomorfní.)

Obvodové axiomy

Nechat ${ displaystyle E}$ být libovolnou sadou. Odkazujeme na ${ displaystyle E}$ jako pozemní souprava. Nechat ${ displaystyle { mathcal {C}}}$ být sbírkou podepsané sady, z nichž každý je podporováno podmnožinou ${ displaystyle E}$.Pokud platí následující axiomy pro ${ displaystyle { mathcal {C}}}$, potom ekvivalentně ${ displaystyle { mathcal {C}}}$ je sada podepsané obvodypro orientovaný matroid na ${ displaystyle E}$.

• (C0) ${ displaystyle emptyset notin { mathcal {C}}}$
• (C1) (symetrický) ${ displaystyle { text {Pro všechny}} X v { mathcal {C}}, ~ - ! X v { mathcal {C}}.}$
• (C2) (neporovnatelný) ${ displaystyle { text {Pro všechny}} X, Y in { mathcal {C}}, ~~ { text {if}} { podtržení {X}} subseteq { podtržení {Y}} { text {then}} (X = Y { text {nebo}} X = -Y).}$
• (C3) (slabá eliminace) ${ displaystyle { text {pro všechny}} X, Y v { mathcal {C}}, X neq -Y { text {s an}} e v X ^ {+} cap Y ^ { -} { text {existuje a}} Z v { mathcal {C}} { text {takový, že}}}$
  • ${ displaystyle Z ^ {+} subseteq (X ^ {+} pohár Y ^ {+}) setminus {e } { text {a}}}$
  • ${ displaystyle Z ^ {-} subseteq (X ^ {-} pohár Y ^ {-}) setminus {e }.}$

Vektorové axiomy

The složení podepsaných sad ${ displaystyle X}$ a ${ displaystyle Y}$ je podepsaná sada ${ Displaystyle X Cir Y}$ definován ${ displaystyle { underline {X circ Y}} = { underline {X}} cup { underline {Y}}}$, ${ displaystyle (X circ Y) ^ {+} = X ^ {+} pohár vlevo (Y ^ {+} setminus X ^ {-} vpravo)}$, a ${ displaystyle (X circ Y) ^ {-} = X ^ {-} cup left (Y ^ {-} setminus X ^ {+} right)}$. The vektory orientovaného matroidu jsou skladby obvodů. Vektory ${ displaystyle { mathcal {V}}}$ orientovaného matroidu splňují následující axiomy:

• ${ displaystyle emptyset in { mathcal {V}}}$
• ${ displaystyle { mathcal {V}} = - { mathcal {V}}}$
• pro všechny ${ displaystyle X, Y v { mathcal {V}}}$, ${ displaystyle X circ Y v { mathcal {V}}}$
• pro všechny ${ displaystyle X, Y v { mathcal {V}}}$, ${ displaystyle e v X ^ {+} čepici Y ^ {-}}$a ${ displaystyle f in ({ podtržení {X}} setminus { podtržení {Y}}) pohár ({ podtržení {Y}} setminus { podtržení {X}}) pohár (X ^ { +} cap Y ^ {+}) cup (X ^ {-} cap Y ^ {-})}$ , tady je ${ displaystyle Z v { mathcal {V}}}$, takový, že
  • ${ displaystyle Z ^ {+} podmnožina X ^ {+} pohár Y ^ {+} setminus e}$,
  • ${ displaystyle Z ^ {-} podmnožina X ^ {-} pohár Y ^ {-} setminus e}$, a
  • ${ displaystyle f in { podtržení {Z}}}$.

Chirotopové axiomy

Nechat ${ displaystyle E}$ být jako výše. Pro každé nezáporné celé číslo ${ displaystyle r}$, a chirotope hodnosti ${ displaystyle r}$ je funkce ${ displaystyle chi tlustého střeva E ^ {r} do {- 1,0,1 }}$ který splňuje následující axiomy:

• (B0) (netriviální): ${ displaystyle chi}$ není identicky nula
• (B1) (střídavě): Pro všechny permutace ${ displaystyle sigma}$ a ${ displaystyle x_ {1}, tečky, x_ {r} v E}$, ${ displaystyle chi left (x _ { sigma (1)}, dots, x _ { sigma (r)} right) = operatorname {sgn} ( sigma) chi left (x_ {1} , dots, x_ {r} right)}$, kde ${ displaystyle operatorname {sgn} ( sigma)}$ je podepsat permutace.
• (B2) (výměna): Pro všechny ${ displaystyle x_ {1}, dots, x_ {r}, y_ {1}, dots, y_ {r} in E}$ takhle ${ displaystyle chi (y_ {i}, x_ {2}, tečky, x_ {r}) chi (y_ {1}, tečky, y_ {i-1}, x_ {1}, y_ {i +1}, tečky, y_ {r}) geq 0}$ pro každého ${ displaystyle i}$, pak také máme ${ displaystyle chi left (x_ {1}, dots, x_ {r} right) chi left (y_ {1}, dots, y_ {r} right) geq 0}$.

Termín chirotop je odvozeno z matematické představy chirality, což je koncept vycházející z chemie, kde se používá k rozlišení molekul, které mají stejnou strukturu s výjimkou odrazu.

Rovnocennost

Každý chirotop hodnosti ${ displaystyle r}$ dává vzniknout množině základů matroidu ${ displaystyle E}$ skládající se z těch ${ displaystyle r}$- prvek to podmnožiny ${ displaystyle chi}$ přiřadí nenulovou hodnotu.^[5] Chirotop pak může podepsat obvody tohoto matroidu. Li ${ displaystyle C}$ je tedy obvod popsaného matroidu ${ displaystyle C podmnožina {x_ {1}, tečky, x_ {r}, x_ {r + 1} }}$ kde ${ displaystyle {x_ {1}, tečky, x_ {r} }}$ je základ. Pak ${ displaystyle C}$ lze podepsat pozitivními prvky

${ displaystyle C ^ {+} = {x_ {i}: (- 1) ^ {i} chi (x_ {1}, tečky, x_ {i-1}, x_ {i + 1}, tečky, x_ {r + 1}) = 1 }}$

a negativní prvky doplňkem. Chirotop tedy vede k orientované základny orientovaného matroidu. V tomto smyslu je (B0) neprázdný axiom pro báze a (B2) je vlastnost směny základny.

Příklady

Orientované matroidy jsou často představovány (např.Bachem a Kern) jako abstrakce pro směrované grafy nebo systémy lineárních nerovností. Níže jsou uvedeny explicitní konstrukce.

Směrované grafy

Vzhledem k digraf, definujeme podepsaný obvod ze standardu obvod následující metodou. Podpora podepsaného obvodu ${ displaystyle textstyle { podtržení {X}}}$ je standardní sada hran v minimálním cyklu. Jdeme po cyklu ve směru hodinových ručiček nebo proti směru hodinových ručiček a přiřadíme ty hrany, jejichž orientace souhlasí se směrem, kladným prvkům ${ displaystyle textstyle X ^ {+}}$ a ty hrany, jejichž orientace nesouhlasí se směrem k negativním prvkům ${ displaystyle textstyle X ^ {-}}$. Li ${ displaystyle textstyle { mathcal {C}}}$ je množina všech takových ${ displaystyle textstyle X}$, pak ${ displaystyle textstyle { mathcal {C}}}$ je sada signovaných obvodů orientovaného matroidu na množině okrajů směrovaného grafu.

Směrovaný graf

Pokud vezmeme v úvahu směrovaný graf vpravo, pak vidíme, že existují pouze dva obvody, a to ${ displaystyle textstyle {(1,2), (1,3), (3,2) }}$ a ${ displaystyle textstyle {(3,4), (4,3) }}$. Pak existují pouze čtyři možné obvody se znaménkem, které odpovídají orientaci ve směru a proti směru hodinových ručiček ${ displaystyle textstyle {(1,2), - (1,3), - (3,2) }}$, ${ displaystyle textstyle {- (1,2), (1,3), (3,2) }}$, ${ displaystyle textstyle {(3,4), (4,3) }}$, a ${ displaystyle textstyle {- (3,4), - (4,3) }}$. Tyto čtyři sady tvoří množinu podepsaných obvodů orientovaného matroidu na množině ${ displaystyle textstyle {(1,2), (1,3), (3,2), (3,4), (4,3) }}$.

Lineární algebra

Li ${ displaystyle textový styl E}$ je jakákoli konečná podmnožina ${ displaystyle textstyle mathbb {R} ^ {n}}$, pak sada minimálních lineárně závislých sad tvoří obvodovou sadu matroidu ${ displaystyle textstyle E}$. Rozšířit tuto konstrukci na orientované matroidy pro každý okruh ${ displaystyle textstyle {v_ {1}, tečky, v_ {m} }}$ existuje minimální lineární závislost

${ displaystyle sum _ {i = 1} ^ {m} lambda _ {i} v_ {i} = 0}$

s ${ displaystyle textstyle lambda _ {i} v mathbb {R}}$. Pak podepsaný obvod ${ displaystyle textstyle X = {X ^ {+}, X ^ {-} }}$ má pozitivní prvky ${ displaystyle textstyle X ^ {+} = {v_ {i}: lambda _ {i}> 0 }}$ a negativní prvky ${ displaystyle textstyle X ^ {-} = {v_ {i}: lambda _ {i} <0 }}$. Soubor všech takových ${ displaystyle textstyle X}$ tvoří množinu podepsaných obvodů orientovaného matroidu ${ displaystyle textstyle E}$. Orientované matroidy, které lze realizovat tímto způsobem, se nazývají reprezentativní.

Vzhledem ke stejné sadě vektorů ${ displaystyle E}$můžeme definovat stejně orientovaný matroid s chirotopem ${ displaystyle chi: E ^ {r} rightarrow {- 1,0,1 }}$. Pro všechny ${ displaystyle x_ {1}, tečky, x_ {r} v E}$ nechat

${ displaystyle chi (x_ {1}, tečky, x_ {r}) = operatorname {sgn} ( det (x_ {1}, tečky, x_ {r}))}$

kde pravá strana rovnice je znaménkem určující. Pak ${ displaystyle chi}$ je chirotop stejného orientovaného matroidu na scéně ${ displaystyle E}$.

Uspořádání nadroviny

Skutečné uspořádání nadroviny ${ displaystyle { mathcal {A}} = {H_ {1}, ldots, H_ {n} }}$ je konečná sada hyperplánů v ${ displaystyle mathbb {R} ^ {d}}$, z nichž každý obsahuje původ. Výběrem jedné strany každé nadroviny jako kladné strany získáme uspořádání poloprostorů. Uspořádání polovičního prostoru rozkládá okolní prostor na konečnou sbírku buněk, z nichž každá je definována na které straně každé nadroviny přistává. To znamená, přiřadit každý bod ${ displaystyle x in mathbb {R} ^ {d}}$k podepsané sadě ${ displaystyle X = (X ^ {+}, X ^ {-})}$s ${ displaystyle i v X ^ {+}}$ -li ${ displaystyle x}$ je na pozitivní straně ${ displaystyle H_ {i}}$a ${ displaystyle i v X ^ {-}}$-li ${ displaystyle x}$ je na negativní straně ${ displaystyle H_ {i}}$. Tato kolekce podepsaných sad definuje množinu covektorů orientovaného matroidu, které jsou vektory dvojitě orientovaného matroidu.^[6]

Konvexní mnohostěn

Günter M. Ziegler zavádí orientované matroidy prostřednictvím konvexních polytopů.

Výsledek

Orientovatelnost

Standardní matroid se nazývá orientovatelný pokud jsou jeho obvody podporou podepsaných obvodů nějakého orientovaného matroidu. Je známo, že všechny skutečné reprezentovatelné matroidy jsou orientovatelné. Je také známo, že třída orientovatelných matroidů je uzavřena nezletilí, nicméně seznam zakázané nezletilé pro orientovatelné matroidy je známo, že je nekonečný.^[7] V tomto smyslu jsou orientované matroidy mnohem přísnější formalizace než běžné matroidy.

Dualita

Stejně jako matroidy mají jedinečné dvojí, orientované matroidy mají jedinečné ortogonální dvojí. To znamená, že podkladové matroidy jsou dvojí a že obvody jsou podepsány tak, aby byly ortogonální do každého okruhu. Říká se, že jsou dvě podepsané sady ortogonální pokud je průsečík jejich podpor prázdný nebo pokud omezení jejich kladných prvků na křižovatku a negativních prvků na křižovatku tvoří dvě neidentické a protilehlé sady se znaménky. Existence a jedinečnost duální orientovaného matroidu závisí na skutečnosti, že každý podepsaný obvod je kolmý ke každému podepsanému obvodu.^[8] Abyste pochopili, proč je ortogonalita nezbytná pro jedinečnost, stačí se podívat na výše uvedený příklad digrafu. Víme, že pro planární grafy je duál matroidu obvodu matroid obvodu grafu planární duální. Existuje tedy tolik různě orientovaných matroidů, které jsou dvojí, protože existuje způsob, jak orientovat graf a jeho dvojí.

Chcete-li vidět explicitní konstrukci tohoto jedinečného ortogonálního dvojího orientovaného matroidu, zvažte chirotop orientovaného matroidu ${ displaystyle chi: E ^ {r} rightarrow {- 1,0,1 }}$. Pokud vezmeme v úvahu seznam prvků ${ displaystyle x_ {1}, dots, x_ {k} v E}$ jako cyklickou permutaci pak definujeme ${ displaystyle operatorname {sgn} (x_ {1}, dots, x_ {k})}$ být znamením související permutace. Li ${ displaystyle chi ^ {*}: E ^ {| E | -r} rightarrow {- 1,0,1 }}$ je definován jako

${ displaystyle chi ^ {*} (x_ {1}, tečky, x_ {r}) mapsto chi (x_ {r + 1}, dots, x_ {| E |}) operatorname {sgn} (x_ {1}, dots, x_ {r}, x_ {r + 1}, dots, x_ {| E |}),}$

pak ${ displaystyle chi ^ {*}}$ je chirotop jedinečného ortogonálního duálního matroidu.^[9]

Topologická reprezentace

Toto je příklad pseudolinového uspořádání odlišný z jakéhokoli uspořádání linky.

Ne všechny orientované matroidy jsou reprezentovatelné - to znamená, že ne všechny mají realizace jako bodové konfigurace nebo ekvivalentní uspořádání nadroviny. V určitém smyslu se však všechny orientované matroidy blíží tomu, aby realizace byly uspořádání nad rovinou. Zejména Věta o topologické reprezentaci Folkman – Lawrence uvádí, že jakýkoli orientovaný matroid má realizaci jako uspořádání pseudosfér. A ${ displaystyle d}$-dimenzionální pseudosféra je vložení ${ displaystyle e: S ^ {d} hookrightarrow S ^ {d + 1}}$ takové, že existuje homeomorfismus ${ displaystyle h: S ^ {d + 1} rightarrow S ^ {d + 1}}$ aby ${ displaystyle h circ e}$ vloží ${ displaystyle S ^ {d}}$ jako rovník ${ displaystyle S ^ {d + 1}}$. V tomto smyslu je pseudosféra jen a krotit koule (na rozdíl od divoké koule ). A uspořádání pseudosféry v ${ displaystyle S ^ {d}}$ je sbírka pseudosfér, které se protínají podél pseudosfér. A konečně, věta topologické reprezentace Folkmana Lawrencea uvádí, že každý orientovaný matroid hodnosti ${ displaystyle d + 1}$ lze získat z uspořádání pseudosféry v ${ displaystyle S ^ {d}}$.^[10] Je pojmenován po Jon Folkman a Jim Lawrence, který ji publikoval v roce 1978.

Geometrie

Zonotop, který je Minkowského součtem úseček, je základním modelem pro orientované matroidy. Šestnáct tmavě červených bodů (vpravo) tvoří Minkowského součet čtyř nekonvexních sad (vlevo), z nichž každý se skládá z dvojice červených bodů. Jejich konvexní trupy (stínované růžové) obsahují znaménka plus (+): Pravé znaménko plus je součtem levého znaménka plus.

Teorie orientovaných matroidů ovlivnila vývoj kombinatorická geometrie, zejména teorie konvexní polytopes, zonotopy, a konfigurací vektorů (uspořádání hyperplánů ).^[11] Mnoho výsledků—Carathéodoryova věta, Hellyho věta, Radonova věta, Hahnova – Banachova věta, Kerin – Milmanova věta, Farkasovo lema —Může být formulován pomocí vhodně orientovaných matroidů.^[12]

Optimalizace

V konvexní geometrii je simplexní algoritmus pro lineární programování interpretován jako trasování cesty podél vrcholů konvexního mnohostěnu. Teorie orientované matroidy studuje kombinatorické invarianty, které jsou odhaleny ve znakových vzorcích matic, které se objevují jako výměnné báze otočných algoritmů.

Vývoj systému axiomu pro orientované matroidy byl zahájen R. Tyrrell Rockafellar popsat znaménkové vzory matic vznikající otočnými operacemi Dantzigova simplexního algoritmu; Rockafellar byl inspirován Albert W. Tucker Studie takových znakových vzorů v "Tuckerových obrazech".^[13]

Teorie orientovaných matroidů vedla k průlomům v oblasti kombinatorická optimalizace. v lineární programování, to byl jazyk, ve kterém Robert G. Bland formuloval svůj otočné pravidlo, kterým simplexní algoritmus vyhýbá se cyklům. Podobně to použili Terlaky a Zhang k prokázání toho, že jejich křížové algoritmy mít konečné ukončení pro lineární programování problémy. Podobné výsledky byly provedeny u konvexních kvadratické programování od Todda a Terlaky.^[14] Bylo aplikováno na lineární-zlomkové programování,^[15] kvadratické programování problémy a problémy lineární komplementarity.^[16][17][18]

Mimo kombinatorická optimalizace, OM teorie také se objeví v konvexní minimalizace v Rockafellarově teorii „monotropního programování“ a souvisejících pojmech „opevněného původu“.^[19] Podobně, matroid teorie ovlivnila vývoj kombinatorických algoritmů, zejména chamtivý algoritmus.^[20] Obecněji, a greedoid je užitečné pro studium konečného ukončení algoritmů.

Reference

Další čtení

Knihy

• Bachem, Achim; Kern, Walter (1992). Dualita lineárního programování: Úvod do orientovaných matroidů. Universitext. Springer-Verlag. doi:10.1007/978-3-642-58152-6. ISBN  978-3-540-55417-2. PAN  1230380.
• Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Orientované matroidy. Encyklopedie matematiky a její aplikace. 46 (2. vyd.). Cambridge University Press. ISBN  978-0-521-77750-6. Zbl  0944.52006.
• Bokowski, Jürgen (2006). Výpočetně orientované matroidy. Třídy ekvivalence matic v přirozeném rámci. Cambridge University Press. ISBN  978-0-521-84930-2. Zbl  1120.52011.
• Lawler, Eugene (2001). Kombinatorická optimalizace: Sítě a matroidy. Doveru. ISBN  978-0-486-41453-9. Zbl  1058.90057.
• Evar D. Nering a Albert W. Tucker, 1993, Lineární programy a související problémy, Academic Press. (základní)
• Rockafellar, R. Tyrrell (1984). Toky v síti a monotropní optimalizace. Wiley-Interscience. publikováno Athena Scientific of Dimitri Bertsekas, 1998.
• Ziegler, Günter M. (1994). Přednášky na Polytopech. New York: Springer-Verlag.
• Richter-Gebert, Jürgen; Ziegler, Günter M. (1997). "Orientované matroidy". v Goodman, Jacob E.; O'Rourke, Joseph (eds.). Příručka diskrétní a výpočetní geometrie. Boca Raton: CRC Press. str.111–132.

Články

• A. Bachem, A. Wanka, Věty o oddělení pro orientované matroidy, Diskrétní matematika. 70 (1988) 303—310.
• Robert G. Bland Nová konečná otočná pravidla pro simplexní metodu, Matematika. Oper. Res. 2 (1977) 103–107.
• Folkman, Jon; Lawrence, Jim (Říjen 1978). "Orientované matroidy". J. Combin. Theory Ser. B. 25 (2): 199–236. doi:10.1016/0095-8956(78)90039-4.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Křížové metody: nový pohled na pivotní algoritmy". Matematické programování, řada B.. 79 (1–3). Amsterdam: North-Holland Publishing Co. str. 369–395. doi:10.1007 / BF02614325. PAN  1464775.
• Fukuda, Komei; Namiki, Makoto (březen 1994). "O extremálním chování Murtyho metody nejmenšího indexu". Matematické programování. 64 (1): 365–370. doi:10.1007 / BF01582581. PAN  1286455.
• Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). „Metoda konečného křížení pro hyperbolické programování“. Evropský žurnál operačního výzkumu. 114 (1): 198–214. CiteSeerX  10.1.1.36.7090. doi:10.1016 / S0377-2217 (98) 00049-6. ISSN  0377-2217.
• R. Tyrrell Rockafellar. Elementární vektory podprostoru o ${ displaystyle R ^ {n}}$, v Kombinatorická matematika a její aplikaceR. C. Bose a T. A. Dowling (eds.), Univ. of North Carolina Press, 1969, 104-127.
• Roos, C. (1990). "Exponenciální příklad Terlakyho otočného pravidla pro metodu criss-cross simplex". Matematické programování. Řada A. 46 (1): 79–84. doi:10.1007 / BF01585729. PAN  1045573.
• Terlaky, T. (1985). "Konvergentní křížová metoda". Optimalizace: Žurnál matematického programování a operačního výzkumu. 16 (5): 683–690. doi:10.1080/02331938508843067. ISSN  0233-1934. PAN  0798939.
• Terlaky, Tamás (1987). „Metoda konečného křížení pro orientované matroidy“. Journal of Combinatorial Theory. Řada B. 42 (3): 319–327. doi:10.1016/0095-8956(87)90049-9. ISSN  0095-8956. PAN  0888684.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot pravidla pro lineární programování: Průzkum o nedávném teoretickém vývoji". Annals of Operations Research. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658. doi:10.1007 / BF02096264. ISSN  0254-5330. PAN  1260019.
• Michael J. Todd, lineární a kvadratické programování v orientovaných matroidech, J. Combin. Theory Ser. B 39 (1985) 105—133.
• Wang, Zhe Min (1987). "Bezplatný algoritmus konečné konformní eliminace nad orientovaným programováním matroidů". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Řada B. 8 (1): 120–125. ISSN  0252-9599. PAN  0886756.

Na webu

• Ziegler, Günter (1998). „Orientované matroidy dnes“. Electronic Journal of Combinatorics.
• Malkevitch, Joseph. „Orientované matroidy: síla sjednocení“. Sloupec funkcí. Americká matematická společnost. Citováno 2009-09-14.

externí odkazy

• Komei Fukuda (ETH Zentrum, Curych) s publikace počítaje v to Orientované programování matroidů (1982 Ph.D. práce)
• Tamás Terlaky (Lehigh University) s publikace