|
|
|
|
|
|
|
|||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Iván Szabolcs: Mátrixok OR_2 bonyolultsága, LP relaxáció és erős dualitási tétel |
|
|||
|
|
||||
|
||||
| Ha adott egy nxm-es A Boole mátrix, azt mondjuk, hogy a G irányított gráf *realizálja A-t*, ha G-nek m forrása és n nyelője van, melyek megfelelnek A oszlopainak és sorainak, oly módon, hogy az i. nyelő a j. forrásból pontosan akkor elérhető G-ben, ha A_ij=1. A célunk az A mátrixot minél kisebb élszámú G gráffal realizálni, ezt a minimális értéket OR(A)-val jelöljük. Természetesen elég körmentes gráfok közt vizsgálódni; ha a realizáló gráfokban az utak hosszára teszünk egy d felső korlátot, az úgy elérhető minimális élszámot OR_d(A)-val jelöljük. Ily módon pl. OR_2(A) megfelel a mátrix minél kisebb összköltségű téglalapokkal való fedésének, ahol egy téglalap egy csupa 1-es részmátrixa A-nak, egy axb méretű téglalap költsége pedig a+b. Stasys Jukna és Igor Szergejev 2013-as "Complexity of Linear Boolean Operators" surveyében ezzel kapcsolatban számos nyitott problémát vet fel, ezek közül kettő: - 7.3. A D_k Kneser-Sierpinski mátrix az a 2^kx2^k-s mátrix, melynek sorai és oszlopai a k-elemű halmaz részhalmazaival cimkézettek, és A_{H,K} pontosan akkor 1, ha H és K diszjunktak. Kérdés OR_2(D_k). Ismert alsó korlát n^{log5 / 2}, felső n^{1+\sqrt{2}}, ittn=2^k. Dimitrij Chistikovval, Jeffrey Shallittel és Anna Lubiwwal megjavítottuk a felső korlátot n^{9/4}-re. Összehasonlításként ezek a kitevők rendre kb. 1.16096, 1.27 és 1.16993. Sejtjük, hogy a valóság a log5 / 2. - 7.5. Ha a fenti lefedési problémában a mátrixok költségét uniforman 1-re vesszük, az úgy kapott bonyolultsági mértéket jelölje rank(A) . Ismert, hogy ha az A mátrixban nincs (k+1)x(k+1)-es téglalap (A "k+1"-mentes), akkor OR(A) >= ||A||/k^2, ahol ||A|| az egyesek száma A-ban, és ha C az A és B mátrixok tenzor szorzata, akkor OR(C) >= rank(A)*||B||/k^2, ha B (k+1)-mentes. Ez felveti a kérdést, hogy vajon az erősebb OR(C) = rank(A)*OR(B) állítás igaz lehet-e? Ezzel kapcsolatosan pedig azt mutattuk meg, hogy OR(C) >= rank(A) * OR(B) / logn, ha A egy nxn-es mátrix. Mindkét esetben egy vonatkozó módosított halmazlefedési feladat LP relaxáltját elemeztük, az első esetben mohó approximációval, a második esetben az erős dualitási tétellel. |
||||
| Hely : Bolyai Intézet, I. emelet, Riesz terem, Aradi Vértanúk tere 1., Szeged | ||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013