Title
Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem.
Abstract
In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph \(G=(V,E)\) with capacity \(c_v\in {\mathbb {N}}\) on each vertex v. The objective is to find a feasible subgraph \(G'=(V,E')\) maximizing \(|E'|\), where \(G'\) is said to be feasible if for each \(e=\{u,v\}\in E'\), \(\deg _{G'}(u)\le c_u\) or \(\deg _{G'}(v)\le c_v\). In the weighted version of the problem, additionally each edge \(e\in E\) has a weight w(e) and we want to find a feasible subgraph \(G'=(V,E')\) maximizing \(\sum _{e\in E'} w(e)\). The problem is already NP-hard if \(c_v = 1\) for all \(v\in V\) (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14–16, pp 359–367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an \(O(\log n)\)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with \(c_v = 1, \; \forall v\in V\) and having degree at most 3.
Year
DOI
Venue
2018
10.1007/s10878-017-0206-1
COCOA
Keywords
DocType
Volume
Approximation algorithms, Combinatorial optimization, Maximum matching, Packing problem
Journal
36
Issue
ISSN
Citations 
4
1573-2886
0
PageRank 
References 
Authors
0.34
13
3
Name
Order
Citations
PageRank
Pawan Aurora112.39
Monalisa Jena200.34
Rajiv Raman318516.47