I detta dokument behandlas problemen med att minimera icke-negativa submodulära funktioner under täckning av begränsningar, som generaliserar vertex-skyddet, kantskyddet och ställer upp täckningsproblem. Vi ger approximationsalgoritmer för dessa problem som utnyttjar den diskreta konvexiteten hos submodulära funktioner. Vi presenterar först en avrundning 2- approximation algoritm för submodulära vertex cover problem baserat på halv-integraliteten av den kontinuerliga avslappningsproblem, och visar att avrundningsalgoritmen kan utföras genom en tillämpning av submodulär funktion minimering på en ringfamilj. Vi visar också att en avrundningsalgoritm och en primal-dual algoritm för den submodulära kostnadsuppsättningen täckningsproblem är båda konstant faktor approximation algoritmer om den maximala frekvensen är fast. Dessutom ger vi en i huvudsak snäv nedre gräns på ungefärligheten av problemet med submodulära kantskydd.
Till exempel har REF studerat problemet med "submodulära kostnadssättningar", där kostnaden för täckningen är en submodulfunktion som beror på vilka undergrupper som ingår i omslaget.
Submodular Function Minimization under Covering Constraints
{'venue': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science']}