Show simple item record

Author
dc.contributor.author
Király, Tamás 
Author
dc.contributor.author
LC, Lau 
Author
dc.contributor.author
M, Singh 
Availability Date
dc.date.accessioned
2015-01-06T12:29:01Z
Availability Date
dc.date.available
2015-01-06T12:29:01Z
Release
dc.date.issued
2012
Issn
dc.identifier.issn
0209-9683
uri
dc.identifier.uri
http://hdl.handle.net/10831/10666
Abstract
dc.description.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. © 2012 János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.
Language
dc.language
Angol
Rent
dc.publisher
Springer
Contact information
dc.relation.ispartof
urn:issn:0209-9683
Title
dc.title
Degree bounded matroids and submodular flows
Type
dc.type
folyóiratcikk
Date Change
dc.date.updated
2014-12-16T13:26:41Z
Language
dc.language.rfc3066
eng
Note
dc.description.note
FELTÖLTŐ: Király Tamás - tkiraly@cs.elte.hu
Scope
dc.format.page
703-720
Doi ID
dc.identifier.doi
doi:10.1007/s00493-012-2760-6
Wos ID
dc.identifier.wos
000320035500005
ID Scopus
dc.identifier.scopus
84879920669
MTMT ID
dc.identifier.mtmt
2202320
Issue Number
dc.identifier.issue
6
Journal
dc.identifier.jtitle
COMBINATORICA
Volume Number
dc.identifier.volume
32
Release Date
dc.description.issuedate
2012
Author Details
dc.description.author
Király, Tamás : 10012149 (ELTE/ELTE TTK/ELTE TTK MI/MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport)
department of Author
dc.contributor.institution
Eötvös Loránd Tudományegyetem
Author institution
dc.contributor.department
ELTE/ELTE TTK/ELTE TTK MI/MTA-ELTE Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport
Author MTMT ID
dc.contributor.mtmtid
10012149
Uploader's email
dc.description.submitteremail
tkiraly@cs.elte.hu
Uploader Name
dc.description.submittername
Király Tamás
ID Uploader
dc.identifier.submitter
10012149


Files in this item

Degree bounded matroids and submodular flows
 

This item appears in the following Collection(s)

Show simple item record