Vi studerar Maximum Independent Set of Rectangles (MISR) problem: med tanke på en samling R av n axel-parallell rektanglar, hitta en maximal-kardinalitet delmängd av separata rektanglar. MISR är ett specialfall av det klassiska problemet Maximum Independent Set, där inmatningen är begränsad till skärningsdiagram över axelparallellrektanglar. På grund av dess många tillämpningar, allt från kartmärkning till datautvinning, har MISR fått stor uppmärksamhet från olika forskarsamfund. Eftersom problemet är NP-hård, har huvudfokus varit på utformningen av approximationsalgoritmer. Flera grupper av undersökningar har självständigt föreslagit O(log n)-tillnärmning algoritmer för MISR, och detta förblev den mest kända approximationsfaktorn för problemet. Huvudresultatet av vårt papper är en O(log log n)-tillnärmningsalgoritm för MISR. Vår algoritm kombinerar befintliga metoder för att lösa speciella fall av problemet, där inmatningsmängden av rektanglar är begränsad till att innehålla specifika skärningstyper, med nya insikter i den kombinatoriska strukturen av uppsättningar skärande rektanglar i planet. Vi överväger också en generalisering av MISR till högre dimensioner, där rektanglar ersätts av ddimensionella hyper-rektanglar. Våra resultat för MISR innebär en O(log n) d−2 log log n) - approximation algoritm för detta problem, förbättra på den mest kända O(log n) d−1 ) - approximation.
De mest kända nedre och övre gränserna för det (i oviktat fall) är 3/2 och O(log log n) REF, respektive.
Maximum independent set of rectangles
{'venue': 'In: SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}