Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem
verfasst von : Pawan Aurora, Monalisa Jena, Rajiv Raman
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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. 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, FAW-AAIM 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 present a PTAS for H-minor free graphs, if the demands on the edges are bounded above by a constant, and we show that the problem is APX-hard even for cubic graphs and bounded degree bipartite graphs with \(c_v = 1, \; \forall v\in V\).