Abstrakt. Att hitta en maximal oberoende uppsättning (MIS) av en given familj av axelparallellrektanglar är ett grundläggande problem i beräkningsgeometri och kombinatorik. Detta problem har fått stor uppmärksamhet sedan sextiotalet, när Wegner antog att motsvarande dualitetsgap, dvs. det maximala möjliga förhållandet mellan den maximala oberoende uppsättningen och den minsta träffuppsättningen (MHS), begränsas av en universell konstant. Ett intressant specialfall, som kan visa sig användbart för att ta itu med det allmänna problemet, är diagonal-intersecting fallet, där den givna familjen av rektanglar skärs av en diagonal. I själva verket Chepoi och Felsner nyligen gav en faktor 6 approximation algoritm för MHS i denna inställning, och visade att duality gap är mellan 3/2 och 6. I detta dokument förbättrar vi dessa resultat. Först visar vi att MIS i diagonal-intersecting familjer är NP-komplett, vilket ger en minsta underklass som MIS är bevisligen svårt. Sedan härleder vi en O(n 2 )-tid algoritm för maximal vikt oberoende set när, dessutom rektanglar skär under diagonalen. Detta förbättrar och utökar ett klassiskt resultat av Lubiw, och uppgår till att erhålla en 2- approximation algoritm för maximal vikt oberoende uppsättning av rektanglar skär en diagonal. Slutligen bevisar vi att dualitetsklyftan är mellan 2 och 4 för familjer som skär diagonalt. Den övre gränsen, som innebär en approximationsalgoritm av samma faktor, följer av ett enkelt kombinatoriskt argument, medan den nedre gränsen representerar den mest kända nedre gränsen på dualitetsklyftan, även i det allmänna fallet. En utökad sammanfattning av en preliminär version av detta verk förekommer i det elfte latinamerikanska teoretiska informatiksymposiet.
Nyligen, Correa et al. REF visade att detta problem är NP-hårdt även när det gäller en rak linje och föreslog en 4-approximationsalgoritm för just detta fall.
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line : Algorithms and Complexity
{'venue': None, 'journal': 'arXiv: Computational Geometry', 'mag_field_of_study': ['Mathematics', 'Computer Science']}