Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Approximations for the Max k-Colored Clustering Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Generalized Hypergraph Matching via Iterated Packing and Local Ratio

Authors : Ojas Parekh, David Pritchard

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

In \(k\)-hypergraph matching, we are given a collection of sets of size at most \(k\), each with an associated weight, and we seek a maximum-weight subcollection whose sets are pairwise disjoint. More generally, in \(k\)-hypergraph \(b\)-matching, instead of disjointness we require that every element appears in at most \(b\) sets of the subcollection. Our main result is a linear-programming based \((k-1+\tfrac{1}{k})\)-approximation algorithm for \(k\)-hypergraph \(b\)-matching. This settles the integrality gap when \(k\) is one more than a prime power, since it matches a previously-known lower bound. When the hypergraph is bipartite, we are able to improve the approximation ratio to \(k-1\), which is also best possible relative to the natural LP. These results are obtained using a more careful application of the iterated packing method.
Using the bipartite algorithmic integrality gap upper bound, we show that for the family of combinatorial auctions in which anyone can win at most \(t\) items, there is a truthful-in-expectation polynomial-time auction that \(t\)-approximately maximizes social welfare. We also show that our results directly imply new approximations for a generalization of the recently introduced bounded-color matching problem.We also consider the generalization of \(b\)-matching to demand matching, where edges have nonuniform demand values. The best known approximation algorithm for this problem has ratio \(2k\) on \(k\)-hypergraphs. We give a new algorithm, based on local ratio, that obtains the same approximation ratio in a much simpler way.

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!

inform now

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!

inform now

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!

inform now
previous chapter Online Packet Scheduling Under Adversarial Jamming
next chapter Steiner Trees with Bounded RC-Delay
Footnotes
1
A hypergraph is \(k\)-dimensional if for some \(k\)-partition of the ground set, every edge intersects every part exactly once.
 
2
In detail, the solutions \(x^i\) for \(i \in Q_v\) have degree 1 at \(v\), so by the definition of a convex combination \((Ax)_v = \lambda (Q_v)\), but \((Ax)_v \le 1 - t\) since, by feasibility, \(1 \ge A(x+t\chi _e)_v = (Ax)_v + t\).
 
3
Splitting means to replace the term \((x^i, \lambda ^i)\) with two terms \((x^i, p), (x^i, \lambda ^i-p)\) with distributed \(\lambda \)-mass on the same integer solution \(x^i\).
 
Literature
1.
Aharoni, R., Kessler, O.: On a possible extension of hall’s theorem to bipartite hypergraphs. Discret. Math. 84(3), 309–313 (1990)CrossRefMATHMathSciNet
2.
3.
Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-column sparse packing programs. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 369–382. Springer, Heidelberg (2010) CrossRef
4.
Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36(4), 422–463 (2004)CrossRef
5.
Bar-Yehuda, R., Halldórsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36(1), 1–15 (2006)CrossRefMATHMathSciNet
6.
Bar-Yehuda, R., Rawitz, D.: On the equivalence between the primal-dual schema and the local ratio technique. SIAM J. Discret. Math. 19(3), 762–797 (2005)CrossRefMATHMathSciNet
7.
Bar-Yehuda, R., Rawitz, D.: A tale of two methods. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 196–217. Springer, Heidelberg (2006) CrossRef
8.
Berman, P.: A \(d\)/2 approximation for maximum weight independent set in \(d\)-claw free graphs. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 214–219. Springer, Heidelberg (2000) CrossRef
9.
10.
Chan, Y., Lau, L.: On linear and semidefinite programming relaxations for hypergraph matching. Math. Program. 135, 123–148 (2011)CrossRefMathSciNet
11.
Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3) (2007)
12.
Feige, U., Singh, M.: Edge coloring and decompositions of weighted graphs. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 405–416. Springer, Heidelberg (2008) CrossRef
13.
Feldman, M., Naor, J.S., Schwartz, R., Ward, J.: Improved approximations for k-exchange systems. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 784–798. Springer, Heidelberg (2011) CrossRef
14.
15.
16.
17.
Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every \(t\) of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discret. Math. 2(1), 68–72 (1989)CrossRefMATHMathSciNet
18.
19.
Koufogiannakis, C., Young, N.E.: Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 221–238. Springer, Heidelberg (2009) CrossRef
20.
Krysta, P.: Greedy approximation via duality for packing, combinatorial auctions and routing. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 615–627. Springer, Heidelberg (2005) CrossRef
21.
Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: Proceedings of the 46th FOCS, pp. 595–604 (2005)
22.
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007) CrossRefMATH
23.
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
24.
Person, Y., Schacht, M.: Almost all hypergraphs without fano planes are bipartite. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 217–226. Society for Industrial and Applied Mathematics, Philadelphia (2009)
25.
Schrijver, A.: Combinatorial Optimization. Springer, New York (2003) MATH
26.
27.
Stamoulis, G.: Approximation algorithms for bounded color matchings via convex decompositions. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 625–636. Springer, Heidelberg (2014) CrossRef
28.
Metadata
Title
Generalized Hypergraph Matching via Iterated Packing and Local Ratio
Authors
Ojas Parekh
David Pritchard
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-18262-9

Electronic ISBN: 978-3-319-18263-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-18263-6_18

Premium Partner

    Image Credits