Abstrakt. På grund av vikten av robusthet i många verkliga optimeringsproblem har området robust optimering fått mycket uppmärksamhet under det senaste årtiondet. Vi koncentrerar oss på problem med maximalt flöde och introducerar en ny robust optimeringsmodell som, jämfört med kända modeller från litteraturen, har flera fördelaktiga egenskaper: (i) Vi anser att en allmän klass av vägbaserade flödesproblem som kan användas för att modellera ett stort utbud av nätverkstrauting problem (och andra förpackningsproblem). (ii) Vi siktar på lösningar som är robusta mot riktade attacker av en potent motståndare som kan attackera alla flöden av hans val på någon kant av nätverket. (iii) I motsats till tidigare robusta modeller för maximalt flöde, för vilka inga effektiva algoritmer är kända, kan optimala robusta flöden för de viktigaste grundläggande varianterna av vår modell hittas i polynom tid. Vi överväger också generaliseringar där flödesspelaren kan spendera en budget för att skydda nätverket mot interdiktorn. Här visar vi att problemet kan lösas effektivt när interdiction kostnaderna bestäms av flödesspelaren från grunden. Problemet blir dock svårt att uppskatta när flödesspelaren måste förbättra en initial skyddsinfrastruktur.
Matuschke m.fl. REF presenterade en ny robust optimeringsmodell för problemet med att maximera mängden flöde som överlever attacken av en interdictor, som kan användas för att modellera en stor mängd olika nätverk routing problem.
Protection of flows under targeted attacks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}