Orienterad matroid

Oriented-matroid teori tillåter en kombinatorisk ansats till max-flow min-cut theorem . Ett nätverk med flödesvärdet lika med kapaciteten för en st cut

En orienterad matroid är en matematisk struktur som abstraherar egenskaperna hos riktade grafer , vektorarrangemang över ordnade fält och hyperplanarrangemang över ordnade fält . I jämförelse abstraherar en vanlig (dvs icke-orienterad) matroid beroendeegenskaperna som är vanliga både för grafer , som inte nödvändigtvis är riktade , och för arrangemang av vektorer över fält , som inte nödvändigtvis är ordnade .

Alla orienterade matroider har en underliggande matroid . Således kan resultat på vanliga matroider appliceras på orienterade matroider. Men det omvända är falskt; vissa matroider kan inte bli en orienterad matroid genom att orientera en underliggande struktur (t.ex. kretsar eller oberoende uppsättningar). Skillnaden mellan matroider och orienterade matroider diskuteras vidare nedan.

Matroider är ofta användbara inom områden som dimensionsteori och algoritmer . På grund av en orienterad matroids inkludering av ytterligare detaljer om en strukturs orienterade karaktär, sträcker sig dess användbarhet ytterligare till flera områden inklusive geometri och optimering .

Bakgrund

Huvudartikel: Signerad uppsättning

För att abstrahera begreppet orientering på kanterna av en graf till uppsättningar, behöver man förmågan att tilldela "riktning" till elementen i en uppsättning. Sättet detta uppnåddes är med följande definition av signerade uppsättningar .

• En signerad uppsättning , $X$ , kombinerar en uppsättning objekt, ${\underline {X}}$ , med en partition av den uppsättningen i två delmängder: $X^{+ }$ och $X^{-}$ .

Medlemmarna av $X^{+}$ kallas de positiva elementen ; medlemmar av $X^{-}$ är de negativa elementen .

• Mängden ${\underline {X}}=X^{+}\cup X^{-}$ kallas stödet för $X$ .
• Den tomma signerade uppsättningen , $\emptyset$ , definieras som den tomma uppsättningen ${\underline {\emptyset }}$ kombinerad med en "partition" av den i två tomma uppsättningar: ${\ displaystyle \emptyset ^{+}}$ och $\emptyset ^{-}$ .
• Den signerade uppsättningen $Y$ är motsatsen till $X$ , dvs $Y=-X$ , om och endast om $Y^{ +}=X^{-}$ och $Y^{-}=X^{+}$

Givet ett element av stödet $x$ kommer vi att skriva $x$ för ett positivt element och $-x$ för ett negativt element. På detta sätt lägger en signerad uppsättning bara till negativa tecken till framstående element. Detta kommer att vara vettigt som en "riktning" endast när vi överväger orienteringar av större strukturer. Sedan kommer tecknet för varje element att koda dess riktning i förhållande till denna orientering.

Axiomatiseringar

Se även: Matroid § Baser och kretsar , Axiomatiskt system och Kryptomorfism

Liksom vanliga matroider finns flera ekvivalenta system av axiom . (Sådana strukturer som har flera ekvivalenta axiomatiseringar kallas kryptomorfa .)

Kretsens axiom

Låt $E$ vara vilken mängd som helst. Vi hänvisar till $E$ som grundsatsen . Låt ${\mathcal {C}}$ vara en samling av signerade uppsättningar , som var och en stöds av en delmängd av $E$ . Om följande axiom gäller för ${\displaystyle {\mathcal {C}}} , så är$${\mathcal {C}}$ motsvarande uppsättningen av signerade kretsar för en orienterad matroid på $E$ .

• (C0) $\emptyset \notin {\mathcal {C}}$
• (C1) (symmetrisk) ${\text{ För alla }}X\in {\mathcal {C}},~-\!X\in {\mathcal {C}}.$
• (C2) (ojämförbar) ${\text{ För alla }}X,Y\in {\mathcal {C}},~~{\text{ if }}{\underline {X}}\subseteq {\underline {Y}}{ \text{ sedan }}(X=Y{\text{ eller }}X=-Y).$
• (C3) (svag eliminering) ${\text{ För alla }}X,Y \i {\mathcal {C}},X\neq -Y{\text{ med ett }}e\i X^{+}\cap Y^{-}{\text{ finns ett }}Z\in {\mathcal {C}}{\text{ så att }}$
  • $Z^{+}\subseteq (X^{+}\cup Y^{+})\setminus \{e\}{\text{ och }}$
  • $Z^{-}\subseteq (X^{-}\cup Y^{-})\setminus \{e\}.$

Vektor Axiom

Sammansättningen av signerade uppsättningar $X$ och $displaystyle Y}$${\displaystyle {\ understryka {X\circ Y}}={\underline {X}}\cup {\underline {Y}}} ,$ är den signerade uppsättningen $X\circ Y$ definierad av _ ( $\displaystyle (X\ circ Y)^{+}=X^{+}\cup \left(Y^{+}\setminus X^{-}\right)} ,$ och $(X\circ Y)^{-}=X^{-}\cup \left(Y^{-}\setminus X^{+}\right)$ . Vektorerna för en orienterad matroid är sammansättningar av kretsar. Vektorerna ${\mathcal {V}}$ för en orienterad matroid uppfyller följande axiom:

• $\emptyset \in {\mathcal {V}}$
• ${\mathcal {V}}=-{\mathcal {V}}$
• för alla ${\displaystyle X,Y\in {\mathcal {V}}} ,$ X $\displaystyle X\circ Y\in {\mathcal {V}}}$
• för alla $X,Y\in {\mathcal {V}}$ , $e\in X^{+}\cap Y^{-}$ och $f\in ({\underline {X}}\setminus {\underline {Y}})\cup ({\underline {Y}}\setminus {\underline {X}})\cup (X^{+}\cap Y^{+})\cup (X^{ -}\cap Y^{-})$ , det finns en ${\displaystyle Z\in {\mathcal {V}}} ,$ så att
  • $Z^{+}\subset X^{+}\cup Y^{+}\setminus e$ ,
  • ${\displaystyle Z^{-}\subset X^{-}\cup Y^{-}\setminus e} ,$ och
  • $f\in {\underline {Z}}$ .

Chirotopaxiom

Låt $E$ vara som ovan. För varje icke-negativt heltal ${\displaystyle r} är$ en chirotop av rang $r$ en funktion $\chi \colon E^{r} \to \{-1,0,1\}$ som uppfyller följande axiom:

• (B0) (icke-trivial) : $\chi$ är inte identiskt noll
• (B1) (alternerande) : För alla permutationer $\sigma$ och $x_{1},\dots ,x_{r}\in E$ , ${\displaystyle \chi \left(x_{\sigma (1)},\dots ,x_ {\sigma (r)}\right)=\operatörsnamn {sgn} (\sigma )\chi \left(x_{1},\dots ,x_{r}\right)} , där$ sgn $\ displaystyle \operatorname {sgn} (\sigma )}$ är tecknet på permutationen.
• (B2) (utbyte) : För alla $x_{1},\dots ,x_{r},y_{1},\dots , y_{r}\in E$ så att ${ \displaystyle \chi (y_{i},x_{2},\dots ,x_{r})\chi (y_{1},\dots ,y_{i-1},x_{1},y_{i+ 1},\dots ,y_{r})\geq 0}$ för varje $i$ , då har vi också ${ \displaystyle \chi \left(x_{1},\dots ,x_{r}\right)\chi \left(y_{1},\dots ,y_{r}\right)\geq 0}$ .

Termen chirotope härrör från den matematiska föreställningen om kiralitet , som är ett begrepp som är abstraherat från kemi , där det används för att skilja molekyler som har samma struktur förutom en reflektion.

Likvärdighet

Varje kirotop av rang $r$ ger upphov till en uppsättning baser av en matroid på $E$ bestående av de $r$ -elementsubset som $\chi$ tilldelar en icke-noll värde. Chirotopen kan sedan signera kretsarna för den matroiden. Om $C$ är en krets av den beskrivna matroiden, då $C\subset \{x_{1},\dots ,x_{ r},x_{r+1}\}$ där $\{x_{1},\dots ,x_{r}\}$ är en grund. Då $C$ signeras med positiva element

$C^{+}=\{ x_{i}:(-1)^{i}\chi (x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{r+1})=1 \}$

och negativa element komplementet. Sålunda ger en kirotop upphov till de orienterade baserna av en orienterad matroid. I denna mening är (B0) det icke-tomma axiomet för baser och (B2) är basutbytesegenskapen.

Exempel

Orienterade matroider introduceras ofta (t.ex. Bachem och Kern) som en abstraktion för riktade grafer eller system av linjära ojämlikheter. Nedan är de explicita konstruktionerna.

Riktade grafer

Huvudartikel: Riktad graf

Se även: Flödesnätverk

Med en digraf definierar vi en signerad krets från standardkretsen i grafen med följande metod. Stödet för den signerade kretsen $\textstyle {\underline {X}}$ är standarduppsättningen av kanter i en minimal cykel. Vi går längs cykeln i medurs eller moturs riktning och tilldelar de kanter vars orientering överensstämmer med riktningen till de positiva elementen $\textstyle X^{+}$ och de kanter vars orientering inte överensstämmer med riktningen till de negativa elementen $\textstyle X^{-}$ . Om $\textstyle {\mathcal {C}}$ är mängden av alla sådana $\textstyle X$ , så är $\textstyle {\mathcal {C}}$ mängden tecken kretsar av en orienterad matroid på uppsättningen av kanter av den riktade grafen.

En riktad graf

Om vi ​​betraktar den riktade grafen till höger, så kan vi se att det bara finns två kretsar, nämligen $\textstyle \{(1 ,2),(1,3),(3,2)\}$ och $\textstyle \{(3,4),(4,3) \}$ . Då finns det bara fyra möjliga teckenkretsar som motsvarar medurs och moturs orientering, nämligen $\textstyle \{(1,2), -(1,3),-(3,2)\}$ , $\textstyle \{-(1,2) ,(1,3),(3,2)\}$ , $\textstyle \{(3,4),(4,3)\}$ , och $\textstyle \{-(3,4),-(4,3)\}$ . Dessa fyra uppsättningar bildar uppsättningen av signerade kretsar för en orienterad matroid på uppsättningen { $\displaystyle \textstil \{(1,2),(1,3),(3,2),(3,4),(4,3)\}}$ .

Linjär algebra

Se även: Matroid § Matroider från linjär algebra

Om $\textstyle E$ är vilken ändlig delmängd som helst av ${\displaystyle \textstyle \mathbb {R} ^{n}} ,$ så bildar mängden av minimala linjärt beroende mängder kretsmängden för en matroid på ${ \displaystyle \textstyle E}$ . För att utöka denna konstruktion till orienterade matroider finns det ett minimalt linjärt beroende för varje krets $\textstyle \{v_{1},\dots ,v_{m}\}$

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

med $\textstyle \lambda _{i}\in \mathbb {R}$ . Då har den signerade kretsen $\textstyle X=\{X^{+},X^{-}\}$ positiva element $\textstyle X^{+}=\{v_{i}:\lambda _{i}>0\}$ och negativa element $\textstyle X^ {-}=\{v_{i}:\lambda _{i}<0\}$ . Uppsättningen av alla sådana $\textstyle X$ bildar uppsättningen av signerade kretsar för en orienterad matroid på $\textstyle E$ . Orienterade matroider som kan realiseras på detta sätt kallas representable .

Givet samma uppsättning vektorer $E$ , kan vi definiera samma orienterade matroid med en chirotop $\chi :E^{r}\rightarrow \{ -1,0,1\}$ . För alla $x_{1},\dots ,x_{r}\in E$ låt

$\chi (x_{1},\dots ,x_{r})=\operatörsnamn {sgn} (\det(x_{1},\dots,x_{r}))$

där den högra sidan av ekvationen är tecknet för determinanten . Då $\chi$ kirotopen för samma orienterade matroid på mängden $E$ .

Hyperplanarrangemang

Huvudartikel: Arrangemang av hyperplan

Ett riktigt hyperplanarrangemang ${\mathcal {A}}=\{H_{1},\ldots ,H_{n}\}$ är en ändlig uppsättning hyperplan i $\mathbb {R} ^{d}$ , var och en innehåller ursprunget. Genom att välja en sida av varje hyperplan som den positiva sidan får vi ett arrangemang av halvrum. Ett halvutrymmesarrangemang bryter ner det omgivande rummet till en ändlig samling celler, var och en definierad av vilken sida av varje hyperplan den landar på. Det vill säga tilldela varje punkt $x\in \mathbb {R} ^{d}$ till den signerade uppsättningen $X=(X^{+} ,X^{-})$ med $i\in X^{+}$ om $x$ är på den positiva sidan av $H_{i}$ och $i\in X^{-}$ om $x$ är på den negativa sidan av $H_{i}$ . Denna samling av signerade uppsättningar definierar uppsättningen av kovektorer för den orienterade matroiden, som är vektorerna för den dubbelorienterade matroiden.

Konvex polytop

Huvudartikel: Konvex polytop

Günter M. Ziegler introducerar orienterade matroider via konvexa polytoper.

Resultat

Orienterbarhet

En standardmatroid kallas orienterbar om dess kretsar är stöd för signerade kretsar av någon orienterad matroid. Det är känt att alla verkliga representativa matroider är orienterbara. Det är också känt att klassen av orienterbara matroider är stängd för att ta emot minderåriga , men listan över förbjudna minderåriga för orienterbara matroider är känd för att vara oändlig. I denna mening är orienterade matroider en mycket strängare formalisering än vanliga matroider.

Dualitet

Se även: Matroid § Dualitet

Ungefär som matroider har unika dubbla , orienterade matroider har unika ortogonala dubbla. Vad detta betyder är att de underliggande matroiderna är dubbla och att samkretsarna är signerade så att de är ortogonala mot varje krets. Två tecken med tecken sägs vara ortogonala om skärningen av deras stöd är tom eller om begränsningen av deras positiva element till skärningspunkten och negativa element till korsningen bildar två icke-identiska och icke motsatta tecken med tecken. Existensen och unikheten hos den dubbelorienterade matroiden beror på det faktum att varje signerad krets är ortogonal mot varje signerad samkrets. För att se varför ortogonalitet är nödvändigt för unikhet behöver man bara titta på digrafexemplet ovan. Vi vet att för plana grafer, att dualen av kretsmatroiden är kretsmatroiden av grafens plana dual . Det finns alltså lika många olika orienterade matroider som är dubbla som det finns sätt att orientera en graf och dess dubbla.

För att se den explicita konstruktionen av denna unika ortogonala dubbelorienterade matroid, betrakta en orienterad matroids chirotop $\chi :E^{r}\rightarrow \{-1,0, 1\}$ . Om vi ​​betraktar en lista med element av $x_{1},\dots ,x_{k}\in E$ som en cyklisk permutation så definierar vi $\operatorname {sgn} (x_{1},\dots ,x_{k})$ för att vara tecknet på den associerade permutationen. Om $\chi ^{*}:E^{|E|-r}\rightarrow \{-1,0,1\}$ definieras som

$\chi ^{*}(x_{1},\dots ,x_{r})\mapsto \chi (x_{r+1},\dots ,x_{|E|})\operatörsnamn {sgn} (x_{1},\dots ,x_{r},x_{r+1},\dots ,x_{|E|}),$

då är $\chi ^{*}$ chirotopen för den unika ortogonala dubbelorienterade matroiden.

Topologisk representation

Detta är ett exempel på ett pseudolinarrangemang som skiljer sig från alla linjearrangemang.

Inte alla orienterade matroider är representerbara – det vill säga, alla har inte realiseringar som punktkonfigurationer, eller på motsvarande sätt hyperplanarrangemang. Men i någon mening kommer alla orienterade matroider nära att ha insikter om hyperplanarrangemang. I synnerhet Folkman-Lawrences topologiska representationsteorem att varje orienterad matroid har en realisering som ett arrangemang av pseudosfärer . En $d$ -dimensionell pseudosfär är en inbäddning av $e:S^{d}\hookrightarrow S^{d+1}$ så att det finns en homeomorfism $h:S^{d+1}\högerpil S^{d+1}$ så att $h\circ e$ bäddar in ${\ displaystyle S^{d}}$ som en ekvator av $S^{d+1}$ . I denna mening är en pseudosfär bara en tam sfär (i motsats till vilda sfärer ). Ett pseudosfärarrangemang i $S^{d}$ är en samling pseudosfärer som skär varandra längs pseudosfärer. Slutligen säger Folkman Lawrence topologiska representationssats att varje orienterad matroid av rang $d+1$ kan erhållas från ett pseudosfärarrangemang i $S^{d}$ . Den är uppkallad efter Jon Folkman och Jim Lawrence, som publicerade den 1978.

Geometri

En zonotop, som är en Minkowski summa av linjesegment, är en grundläggande modell för orienterade matroider. De sexton mörkröda punkterna (till höger) bildar Minkowskisumman av de fyra icke-konvexa uppsättningarna (till vänster), som var och en består av ett par röda punkter. Deras konvexa skrov (rosa skuggade) innehåller plustecken (+): Det högra plustecknet är summan av de vänstra plustecknen.

Huvudartikel: Kombinatorisk geometri

Se även: Konvex polytop och Zonotop

Teorin om orienterade matroider har påverkat utvecklingen av kombinatorisk geometri , särskilt teorin om konvexa polytoper , zonotoper och konfigurationer av vektorer ( arrangemang av hyperplan ). Många resultat — Carathéodorys sats , Hellys sats , Radons sats , Hahn -Banachs sats , Krein -Milmans sats , Farkas lemma — kan formuleras med hjälp av lämpliga orienterade matroider.

Optimering

I konvex geometri tolkas simplexalgoritmen för linjär programmering som att spåra en bana längs hörnen på en konvex polyeder. Orienterad matroideori studerar de kombinatoriska invarianter som avslöjas i teckenmönster för matriserna som framträder som pivoterande algoritmer som utbyter baser.

Se även: Linjär programmering , Kvadratisk programmering och Kors-kors-algoritm

Utvecklingen av ett axiomsystem för orienterade matroider initierades av R. Tyrrell Rockafellar för att beskriva teckenmönster för matriserna som uppstår genom svängningsoperationerna i Dantzigs simplexalgoritm; Rockafellar inspirerades av Albert W. Tuckers studier av sådana teckenmönster i "Tucker-tablåer".

Teorin om orienterade matroider har lett till genombrott inom kombinatorisk optimering . Inom linjär programmering var det språket där Robert G. Bland formulerade sin svängningsregel , med vilken simplexalgoritmen undviker cykler. På liknande sätt användes den av Terlaky och Zhang för att bevisa att deras kors och tvärs algoritmer har ändlig terminering för linjära programmeringsproblem . Liknande resultat gjordes i konvex kvadratisk programmering av Todd och Terlaky. Det har tillämpats på linjär-fraktionell programmering , kvadratiska programmeringsproblem och linjära komplementaritetsproblem .

Utanför kombinatorisk optimering förekommer OM-teorin också i konvex minimering i Rockafellars teori om "monotropic programmering" och relaterade föreställningar om "befäst härkomst". På liknande sätt matroidteori påverkat utvecklingen av kombinatoriska algoritmer, särskilt den giriga algoritmen . Mer generellt är en greedoid användbar för att studera den ändliga avslutningen av algoritmer.

Vidare läsning

Böcker

•    Bachem, Achim; Kern, Walter (1992). Linjär programmeringsdualitet: en introduktion till orienterade matroider . Universitext. Springer-Verlag. doi : 10.1007/978-3-642-58152-6 . ISBN 978-3-540-55417-2 . MR 1230380 .
•    Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). Oriented Matroids . Encyclopedia of Mathematics och dess tillämpningar. Vol. 46 (andra upplagan). Cambridge University Press . ISBN 978-0-521-77750-6 . Zbl 0944.52006 .
•    Bokowski, Jürgen (2006). Beräkningsorienterade matroider. Ekvivalensklasser av matriser inom en naturlig ram . Cambridge University Press . ISBN 978-0-521-84930-2 . Zbl 1120.52011 .
•    Lawler, Eugene (2001). Kombinatorisk optimering: nätverk och matroider . Dover. ISBN 978-0-486-41453-9 . Zbl 1058.90057 .
• Evar D. Nering och Albert W. Tucker , 1993, Linjära program och relaterade problem , Academic Press. (elementärt)
• Rockafellar, R. Tyrrell (1984). Nätverksflöden och monotropisk optimering . Wiley-Interscience. återutgiven av Athena Scientific av Dimitri Bertsekas , 1998.
• Ziegler, Günter M. (1994). Föreläsningar om polytoper . New York: Springer-Verlag.
•   Richter-Gebert, Jürgen; Ziegler, Günter M. (1997). "Oriented Matroids". I Goodman, Jacob E .; O'Rourke, Joseph (red.). Handbok för diskret och beräkningsgeometri . Boca Raton: CRC Press. s. 111–132 . ISBN 9780849385247 .

Artiklar

• A. Bachem, A. Wanka, Separationssatser för orienterade matroider, Diskret matematik. 70 (1988) 303—310.
• Robert G. Bland , New finita pivoting rules for the simplex method, Math. Oper. Res. 2 (1977) 103-107.
• Folkman, Jon ; Lawrence, Jim (oktober 1978). "Oriented Matroids" . J. Combin. Teori 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 (red.). "Cross-cross-metoder: En ny syn på pivotalgoritmer" (PDF) . Matematisk programmering, serie B . Amsterdam: North-Holland Publishing Co. 79 (1–3): 369–395. doi : 10.1007/BF02614325 . MR 1464775 . S2CID 2794181 .
•    Fukuda, Komei ; Namiki, Makoto (mars 1994). "Om extrema beteenden av Murtys minsta index-metod". Matematisk programmering . 64 (1): 365–370. doi : 10.1007/BF01582581 . MR 1286455 . S2CID 21476636 .
•    Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "Den finita kors och tvärs-metoden för hyperbolisk programmering" . European Journal of Operational Research . 114 (1): 198–214. CiteSeerX 10.1.1.36.7090 . doi : 10.1016/S0377-2217(98)00049-6 . ISSN 0377-2217 .
• R. Tyrrell Rockafellar . De elementära vektorerna för ett delrum av $R^{n}$ , i Combinatorial Mathematics and its Applications , RC Bose och TA Dowling (red.), Univ. av North Carolina Press, 1969, 104-127.
•    Roos, C. (1990). "Ett exponentiellt exempel på Terlakys svängningsregel för den kors och tvärs simplexmetoden". Matematisk programmering . Serie A. 46 (1): 79–84. doi : 10.1007/BF01585729 . MR 1045573 . S2CID 33463483 .
•    Terlaky, T. (1985). "En konvergent kors och tvärs metod". Optimering: A Journal of Mathematical Programming and Operations Research . 16 (5): 683–690. doi : 10.1080/02331938508843067 . ISSN 0233-1934 . MR 0798939 .
•    Terlaky, Tamás (1987). "En finit kors och tvärs metod för orienterade matroider" . Journal of Combinatorial Theory . Serie B. 42 (3): 319–327. doi : 10.1016/0095-8956(87)90049-9 . ISSN 0095-8956 . MR 0888684 .
•      Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivotregler för linjär programmering: En undersökning om den senaste teoretiska utvecklingen". Annals of Operations Research . 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658 . doi : 10.1007/BF02096264 . ISSN 0254-5330 . MR 1260019 . S2CID 6058077 .
• Michael J. Todd, Linjär och kvadratisk programmering i orienterade matroider, J. Combin. Teori Ser. B 39 (1985) 105—133.
•    Wang, Zhe Min (1987). "En finit konform-elimineringsfri algoritm över orienterad matroidprogrammering". Kinesiska annaler av matematik (Shuxue Niankan B Ji) . Serie B. 8 (1): 120–125. ISSN 0252-9599 . MR 0886756 .

På webben

• Ziegler, Günter (1998). "Oriented Matroids Today" . The Electronic Journal of Combinatorics : DS4: 10 september–1998. doi : 10.37236/25 .
• Malkevitch, Joseph. "Oriented Matroids: The Power of Unification" . Funktionskolumn . American Mathematical Society . Hämtad 2009-09-14 .

externa länkar

• Komei Fukuda (ETH Zentrum, Zürich) med publikationer inklusive Oriented matroid programmering (1982 Ph.D.-avhandling)
• Tamás Terlaky (Lehigh University) med publikationer