Antag att vi får en uppsättning objekt som täcker en region och en varaktighet i samband med varje objekt. Betrakta objekten som jobb, kan vi schemalägga deras starttider för att maximera den tid som den ursprungliga regionen förblir täckt? Vi kallar detta problem för SENSOR COVER PROBLEM. Det uppstår i samband med att täcka en region med sensorer. Anta till exempel att du vill övervaka aktivitet längs ett staket (interval) med sensorer placerade på olika fasta platser. Varje sensor har ett intervall (även ett intervall) och begränsad batteritid. Problemet är då att schemalägga när man ska slå på sensorerna så att staketet är helt övervakat så länge som möjligt. Detta endimensionella problem inbegriper intervaller på den verkliga linjen. Associering av en varaktighet till varje ger en uppsättning rektanglar i rum och tid, var och en anges av ett par fasta horisontella endpoints och en höjd. Målet är att tilldela en bottenposition till varje rektangel (genom att flytta dem uppåt eller nedåt) för att maximera den höjd på vilken spännvidden är fullt täckt. Vi kallar detta endimensionella problem RESTRICTED STRIPS OMFATTNING. Om vi ersätter den täckande begränsningen med en förpackningsrestriktion (rektanglar får inte överlappa, och målet är att minimera den högsta punkten som omfattas), då problemet blir identiskt med DYNAMISK LAGRING, ett välstuderat schemaläggningsproblem, som i sin tur är ett begränsat fall av det välkända problemet STRIP FÖRPACKNING. Vi presenterar en samling algoritmer för RESTRICTED STRIP COVERING. Vi visar att problemet är NP-hård och presentera en O (log log n)-tillnärmning algoritm. Vi presenterar också bättre approximation eller exakta algoritmer för vissa specialfall, även när alla intervall har samma bredd. För den allmänna SEN-SOR COVER PROBLEM, skiljer vi mellan fall där delar har enhetliga eller varierande varaktigheter. Resultaten beror på strukturen i den region som ska täckas: Vi ger en polynom-tid, exakt algoritm för den enhetliga varaktighet fall av RESTRICTED STRIP COVERING men bevisa att den enhetliga varaktighet fall för högre-dimensionella regioner är NP-hård. Vi ger några mer specifika resultat för tvådimensionella regioner. Slutligen anser vi att regioner som är godtyckliga uppsättningar, och vi presenterar en O(log n)-tillnärmning algoritm för de mest allmänna fallet.
TimeSC, som är känd som Restricted Strip Covering, visades vara NP-hard av Buchsbaum et al. REF, som också gav en O (log log log n) - approximation algoritm.
Restricted strip covering and the sensor cover problem
{'venue': "SODA '07", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}