Fair Packing of Independent Sets

DOI10.1007/978-3-030-48966-3_12MaRDI QIDQ5041187zbMATH OpenOpenAlexFDO

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

Publication date 13 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-48966-3_12

zbMATH Keywords

conflict graphfair divisionpartial coloring

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• Fair allocation algorithms for indivisible items under structured conflict constraints
• Diverse fair allocations: complexity and algorithms
• Diverse fair allocations: complexity and algorithms
• On fair division for indivisible items
• Restricted max-min fair allocations with inclusion-free intervals

Cites work

• Algorithmic graph theory and perfect graphs
• Algorithms for the bin packing problem with conflicts
• Approximation of knapsack problems with conflict and forcing graphs
• Biconvex graphs: Ordering and algorithms
• Combinatorial algorithm for restricted max-min fair allocation
• Fair Allocation of Indivisible Goods
• Graph Classes: A Survey
• scientific article; zbMATH DE number 4162902 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• Minimax relations for the partial q-colorings of a graph
• On-line machine covering
• Partitioning to three matchings of given size is NP-complete for bipartite graphs
• Paths, trees and matchings under disjunctive constraints
• PTAS for ordered instances of resource allocation problems
• Restricted max-min fair allocations with inclusion-free intervals
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Scheduling with conflicts: Online and offline algorithms
• The Knapsack Problem with Conflict Graphs
• The Santa Claus problem

Cited in

(4)

• The complexity of finding fair independent sets in cycles
• Allocating indivisible items with minimum dissatisfaction on preference graphs
• Fair allocation of indivisible items with conflict graphs
• Fair allocation algorithms for indivisible items under structured conflict constraints

This page was built for publication: Fair Packing of Independent Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041187)