Begreppet submodularitet spelar en viktig roll i kombinatorisk optimering. I synnerhet kan många viktiga optimeringsproblem gjutas som submodulära maximeringsproblem, inklusive maximal täckning, maximal anläggningsplacering och maximal nedskärning i riktade/oriktade grafer. I detta dokument presenterar vi de första kända approximationsalgoritmer för problemet med att maximera en icke-decreasing submodulär uppsättning funktion med flera linjära begränsningar. Med tanke på en d-dimensionell budget vektorL, för vissa d ≥ 1, och en orakel för en icke-decreasing submodulär uppsättning funktion f över ett universum U, där varje element e U är associerad med en d-dimensionell kostnadsvektor, söker vi en delmängd av element S  på U vars totala kostnad är som mestL, sådan att f (S) maximeras. Vi utvecklar ett ramverk för att maximera submodulära funktioner med d linjära begränsningar som ger en (1 − ε)(1 − e −1 ) approximation till optimal för alla ε > 0, där d > 1 är något konstant. Vår studie motiveras av en variant av det klassiska problemet med maximal täckning som vi kallar maximal täckning med flera förpackningsbegränsningar. Vi använder vårt ramverk för att få samma approximationsgrad för detta problem. Såvitt vi vet är detta första gången den teoretiska gränsen på 1 – e – 1 matchas (nästan) för båda dessa problem.
Eftersom en av pionjärerna arbetar föreslogs en approximationsalgoritm i REF med en (1 - e - 1 - ) approximationsfaktor för alla > 0.
Maximizing Submodular Set Functions Subject to Multiple Linear Constraints
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}