Fair allocation algorithms for indivisible items under structured conflict constraints

DOI10.1007/S40314-023-02437-0MaRDI QIDQ6056608zbMATH OpenOpenAlexFDO

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

Publication date 2 October 2023

Published in Computational and Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2308.09399

zbMATH Keywords

bounded clique-widthbounded tree-independence numberconflict graphconvex bipartite graphsfair divisionpartial coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Dynamic programming (90C39) Minimax problems in mathematical programming (90C47) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Fair Packing of Independent Sets
• Allocation of indivisible items with individual preference graphs
• On fair division for indivisible items
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• An approximation algorithm for max-min fair allocation of indivisible goods

Cites work

• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A survey of -boundedness
• Algorithms for the bin packing problem with conflicts
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Approximating clique-width and branch-width
• Approximation of knapsack problems with conflict and forcing graphs
• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Clique-width is NP-complete
• Computations by fly-automata beyond monadic second-order logic
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient graph representations
• Fair allocation of indivisible items with conflict graphs
• Finding branch-decompositions of matroids, hypergraphs, and more
• Geometric algorithms and combinatorial optimization
• Graph-Theoretic Concepts in Computer Science
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 4162902 (Why is no real title available?)
• scientific article; zbMATH DE number 1303600 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Mim-width. I. Induced path problems
• Minimax relations for the partial q-colorings of a graph
• Minor-matching hypertree width
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• On \(H\)-topological intersection graphs
• On list \(k\)-coloring convex bipartite graphs
• On the Relationship Between Clique-Width and Treewidth
• On the thinness and proper thinness of a graph
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Paths, trees and matchings under disjunctive constraints
• Precoloring extension. I: Interval graphs
• Recognizing interval bigraphs by forbidden patterns
• Scheduling with conflicts: Online and offline algorithms
• Structural parameterizations with modulator oblivion
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Knapsack Problem with Conflict Graphs
• The Santa Claus problem
• The stable set problem and the thinness of a graph
• Treewidth versus clique number in graph classes with a forbidden structure
• Upper bounds to the clique width of graphs

Cited in

(6)

• Allocating indivisible items with minimum dissatisfaction on preference graphs
• scientific article; zbMATH DE number 7366679 (Why is no real title available?)
• Fair Packing of Independent Sets
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Maximin share based mechanisms for multi-resource fair allocation with divisible and indivisible tasks
• Induced matching treewidth and tree-independence number, revisited

This page was built for publication: Fair allocation algorithms for indivisible items under structured conflict constraints

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