NDLI: Degree bounded matroids and submodular flows

Please wait, while we are loading the content...

Degree bounded matroids and submodular flows

Content Provider	Springer Nature Link
Author	Singh, Mohit Lau, Lap Chi Király, Tamás
Copyright Year	2012
Abstract	We consider two related problems, the Minimum Bounded Degree Matroid Basis problem and the Minimum Bounded Degree Submodular Flow problem. The first problem is a generalization of the Minimum Bounded Degree Spanning Tree problem: We are given a matroid and a hypergraph on its ground set with lower and upper bounds f(e)≤g(e) for each hyperedge e. The task is to find a minimum cost basis which contains at least f(e) and at most g(e) elements from each hyperedge e. In the second problem we have a submodular flow problem, a lower bound f(v) and an upper bound g(v) for each node v, and the task is to find a minimum cost 0–1 submodular flow with the additional constraint that the sum of the incoming and outgoing flow at each node v is between f(v) and g(v). Both of these problems are NP-hard (even the feasibility problems are NP-complete), but we show that they can be approximated in the following sense. Let opt be the value of the optimal solution. For the first problem we give an algorithm that finds a basis B of cost no more than opt such that f(e)−2Δ+1≤\|B∩e\|≤g(e)+2Δ−1 for every hyperedge e, where Δ is the maximum degree of the hypergraph. If there are only upper bounds (or only lower bounds), then the violation can be decreased to Δ−1. For the second problem we can find a 0–1 submodular flow of cost at most opt where the sum of the incoming and outgoing flow at each node v is between f(v)−1 and g(v)+1. These results can be applied to obtain approximation algorithms for several combinatorial optimization problems with degree constraints, including the Minimum Crossing Spanning Tree problem, the Minimum Bounded Degree Spanning Tree Union problem, the Minimum Bounded Degree Directed Cut Cover problem, and the Minimum Bounded Degree Graph Orientation problem.
Ending Page	720
Page Count	18
Starting Page	703
File Format	PDF
ISSN	02099683
e-ISSN	14396912
Journal	Combinatorica
Issue Number	6
Volume Number	32
Language	English
Publisher	Springer-Verlag
Publisher Date	2013-01-03
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms Mathematics Combinatorial optimization Combinatorics
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Simple push-relabel algorithms for matroids and submodular flows

Approximating Directed Multicuts

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

The optimal path-matching problem

Submodular maximization meets streaming: matchings, matroids, and more

Submodular Stochastic Probing on Matroids

Submodular function minimization

Bulk-Robust combinatorial optimization

Degree bounded matroids and submodular flows

Similar Documents

Simple push-relabel algorithms for matroids and submodular flows

Approximating Directed Multicuts

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

The optimal path-matching problem

Submodular maximization meets streaming: matchings, matroids, and more

Submodular Stochastic Probing on Matroids

Submodular function minimization

Bulk-Robust combinatorial optimization

Degree bounded matroids and submodular flows