Fair allocation algorithms for indivisible items under structured conflict constraints
DOI10.1007/s40314-023-02437-0arXiv2308.09399OpenAlexW4386616679MaRDI QIDQ6056608
Matjaž Krnc, Joachim Schauer, Ulrich Pferschy, Martin Milanič, Nina Chiarelli
Publication date: 2 October 2023
Published in: Computational and Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2308.09399
fair divisionconflict graphconvex bipartite graphspartial coloringbounded clique-widthbounded tree-independence number
Analysis of algorithms and problem complexity (68Q25) Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- Paths, trees and matchings under disjunctive constraints
- Scheduling with conflicts: Online and offline algorithms
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Precoloring extension. I: Interval graphs
- Geometric algorithms and combinatorial optimization
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Efficient graph representations
- Minimax relations for the partial q-colorings of a graph
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximation of knapsack problems with conflict and forcing graphs
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- On list \(k\)-coloring convex bipartite graphs
- Treewidth versus clique number in graph classes with a forbidden structure
- Structural parameterizations with modulator oblivion
- Mim-width. I. Induced path problems
- On the tractability of optimization problems on \(H\)-graphs
- Handle-rewriting hypergraph grammars
- On the thinness and proper thinness of a graph
- Approximating clique-width and branch-width
- The stable set problem and the thinness of a graph
- Fair allocation of indivisible items with conflict graphs
- Algorithms for the Bin Packing Problem with Conflicts
- The Santa Claus problem
- The Knapsack Problem with Conflict Graphs
- A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
- Clique-Width is NP-Complete
- Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
- Finding Branch-Decompositions of Matroids, Hypergraphs, and More
- A survey of χ‐boundedness
- On the Relationship Between Clique-Width and Treewidth
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- On \(H\)-topological intersection graphs
- Computations by fly-automata beyond monadic second-order logic
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Recognizing interval bigraphs by forbidden patterns
This page was built for publication: Fair allocation algorithms for indivisible items under structured conflict constraints
