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.
De submodulära kostnaderna som täcker problemet föreslogs först av Iwata och Nagano REF.
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']}