Skip to main content
Top

2016 | OriginalPaper | Chapter

Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem

Authors : Pawan Aurora, Monalisa Jena, Rajiv Raman

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 288–298. Springer, Heidelberg (1997)CrossRef Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 288–298. Springer, Heidelberg (1997)CrossRef
2.
go back to reference Aurora, P., Singh, S., Mehta, S.K.: Partial degree bounded edge packing problem with arbitrary bounds. In: Tan, X., Zhu, B., Fellows, M. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 24–35. Springer, Heidelberg (2013)CrossRef Aurora, P., Singh, S., Mehta, S.K.: Partial degree bounded edge packing problem with arbitrary bounds. In: Tan, X., Zhu, B., Fellows, M. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 24–35. Springer, Heidelberg (2013)CrossRef
3.
go back to reference Babenko, M.A., Gusakov, A.: New exact and approximation algorithms for the star packing problem in undirected graphs. In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10–12 March 2011, Dortmund, Germany, pp. 519–530 (2011) Babenko, M.A., Gusakov, A.: New exact and approximation algorithms for the star packing problem in undirected graphs. In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10–12 March 2011, Dortmund, Germany, pp. 519–530 (2011)
7.
go back to reference Chlebík, M., Chlebíková, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264–1275 (2008)MathSciNetCrossRefMATH Chlebík, M., Chlebíková, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264–1275 (2008)MathSciNetCrossRefMATH
8.
go back to reference Dehne, F., Fellows, M.R., Fernau, H., Prieto, E., Rosamond, F.A.: nonblocker: parameterized algorithmics for minimum dominating set. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 237–245. Springer, Heidelberg (2006)CrossRef Dehne, F., Fellows, M.R., Fernau, H., Prieto, E., Rosamond, F.A.: nonblocker: parameterized algorithmics for minimum dominating set. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 237–245. Springer, Heidelberg (2006)CrossRef
9.
go back to reference Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.-i.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, pp. 637–646 (2005) Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.-i.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, pp. 637–646 (2005)
11.
go back to reference Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D., et al. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Heidelberg (1972)CrossRef Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D., et al. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Heidelberg (1972)CrossRef
12.
go back to reference Lovász, L., Plummer, M.D.: Matching Theory, vol. 367. American Mathematical Soc., Providence (2009)CrossRefMATH Lovász, L., Plummer, M.D.: Matching Theory, vol. 367. American Mathematical Soc., Providence (2009)CrossRefMATH
13.
go back to reference Micali, S., Vazirani, V.V.: An \({O}(\sqrt{|{V}|}|{E}|)\) algoithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, pp. 17–27. IEEE (1980) Micali, S., Vazirani, V.V.: An \({O}(\sqrt{|{V}|}|{E}|)\) algoithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, pp. 17–27. IEEE (1980)
14.
go back to reference Parekh, O.: Iterative packing for demand and hypergraph matching. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 349–361. Springer, Heidelberg (2011)CrossRef Parekh, O.: Iterative packing for demand and hypergraph matching. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 349–361. Springer, Heidelberg (2011)CrossRef
15.
go back to reference Parekh, O., Pritchard, D.: Generalized hypergraph matching via iterated packing and local ratio. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 207–223. Springer, Heidelberg (2015) Parekh, O., Pritchard, D.: Generalized hypergraph matching via iterated packing and local ratio. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 207–223. Springer, Heidelberg (2015)
16.
go back to reference Sahni, S.K.: On the knapsack and other computationally related problems (1973) Sahni, S.K.: On the knapsack and other computationally related problems (1973)
17.
go back to reference Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Heidelberg (2003)MATH Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Heidelberg (2003)MATH
18.
go back to reference Shepherd, B., Vetta, A.: The demand matching problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 457–474. Springer, Heidelberg (2002)CrossRef Shepherd, B., Vetta, A.: The demand matching problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 457–474. Springer, Heidelberg (2002)CrossRef
19.
go back to reference Zhang, P.: Partial degree bounded edge packing problem. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 359–367. Springer, Heidelberg (2012)CrossRef Zhang, P.: Partial degree bounded edge packing problem. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 359–367. Springer, Heidelberg (2012)CrossRef
Metadata
Title
Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem
Authors
Pawan Aurora
Monalisa Jena
Rajiv Raman
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-48749-6_14

Premium Partner