Abstrakt. Vi anser att problemet med samtidiga källplatser väljer platser för källor i en kapacierad graf så att en given uppsättning krav kan uppfyllas. Vi ger en exakt algoritm för träd och visar hur detta kan kombineras med ett resultat av Räcke för att ge en lösning som överstiger kantkapaciteten med högst O(log 2 n log n), där n är antalet noder. På grafer av avgränsad trädbredd, visar vi problemet är fortfarande NP-Hard, men vi kan ge en PTAS med högst O(1+ ) överträdelse av kapaciteten, eller en (k +1)- approximation med exakt kapacitet, där k är trädbredd och kan göras godtyckligt liten.
Andreev m.fl. REF mycket nyligen föreslagna approximationsalgoritmer för att välja platser för källor i en kapacierad graf så att en given uppsättning krav kan tillgodoses samtidigt, med målet att minimera antalet valda platser.
Simultaneous Source Location
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Computer Science']}