Abstrakt. Vi anser två relaterade problem, Minimum Bounded Degree Matroid Basis problem och Minimum Bounded Degree Submodular Flow problem. Det första problemet är en generalisering av problemet Minimum Bounded Degree Spanning Tree: vi får en matris och en hypergraf på sin markuppsättning med lägre och övre gränser f (e) ≤ g (e) för varje hyperkant e. Uppgiften är att hitta en lägsta kostnadsbas som innehåller minst f (e) och som mest g (e) element från varje hyperkant e. I det andra problemet har vi ett submodulärt flöde problem, en lägre gräns f (v) och en övre gräns g (v) för varje nod v, och uppgiften är att hitta en minsta kostnad 0-1 submodulärt flöde med ytterligare begränsning att summan av inkommande och utgående flöde vid varje nod v är mellan f (v) och g (v). Båda dessa problem är NP-hårda (även genomförbarhetsproblemen är NP-fullständiga), men vi visar att de kan approximeras i följande mening. Låt opt vara värdet av den optimala lösningen. För det första problemet ger vi en algoritm som finner en grund B av kostnad inte mer än opt sådan att f (e) − 2Δ + 1 ≤  och B  för e till ≤ g(e) + 2Δ − 1 för varje hyperged e, där Δ är den maximala graden av hypergrafen. Om det bara finns övre gränser (eller bara nedre gränser), kan överträdelsen minskas till Δ − 1. För det andra problemet kan vi hitta en 0-1 submodulär flöde av kostnad på de flesta väljer där summan av inkommande och utgående flöde vid varje nod v är mellan f (v) − 1 och g(v) + 1. Dessa resultat kan tillämpas för att få approximationsalgoritmer för olika kombinatoriska optimeringsproblem med gradbegränsningar, inklusive problemet med minimalt korsande spanning träd, problemet med minsta gränsade grad spanning träd union, problemet med minimal gränsade grad directed cut cover och problemet med minimal gränsade grad graforientering.
Den minsta korsningen matroid bas problemet infördes i REF, där författarna använde iterativ avslappning för att få (1) (1, b +  på - 1)-tillnärmning när det bara finns övre gränser på grad, och (2) (1, b + 2 till - 1)-tillnärmning i närvaro av både övre och lägsta grad-bundet.
Degree bounded matroids and submodular flows
{'venue': 'In IPCO', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}