Leírás
Az előadáson bevezetjük a d-distance matching feladatot, amelyben adott egy G=(S,T;E) páros gráf S={s_1,...,s_n}, T={t_1,...,t_k} csúcsosztályokkal, egy súlyfüggvény az éleken és egy d pozitív egész. A cél olyan M élrészhalmazt keresni, amelyre i) minden S-beli csúcs foka legfeljebb egy ii) ha s_it_j\in M, akkor |j-i|\geq d. A kérdés természetesen vetődik fel bizonyos ütemezési feladatoknál.
A feladat NP-nehéz, de könnyen adható 3-közelítő algoritmus. Az előadáson többek között ismertetünk egy érdekes LP-alapú (2-1/(2d-1))-közelítő algoritmust a súlyozott esetre, egy 3/2+\epsilon közelítő algoritmust a súlyozatlan esetre, és egy FPT algoritmust d paraméterrel. A feladat kapcsán számos nyitott kérdés van, és több természetes általánosítás is adódik.