Strålbehandling är en av de vanliga cancerbehandlingarna. Strålbehandlingen utgör ett tuningsproblem: det måste vara tillräckligt effektivt för att förstöra tumören, men det bör upprätthålla funktionen hos de organ som ligger nära tumören. Mot detta mål måste utformningen av en strålbehandling anpassas för varje patient. En del av denna konstruktion är intensitetsmatriser som definierar stråldosen i en diskretisering av strålhuvudet. För att minimera behandlingstiden för en patient måste stråltiden och installationstiden minimeras. För en given rad av intensitetsmatrisen motsvarar minimitiden för strålkastning det minsta antalet binära vektorer med den på varandra följande egenskapen "1" som summan av denna rad, och minimiinställningstiden motsvarar det minsta antalet olika vektorer i en uppsättning binära vektorer med den på varandra följande egenskapen "1" som summan till denna rad. Vi ger en enkel linjär tidsalgoritm för att beräkna minsta stråltid. Vi bevisar att den minsta installationstiden problem är APX-hård och ge approximation algoritmer för det med hjälp av en duality egenskap. I det allmänna fallet ger vi en 24 13 approximationsalgoritm. För unimodala rader ger vi en 9 7 approximationsalgoritm. Vi överväger också andra varianter för vilka det finns bättre approximativa proportioner.
Bansal m.fl. REF tillhandahåller en 3⁄4 1⁄2¿-approximeringsalgoritm för enradsproblemet och ger bättre approximationer för mer begränsade versioner.
Minimizing setup and beam-on times in radiation therapy
{'venue': 'In Proceedings of APPROX 2006', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}