Folyamok, Vágások, Hálózattervezés - Benczúr András, 2000 November 8

MTA SZTAKI, Informatika Kutatólaboratórium

Folyamok, Vágások:

• A gráfelmélet klasszikus területe [Ford-Fulkerson 1966]
• Ma is aktívan kutatott. Példa egy meglepő saját eredmény: egy véletlen mintavételezés és felerősítés segítségével jelentősen kiritkított gráfban is közelítőleg helyes vágásértékeket kapunk.

Alkalmazások:

• Változatos gráfproblémák: párosítások, posetek, utazó ügynök ...
• Hálózattervezési alapfeladat: legkisebb összköltségű, vágásértékek előírásait tejesítő gráf
  Általános esetben nehéz optimalizálási feladat
• Speciális esetek:
   
  • Minden vágásérték legalább k:   egy saját eredmény  
  • Kapacitáskorlát a csomópontokon:   irányított esetben reményteli eredmények,   de irányítatlan esetben teljesen ismeretlen a feladat nehézsége

Szakadék elmélet és gyakorlat között:

 

+

Nagyon gyors, bizonyíthatóan (közel) optimális végeredmény  

-

A gyakorlati problémák gyakran kicsik és alulspecifikáltak

Közeledés - Implementációk:

Utazó ügynök	Mozgássérült-szállító rendszer, Berlin	Saját implementáció  egy geometriai feladatra	A LEDA implementációs platform