otvorené problémy

prehľadávanie grafu

V [1] sa analyzuje nasledovný problém: je dan graf (bludisko) s ohodnotenmi hranami. Každý vrchol má jednoznačný idetifikátor. V jednom vrchole stojí agent, ktorý vidí ceny incidentných hrán a identifikátory vrcholov, do ktorých tieto hrany vedú. Agent sa môže presúvať po hranách, pričom za presun zaplat cenu hrany. Cieľom je navštviť všetky vrcholy a zaplatiť čo najmenej.

Ak je graf dopredu známy, ide o (jemne modifikovaný) problém obchodného cestujúceho. Otvorená otázka je, či existuje algoritmus bez znalosti grafu, ktorý dosiahne konštantný aproximačný pomer.

[1] Nicole Megow, Kurt Mehlhorn, Pascal Schweitzer: Online Graph Exploration: New Results on Old and New Algorithms. ICALP (2) 2011: 478-489 ( pdf)

k-partícia hyperkociek

Uvažujme fixnú konštantu k a množinu d-rozmerných hyperkociek Q_d. k-partíciou kocky Q_d nazveme rozdelenie vrcholov na k takmer rovnakých častí (t.j. na časti V_1,...,V_k tak, že |V_i| a |V_j| sa líšia najviac o 1). Úlohou je nájsť k-partíciu s minimálnym hranovým rezom, t.j. takú, aby počet hrán medzi rôznymi časťami bol minimálny. Špeciálne pre k tvaru 2^a je riešením rozdeliť kocku na a-dimenzionálne podkocky; úlohou je nájsť riešenie pre ľubovoľné fixné k.

V [1] je odvodený dolný odhad, ktorý vychádza z izoperimetrických nerovností: označme e(A) hranovú hranicu množiny A a e(m) minimálnu hranovú hranicu nejakej m-prvkovej množiny vrcholov. Zjavne počet hrán v minimálnej k-partícii je aspoň

G(k,d) := k/2 * min (  e ( floor(2^d / k) ),  e ( ceil(2^d / k) )  )
Keďže m-prvkové množiny, na ktorých sa nadobúda hranica e(m) sú presne charakterizované, vieme [2] ukázať, že
lim _(d->infty) G(k,d) / 2^d = c_k
a vyjadriť číslo c_k v závislosti od k. V [1] sa ukázalo, že tento odhad je asymtoticky tesný pre k tvaru 2^a+2^b alebo 2^a-2^b. Z [2] vyplýva, že odhad je asymptoticky tesný aj pre ďalšie hodnoty k, pričom prvé k, pre ktoré nemáme výsledok je 11.

[1] Bezrukov S.L.: On k-partitioning the n-cube. In: Proceedings Graph-Theoretic Concepts in Computer Science WG\\'96, LNCS 1197, Springer Verlag (1997), 44–55
[2] Bezrukov S.L., Královič R.: Partitioning of Hypercubes, unpublished manuscript