Top

Published in:

2020 | OriginalPaper | Chapter

Fair Packing of Independent Sets

Authors : Nina Chiarelli, Matjaž Krnc, Martin Milanič, Ulrich Pferschy, Nevena Pivač, Joachim Schauer

Published in: Combinatorial Algorithms

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

In this work we add a graph theoretical perspective to a classical problem of fairly allocating indivisible items to several agents. Agents have different profit valuations of items and we allow an incompatibility relation between pairs of items described in terms of a conflict graph. Hence, every feasible allocation of items to the agents corresponds to a partial coloring, that is, a collection of pairwise disjoint independent sets. The sum of profits of vertices/items assigned to one color/agent should be optimized in a maxi-min sense. We derive complexity and algorithmic results for this problem, which is a generalization of the classical Partition and Independent Set problems. In particular, we show that the problem is strongly NP-complete in the classes of bipartite graphs and their line graphs, and solvable in pseudo-polynomial time in the classes of cocomparability graphs and biconvex bipartite graphs.

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 Further Results on Online Node- and Edge-Deletion Problems with Advice

next chapter Polynomial Time Algorithms for Tracking Path Problems

Abbas, N., Stewart, L.K.: Biconvex graphs: ordering and algorithms. Discret. Appl. Math. 103(1–3), 1–19 (2000)MathSciNetCrossRef

Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3–13. Gorky University Press (1982). (in Russian)

Annamalai, C., Kalaitzis, C., Svensson, O.: Combinatorial algorithm for restricted max-min fair allocation. ACM Trans. Algorithms 13(3), 1–28 (2017)MathSciNetCrossRef

Azar, Y., Epstein, L.: On-line machine covering. J. Sched. 1, 67–77 (1998)MathSciNetCrossRef

Bansal, N., Sviridenko, M.: The Santa Claus problem. In: STOC 2006: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 31–40 (2006)

Berge, C.: Minimax relations for the partial \(q\)-colorings of a graph. Discret. Math. 74(1–2), 3–14 (1989)MathSciNetCrossRef

Bezakova, I., Dani, V.: Allocating indivisible goods. ACM SIGecom Exchanges 5(3), 11–18 (2005)CrossRef

Bodlaender, H.L., Jansen, K.: On the complexity of scheduling incompatible jobs with unit-times. In: Borzyszkowski, A.M., Sokołowski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 291–300. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57182-5_21CrossRefMATH

Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair allocation of indivisible goods. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, pp. 284–310. Cambridge University Press, Cambridge (2016)CrossRef

10.

Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM) (1999)

11.

Darmann, A., Pferschy, U., Schauer, J., Woeginger, G.: Paths, trees and matchings under disjunctive constraints. Discret. Appl. Math. 159, 1726–1735 (2011)MathSciNetCrossRef

12.

Deuermeyer, B.L., Friesen, D.K., Langston, M.A.: Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J. Algebraic Discret. Methods 3(2), 190–196 (1982)MathSciNetCrossRef

13.

Even, G., Halldórsson, M.M., Kaplan, L., Ron, D.: Scheduling with conflicts: online and offline algorithms. J. Sched. 12(2), 199–224 (2009)MathSciNetCrossRef

14.

Golovin, D.: Max-min fair allocation of indivisible goods. Technical report, CMU-CS-05-144, Carnegie Mellon University (2005)

15.

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. Elsevier, Amsterdam (2004)MATH

16.

Khodamoradi, K., Krishnamurti, R., Rafiey, A., Stamoulis, G.: PTAS for ordered instances of resource allocation problems. In: Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013. LIPICS, vol. 24, pp. 461–473 (2013)

17.

Mastrolilli, M., Stamoulis, G.: Restricted max-min fair allocations with inclusion-free intervals. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 98–108. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32241-9_9CrossRef

18.

Muritiba, A., Iori, M., Malaguti, E., Toth, P.: Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. 22(3), 401–415 (2010)MathSciNetCrossRef

19.

Pálvölgi, D.: Partitioning to three matchings of given size is NP-complete for bipartite graphs. Acta Univ. Sapientiae Informatica 6(2), 206–209 (2014)CrossRef

20.

Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233–249 (2009)MathSciNetCrossRef

21.

Pferschy, U., Schauer, J.: Approximation of knapsack problems with conflict and forcing graphs. J. Comb. Optim. 33(4), 1300–1323 (2017)MathSciNetCrossRef

22.

de Werra, D.: Packing independent sets and transversals. In: Combinatorics and Graph Theory, Banach Center Publications, vol. 25, pp. 233–240. PWN, Warsaw (1989)

Title: Fair Packing of Independent Sets
Authors: Nina Chiarelli
Matjaž Krnc
Martin Milanič
Ulrich Pferschy
Nevena Pivač
Joachim Schauer
Publisher: Springer International Publishing
Book: Combinatorial Algorithms
Print ISBN: 978-3-030-48965-6

Electronic ISBN: 978-3-030-48966-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-48966-3_12

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner