Tartalomjegyz´ ek Bevezet´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Jel¨ ol´ esek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
??
1. Saj´ at´ ert´ ekek a kombinatorikus optimaliz´ al´ asban . . . . .
??
1. 2. 3. 4.
Algebrai seg´edt´etelek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . K´et “klasszikus” saj´at´ert´ekkorl´ at . . . . . . . . . . . . . . . . . . . . . Neumann ´es Ky Fan t´etele . . . . . . . . . . . . . . . . . . . . . . . . . . . . Part´ıci´ os probl´em´ ak ´es a ϑ-f¨ uggv´eny . . . . . . . . . . . . . . . . . .
?? ?? ?? ??
2. Dualit´ ast´ etelek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
??
5. 6. 7. 8. 9.
A Farkas-lemma ´es v´altozatai . . . . . . . . . . . . . . . . . . . . . . . . . A Farkas–Weyl–Minkowski-t´etel . . . . . . . . . . . . . . . . . . . . . . Line´aris ´es k´ upline´aris dualit´ ast´etelek . . . . . . . . . . . . . . . . . Egy regularit´asi krit´erium . . . . . . . . . . . . . . . . . . . . . . . . . . . . Szemidefinit programok. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
?? ?? ?? ?? ??
3. Szemidefinit korl´ atok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
??
10. 11. 12. 13.
Maxim´ alis v´ag´ as, gr´ af kett´ev´ag´as . . . . . . . . . . . . . . . . . . . . . A szendvicst´etel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Approxim´aci´ os algoritmusok. . . . . . . . . . . . . . . . . . . . . . . . . . A Lov´asz–Schrijver-m´ odszer . . . . . . . . . . . . . . . . . . . . . . . . . .
1
?? ?? ?? ??
F¨ uggel´ ekek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A. B. C. D.
??
A Minkowski–Klee-t´etel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A PSD lapjair´ol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Wolkowicz–Zhao-korl´ at . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Ramana-du´ al . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
?? ?? ?? ??
Irodalomjegyz´ ek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
T´ argymutat´ o................................................
??
2
Bevezet´ es Mit tudunk mondani egy gr´ afr´ol, ha csak bizonyos hozz´ arendelt m´ atrixok saj´at´ert´ekeit ismerj¨ uk? Vegy¨ uk p´eld´ aul a gr´ af adjacencia m´ atrix´at, mennyit ´ arul el ennek spektruma a gr´ afr´ol? Hogy mindent nem, azt p´eld´ aul a K1 ∪ C4 ´es a K1,4 gr´ afok bizony´ıtj´ak, melyek saj´at´ert´ekei ugyan megegyeznek, a gr´ afok m´egsem izomorfak. M´egis sz´ amtalan eredm´eny mutatja ([15], [16]), hogy a spektrumban b˝ os´eges inform´ aci´o rejlik a gr´ afr´ol. A kombinatorikus optimaliz´ al´asban sz´ amos olyan feladattal tal´alkozunk, melynek megold´ asa bizony´ıtottan neh´ez. P´eld´ aul: sz´ am´ıtsuk ki egy adott gr´ af kromatikus sz´ am´ at! A probl´ema NP-teljes, ´ıgy val´osz´ın˝ uleg nem oldhat´ o meg polinom id˝ oben. S hogy m´egis mondhassunk valamit, megpr´ob´ aljuk k¨onnyen sz´ am´ıthat´ o, sz˝ uk korl´ atok k¨oz´e szor´ıtani a keresett mennyis´eget. A Brooks-t´etel szerint ([32]) b´ armely gr´ afra χ(G) ≤ 1 + dmax (χ(G) a kromatikus sz´ amot, dmax a maxim´alis foksz´ amot jel¨oli), ´es ¨ osszef¨ ugg˝ o gr´ af eset´en pontosan akkor van egyenl˝ os´eg, ha G klikk, vagy p´ aratlan k¨or. Ez egy k¨onnyen sz´ am´ıthat´ o korl´ at, polinom id˝ oben realiz´ alhat´ o (teh´ at gyorsan ki tudjuk sz´ınezni a gr´ afot 1 + dmax sz´ınnel), m´egsem tekinthet˝ o igaz´ an j´o korl´ atnak, hiszen ´ert´eke eg´eszen messze lehet χ(G)t˝ol (pl. csillag), ´es (¨ osszef¨ ugg˝ o gr´ afokra) mind¨ossze k´et esetben ad pontos eredm´enyt. Foglaljuk ¨ ossze, hogy milyen is lenne egy ide´ alis (fels˝o) korl´ at. 1. Gyorsan sz´ am´ıthat´ o, s˝ ot 2. gyorsan realiz´ alhat´ o, 3. nem becs¨ uli t´ ulzottan fel¨ ul a keresett mennyis´eget, 4. melyet j´ol k¨or¨ ulhat´ arolhat´ o, t´ag gr´ afoszt´alyokra meg is ad. A jegyzetben a gr´ afokhoz rendelt m´ atrixok spektrum´ ab´ ol nyerhet˝ o korl´atokat vizsg´alunk meg ebb˝ ol a szempontb´ ol. Minden eddig ismert korl´ atn´ al ide´ alisabbnak bizonyulnak, k¨ ul¨ on¨ osen part´ıci´os probl´em´ ak eset´eben. Az els˝ o saj´at´ert´ek-korl´ atot Wilf adta 1967-ben Brooks t´etel´et bizony´ıtva 1 + dmax helyett az ´elesebb 1 + αmax korl´ attal. (αmax a gr´ af adjacencia m´ atrix´anak legnagyobb saj´at´ert´ek´et jel¨oli.) 1970-ben Hoffman a kro3
matikus sz´ am als´ o korl´ atj´at adta, 1973-ban Donath ´es Hoffman a gr´ afpart´ıci´ o ter¨ ulet´en ´ert el eredm´enyeket. A saj´at´ert´ekek haszn´alat´anak igen fontos p´eld´ aja a ϑ-f¨ uggv´eny, melyet Lov´asz defini´alt 1979-ben. Akkor m´ ar hossz´ u ideje megoldatlan volt Shannon probl´em´ aja, az ¨ot-k¨or√kapacit´ as´ anak (Θ(C5 )) meghat´ aroz´ asa. Annyit lehetett csak tudni, hogy 5 ≤ Θ(C5 ) ≤ 5 o korl´ at a defin´ıci´ob´ ol, a fels˝o korl´ at Shannon t´etel´eb˝ ol ad´ odott, 2 , ahol az als´ mely szerint Θ(G) fel¨ ulr˝ ol becs¨ ulhet˝ o egy line´ aris program optimum´ert´ek´evel. A√ϑ(G) az ut´ obbin´al √ ´elesebb fels˝o becsl´es a gr´ af kapacit´ as´ ara ´es ol Θ(C5 ) = 5 ad´ odik. A Shannon-probl´ema megold´ asa ϑ(C5 ) = 5, amib˝ mellett Lov´asz bebizony´ıtja, hogy ϑ(G) a gr´ af stabilit´ asi sz´ am´ anak (α(G)) fels˝o korl´ atja ´es perfekt gr´ afokra ϑ(G) = α(G). 1981-ben Gr¨ otschel, Lov´asz ´es Schrijver megmutatt´ ak, hogyan lehet az ellipszoid algoritmus seg´ıts´eg´evel polinom id˝ oben megtal´ alni egy perfekt gr´ af egy legnagyobb stabil halmaz´ at. E t´etelek a szemidefinit programoz´as korai ´es sz´ep alkalmaz´ asai. A szemidefinit program egy m´ atrixv´ altoz´os line´ aris program, melyben a v´altoz´ ora line´ aris felt´etelek mellett pozit´ıv szemidefinit´ast k¨ovetel¨ unk meg. Speci´ alis konvex program ´ am m´eg mindig el´eg ´altal´anos ahhoz, hogy fontos konvex optimaliz´ aci´ os probl´em´ ak, mint p´eld´ aul a line´ aris ´es kvadratikus program, valamint saj´at´ert´ek-probl´em´ ak megfogalmazhat´ ok legyenek szemidefinit programk´ent. A szemidefinit program n´eh´ any vonatkoz´asban hasonl´ıt a line´ aris programhoz. Ut´obbi dualit´ aselm´elete bizonyos regularit´ asi felt´etelekkel ´ altal´ anos´ıt´odik a szemidefinit programokra, ak´arcsak a gyorsas´agukban a szimplex algoritmussal veteked˝ o bels˝ opontos m´ odszerek. Adott ǫ > 0 eset´en a szemidefinit program polinom id˝ oben, ǫ-nyi addit´ıv hib´ aval megoldhat´o, ak´ar az ellipszoid m´ odszert, ak´ar a gyakorlatban hat´ekonyabb bels˝ opontos algoritmusokat haszn´alva. 1989-ben Lov´asz ´es Schrijver megmutatt´ ak hogyan lehet eg´esz´ert´ek˝ u programok a line´ aris relax´aci´on´ al szorosabb szemidefinit relax´aci´oit elk´esz´ıteni. A m´ odszer erej´et mutatja, hogy mikor a stabil halmaz poli´ederre alkalmazt´ ak, a poli´eder n´egy line´ aris relax´aci´oj´anak metszet´en´el is er˝ osebb relax´aci´ ot kaptak! A leg´ ujabb eredm´enyek, Delorme, Poljak ´es Boppana korl´ atai a maxim´ alis v´ag´ as illetve a minim´alis f´elbev´ag´as ´ert´ek´ere, szint´en szemidefinit programok optimum´ert´ekei. Az el˝obbi 0, 87-szerese a maxim´ alis v´ag´ as ´ert´ek´enek polinom id˝ oben realiz´ alhat´ o als´ o korl´ atja, az ut´ obbi pedig bizonyos val´ osz´ın˝ us´egi modellben nagy val´osz´ın˝ us´eggel pontos ´ert´eket ad.
4
A jegyzet fel´ ep´ıt´ ese 1. Az alapfogalmak ´ atism´etl´ese mellett bebizony´ıtjuk az alapvet˝o t´etelt szimmetrikus m´ atrixok ortogon´ alis diagonaliz´ alhat´ os´ ag´ar´ ol, valamint Rayleigh ´es Cauchy t´etel´et. 2. A gr´ af adjacencia m´ atrix´anak spektrum´ ab´ ol nyer¨ unk fels˝o ´es als´ o korl´ atot a kromatikus sz´ amra. (Wilf ´es Hoffman t´etelei.) 3. Ky Fan t´etel´et (illetve az ´altal´anosabb Neumann-t´etelt) bizony´ıtjuk h´ aromf´elek´eppen konvex burok t´etelek ´es Lagrange-multiplik´atorok seg´ıts´eg´evel. E t´etelek sz´ amos alkalmaz´ as´ aval tal´alkozunk a k´es˝ obbiekben: a k¨ovetkez˝ o fejezetben szerepl˝o korl´ atok konvexit´as´ anak vizsg´alat´ara, egyszer˝ u bizony´ıt´ as´ ara, illetve ´ altal´anos´ıt´as´ ara haszn´aljuk ˝oket, Ky Fan t´etel´enek m´ asodik bizony´ıt´ asa seg´ıts´eg´evel ´ırunk fel szemidefinit programk´ent bizonyos saj´at´ert´ek-probl´em´ akat a 9. fejezetben. 4. Ebben a fejezetben egyetlen m´ atrix helyett m´ atrixseregek spektrumaib´ ol olvasunk ki saj´at´ert´ek-korl´ atokat a maxim´alis v´ag´as, gr´ af f´elbev´ag´as ´es gr´ afpart´ıci´ o probl´em´ ak optimum´ert´ek´ere. A Shannon-probl´ema ´es megold´ asa a ϑ-f¨ uggv´eny seg´ıts´eg´evel. Megmutatjuk, hogy a ϑ-f¨ uggv´eny egy saj´at´ert´ek-probl´ema optimum´ert´eke ´es t´argyaljuk egy ´altal´anos´ıt´as´ at. A m´ asodik r´eszben a line´ aris, illetve a konvex programoz´as elm´elet´eb˝ ol ismert t´eteleket bizony´ıtunk. 5. A Farkas-lemma egy szepar´aci´os t´etelre ´es Caratheodory t´etel´ere alapul´ o bizony´ıt´ as´ at adjuk, valamint n´eh´ any alakj´ at soroljuk fel. 6. Az adjung´ alt k´ up ´es tulajdons´ agai, a line´ aris egyenl˝ otlens´egek alapt´etele, a Weyl–Minkowski-t´etel valamint a poli´ederek u ´j jellemz´ese. 7. A line´ aris programoz´as dualit´ ast´etelei, majd ´altal´anos´ıt´asuk (z´arts´ agi felt´etelekkel) a k´ upline´aris programok eset´ere. 8. Egy a z´ arts´ agi felt´etelek teljes¨ ul´es´ehez el´egs´eges krit´erium. 9. A standard alak´ u szemidefinit program eset´eben u ´jra bizony´ıtjuk a fenti dualit´ ast´eteleket. P´eld´ ak ´es a program bonyolults´ ag´ara vonatkoz´o eredm´enyek. Ezut´an a dualit´ aselm´elet ismeret´eben visszat´er¨ unk a maxim´alis v´ag´as ´es gr´ af f´elbev´ag´ as probl´em´ akhoz, valamint a ϑ-f¨ uggv´enyhez. Megmutatjuk, hogy a m´ ar bevezetett korl´ atok hogyan ´ırhat´ ok fel szemidefinit programok optimum´ert´ekek´ent, ´es hogy bizonyos ´ertelemben mindny´ajan ide´ alisak.
5
10. A maxim´ alis v´ag´ as ´es gr´ af kett´ev´ag´as probl´em´ak optimum´ert´ek´ere adott saj´at´ert´ek-korl´ atokat vizsg´aljuk a fenti szempontb´ ol. 11. A ϑ-f¨ uggv´eny sz´ amos jellemz´ese, tulajdons´ agai. Bizony´ıtjuk a szendvicst´etelt, amely a perfekt gr´ afok egy legnagyobb klikkj´et polinom id˝ oben megtal´ al´ o algoritmushoz vezet. 12. A szemidefinit programoz´as elm´elet´enek leg´ ujabb alkalmaz´ asai, a Goemans–Williamson ´es a Karger–Motwani–Sudan approxim´ aci´os algoritmus a maxim´ alis v´ag´ as, illetve a gr´ afsz´ınez´es probl´em´ ara. 13. A Lov´asz–Schrijver-m´ odszer ´es alkalmaz´ asa a stabil halmaz probl´em´ ara. Megmutatjuk, hogy az ´ıgy nyert szemidefinit korl´ at ´elesebb, mint sz´ amos line´ aris korl´ at, vagy ak´ar a ϑ(G). A f¨ uggel´ekekben extrem´ alis r´eszhalmazokra vonatkoz´ o t´eteleket bizony´ıtunk, illetve p´eld´ akat mutatunk regulariz´aci´ora ´es regularit´asi felt´etelek n´elk¨ uli dualit´ asra.
Irodalomjegyz´ ek ´ es k¨ osz¨ onetnyilv´ an´ıt´ as A jegyzet olvas´ asa algebrai, anal´ızisbeli, geometriai, val´osz´ın˝ us´egsz´ am´ıt´asi, v´eges matematikai el˝ oismereteket ig´enyel. 17, 19, 20, 25, 26, 32, 36, 37, 39, 55, 57, 61 Az egyes fejezetekhez felhaszn´ alt irodalom: 1. 2. 3. 4. 5.-7. 8. 9.
25, 26, 34, 36, 37, 61 3, 13, 16, 32, 36, 39, 57, 59 29, 56, 60, 61, 1, 30, 43, 47, 48, 53, 54, 17 44, 18, 43, 6, 53, 50, 15, 34, 40, 41, 46 29, 41, 58, 7, 9-12 35, 56, 41, 2, 9-12, 65, 1, 62 37, 61, 45, 41, 1, 51, 63
10. 11. 12. 13. A. B. C. D.
50, 18, 44, 14 40, 41, 23, 34 41, 22, 64, 31, 27 42 35, 60 4, 5, 28, 38, 60 66, 67 49, 51, 52, 62
Tov´abbi (pl. m˝ uszaki) alkalmaz´ asokr´ol ´es megold´ o algoritmusokr´ ol sz´ ol 1, 8, 21, 27, 33, 41, 62, 63
6
K¨ osz¨ onetet mondok Lov´asz L´ aszl´ onak, akinek 1995 december´eben tartott el˝ oad´ assorozata jelent˝ os m´ert´ekben hozz´ aj´arult e jegyzet elk´esz´ıt´es´ehez. Az 1., 2., 4., 5., 8., 9. fejezetek egyes r´eszeit, valamint a teljes 11., 12. fejezetet szinte v´altoztat´ as n´elk¨ ul ezekb˝ol az el˝oad´ asokb´ol vettem ´at. A 12. fejezet meg´ır´ as´ aban David Williamson el˝oad´ asai is seg´ıtettek. K¨ osz¨ onetet mondok Frank Andr´ asnak, aki sokir´any´ u seg´ıts´eget ny´ ujtott e jegyzet elk´esz´ıt´es´ehez: t´emavezet˝omk´ent ˝o h´ıvta fel a figyelmem erre az ´erdekes ter¨ uletre, seg´ıtett az anyaggy˝ ujt´esben ´es sz´ amos konzult´ aci´oval. A jegyzet 5., 6. ´es 7. fejezetei l´enyeg´eben az ˝o m´ asod´eves matematikus hallgat´ oknak tartott Oper´ aci´okutat´as el˝oad´ asainak egy r´esz´et t¨ ukr¨ozik. OTKA keret´enek (jelenlegi sz´ ama T17580) t´amogat´ as´ aval sz´ amos konferenci´ ara ´es minikurzusra eljutottam. Kov´acs Margit Konvex anal´ızis ´es nemline´aris programoz´as el˝oad´ asai (l´asd [35]-t) nagy seg´ıts´egemre voltak a 8. fejezet fel´ep´ıt´es´en´el. Terlaky Tam´ as adta a 9.14.-beli ellenp´eld´ at, sz´ amos konzult´ aci´oval ´es az anyaggy˝ ujt´esben is seg´ıtett. Hozz´a a Peregrinatio II. Alap´ıtv´any seg´ıts´eg´evel jutottam ki a delfti M˝ uszaki Egyetem Oper´ aci´okutat´asi Tansz´ek´ere. Ill´es Tibor h´ıvta fel a figyelmem a k´ upline´aris programoz´as n´eh´ any alapvet˝ o eredm´eny´ere. Jos Sturm adott p´eld´ at olyan gr´ afra, amelyre a Boppana-korl´ at du´ alj´anak optimum´ert´eke nem v´etetik fel. Pataki G´ abor h´ıvta fel a figyelmemet a [49] cikkre. K¨ osz¨ onettel tartozom m´eg Bacs´o G´ abornak ´es ifj. B¨or¨ oczky K´ arolynak vil´agos el˝ oad´ asaik´ert a perfekt gr´ afok, illetve a konvex geometria t´emak¨or´eben. A jegyzet meg´ır´ as´ at a Magyar Fels˝ ooktat´as´ert ´es Kutat´ as´ert Alap´ıtv´any 109/95. sz´ am´ u p´ aly´azata, kor´ abbi v´altozat´anak g´epeltet´es´et a TEMPUS amogatta. S JEP-11097-96 projectje t´ A jegyzet meg´ır´ as´ anak idej´en munk´altat´oim az E¨ otv¨ os Lor´and Tudom´ anyegyetem ´es a MTA R´enyi Alfr´ed Matematikai Kutat´ oint´ezet voltak. A lektori feladatokat Ill´es Tibor v´allalta. Figyelmesen ´atolvasta a teljes jegyzetet ´es t¨ obb hely¨ utt felh´ıvta a figyelmemet a nem el´eg r´eszletesen elmagyar´ azott bizony´ıt´ asokra, ´ıgy seg´ıtve a jegyzet ´erthet˝ obb´e t´etel´et.
7
Irodalomjegyz´ ek 1. F. Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization, SIAM J. Optimization 5 (1995), 13–51. 2. E. Anderson and P. Nash, Linear Programming in Infinite Dimensional Spaces, John Wiley & Sons, New York, 1987. 3. B. Andr´ asfai, Graph Theory: Flows, matrices, Akad´emiai Kiad´ o, Budapest, 1991. 4. G. P. Barker, The lattice of faces of a finite dimensional cone, Lin. Alg. Appl. 7 (1973), 71–82. 5. G. P. Barker and D. Carlson, Cones of diagonally dominant matrices, Pacific J. Math. 57 (1975), 14–32. 6. E. R. Barnes and A. J. Hoffman, Partitioning, spectra, and linear programming, in “Progress in Combinatorial Optimization”, (W. Pulleyblank, eds.), Academic Press, 1984, 13–25. 7. A. Ben-Israel, Linear equations and inequalities in finite dimensional, real or complex, vector spaces: A unified theory, J. Math. Anal. Appl. 27 (1969), 367–389. 8. A. Ben-Tal and A. Nemirovski, Convex optimization in engineering: Modeling, analysis, algorithms, Lecture notes, wi485, TU Delft. 9. A. Berman, Cones, matrices and mathematical programming, Springer-Verlag, Berlin, 1973. 10. A. Berman and A. Ben-Israel, More on Linear Inequalities with Applications to Matrix Theory, J. Math. Anal. Appl. 33 (1971), 482–496. 8
11. A. Berman and A. Ben-Israel, Linear Inequalities, Mathematical Programming and Matrix Theory, Math. Progr. 1 (1971), 291–300. 12. A. Berman and A. Ben-Israel, Linear Equations over Cones with Interior: A Solvability Theorem with Applications to Matrix Theory, Lin. Alg. Appl. 7 (1973), 139–149. 13. N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993. 14. R. B. Boppana, Eigenvalues and graph bisection: An average case analysis, 28th Annual Symp. Found. Comp. Sci. IEEE, 1987, 280– 285. 15. D. M. Cvetkovi´c, M. Doob, I. Gutman and A. Torgaˇsev, Recent results in the theory of graph spectra, Ann. Discr. Math. North-Holland 36 (1988). 16. D. M. Cvetkovi´c, M. Doob and H. Sachs, Spectra of graphs, Academic Press, New York, 1979. ´ Val´ 17. Cs´ asz´ ar A., os anal´ızis I., Tank¨onyvkiad´o, Budapest, 1989. 18. C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Progr. 62 (1993), 557–574. ´ anos algebra, Tank¨onyvkiad´o, Budapest, 1989. 19. Fried E., Altal´ 20. Fried E., Klasszikus ´es line´ aris algebra, Tank¨onyvkiad´o, Budapest, 1991. 21. M. X. Goemans, Semidefinite programming in combinatorial optimization, Math. Progr. 79 (1997), 143–161. 22. M. X. Goemans and D. P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM 42 (1995), 1115–1145. 23. M. Gr¨ otschel, L. Lov´asz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169–197. 24. Hajnal A. ´es Hamburger P., Halmazelm´elet, Tank¨onyvkiad´o, Budapest, 1989. 9
25. Haj´os Gy., Bevezet´es a geometri´ aba, Tank¨onyvkiad´o, Budapest, 1991. 26. P. R. Halmos, V´eges dimenzi´ os vektorterek, M˝ uszaki K¨ onyvkiad´o, Budapest, 1984. 27. C. Helmberg, Semidefinite programming for combinatorial optimization, ZIB-Report 00-34 (2000 October), Konrad-Zuse-Zentrum f¨ ur Informationstechnik Berlin. 28. R. D. Hill and S. R. Waters, On the cone of positive semidefinite matrices, Lin. Alg. Appl. 90 (1987), 81–88. 29. J. Hiriart-Urruty and C. Lemar´echal, Convex Analysis and Minimization Algorithms I, Springer-Verlag, Berlin, 1993. 30. A. J. Hoffman and H. W. Wielandt, The variation of the spectrum of a normal matrix, Duke Math. J. l20 (1953), 37–39. 31. D. Karger, R. Motwani and M. Sudan, Approximate Graph Coloring by Semidefinite Programming, J. ACM 45(2) (1998), 246–265. 32. Katona Gy. ´es Recski A., Bevezet´es a v´eges matematik´ aba, ELTE, Budapest, 1993. 33. E. De Klerk, Interior point methods for semidefinite programming, Phd Thesis, TU Delft. 34. D. E. Knuth, The sandwich theorem, The Electronic Journal of Combinatorics 1 (1994). 35. Kov´acs M., A nemline´ aris programoz´ as elm´elete, TYPOTEX Kft., Budapest, 1997. 36. A. G. Kuros, Fels˝ obb algebra, Tank¨onyvkiad´o, Budapest, 1968. 37. P. Lancaster, Theory of Matrices, Academic Press, 1969. 38. M. Laurent and S. Poljak, On the facial structure of the set of correlation matrices, SIAM J. Matrix Anal. Appl. 17 (1996), 530–547. 39. L. Lov´asz, Combinatorial Problems and Exercises, Akad´emiai Kiad´ o, Budapest, 1979.
10
40. L. Lov´asz, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory IT-25 (1979), 1–7. 41. L. Lov´asz, Semidefinite programs and combinatorial optimization, minicourse & lecture notes, Budapest, 1995. 42. L. Lov´asz and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optimization 1(2) (1991), 160–190. 43. B. Mohar and S. Poljak, Eigenvalues and the max-cut problem, Czech. Math. J. 40(115) (1990), 343–352. 44. B. Mohar and S. Poljak, Eigenvalues in combinatorial optimization, Technical report, University of Ljubljana, 1992. 45. K. G. Murty, Linear and Combinatorial Programming, John Wiley & Sons, New York, 1976. 46. G. Narasimhan and R. Manber, A generalization of Lov´ asz’s Θ function, DIMACS Series in Discrete Math. and Comp. Sci. 1 (1990), 19–27. 47. M. L. Overton and R. S. Womersley, On the sum of the largest eigenvalues of a symmetric matrix, SIAM J. Matrix Anal. Appl. 13 (1992), 41–45. 48. M. L. Overton and R. S. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Math. Progr. 62 (1993), 321–357. 49. G. Pataki, A simple derivation of a facial reduction algorithm and extended dual systems, Technical Report, Dept. of IE/OR, Columbia University, 2000. 50. S. Poljak and F. Rendl, Nonpolyhedral relaxations of graph-bisection problems, SIAM J. Opt. 5(3) (1995), 467–487. 51. M. Ramana, An exact duality theory for semidefinite programming and its complexity implications, Math. Progr. 77(2) (1997), 129–162. 52. M. Ramana, L. Tun¸cel and H. Wolkowicz, Strong duality theorems for semidefinite programming, SIAM J. Opt., 7(3) (1997), 641–662.
11
53. F. Rendl and H. Wolkowicz, A Projection Technique for Partitioning the Nodes of a Graph, Ann. Oper. Res. 58 (1995), 155–180. 54. F. Rendl and H. Wolkowicz, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Math. Progr. 53 (1992), 63–78. 55. R´enyi A., Val´ osz´ın˝ us´egsz´ am´ıt´ as, Tank¨onyvkiad´o, Budapest, 1989. 56. R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. 57. R´ ozsa P., Line´ aris Algebra ´es Alkalmaz´ asai, Tank¨onyvkiad´o, Budapest, 1991. 58. A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1986. 59. A. J. Schwenk and R. J. Wilson, On the Eigenvalues of a Graph, Selected Topics in Graph Theory (L. W. Beineke and R. J. Wilson eds.). 60. J. Stoer and C. Witzgall, Convexity and optimization in finite dimensions I., Springer-Verlag, Berlin, 1970. 61. G. Strang, Linear Algebra and its Applications, Academic Press, New York, 1980. 62. J. Sturm, Primal-Dual Interior Point Approach to Semidefinite Programming, Phd thesis, Tinbergen Institute Research Series no. 156, Thesis Publishers, Amsterdam, 1997. 63. L. Vanderberghe and S. Boyd, Semidefinite programming, SIAM Review 38 (1996), 49–95. 64. D. P. Williamson, Approximation algorithms, minicourse & lecture notes, Eindhoven, 1996. 65. H. Wolkowicz, Some applications of optimization in matrix theory, Linear Algebra and its Applications 40 (1981), 101–118. 66. H. Wolkowicz and Q. Zhao, Semidefinite programming relaxations for the graph partitioning problem, Discrete Applied Math. 96/97 (1999), 461–479. 12
67. Q. Zhao, S. E. Karisch, F. Rendl and H. Wolkowicz, Semidefinite programming relaxations for the quadratic assignment problem, Journal of Combinatorial Optimization, 2(1) (1998), 71–109.
13
