Fair allocation of indivisible items with conflict graphs
From MaRDI portal
Publication:2701390
DOI10.1007/s00453-022-01079-8OpenAlexW4311131004MaRDI QIDQ2701390
Nina Chiarelli, Nevena Pivač, Martin Milanič, Joachim Schauer, Matjaž Krnc, Ulrich Pferschy
Publication date: 28 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.11313
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The maximum flow problem with disjunctive constraints
- Paths, trees and matchings under disjunctive constraints
- Finding odd cycle transversals.
- Scheduling with conflicts: Online and offline algorithms
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- The maximum k-colorable subgraph problem for chordal graphs
- Geometric algorithms and combinatorial optimization
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- Efficient graph representations
- Biconvex graphs: Ordering and algorithms
- Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Minimax relations for the partial q-colorings of a graph
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algorithmic graph theory and perfect graphs
- Approximation of knapsack problems with conflict and forcing graphs
- Preprocessing and cutting planes with conflict graphs
- A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
- Set covering problem with conflict constraints
- Partitioning to three matchings of given size is NP-complete for bipartite graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Scheduling identical jobs on uniform machines with a conflict graph
- Pickup and delivery problem with incompatibility constraints
- A structure theorem for the consecutive 1's property
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation
- Algorithms for the Bin Packing Problem with Conflicts
- Restricted Max-Min Fair Allocations with Inclusion-Free Intervals
- The Santa Claus problem
- PTAS for Ordered Instances of Resource Allocation Problems
- Approximating Multiobjective Knapsack Problems
- The Knapsack Problem with Conflict Graphs
- Easy problems for tree-decomposable graphs
- On Comparability and Permutation Graphs
- Algorithms for maximumk-colorings andk-coverings of transitive graphs
- Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Graph Classes: A Survey
- Approximation Algorithms for Computing Maximin Share Allocations
- Fair Enough
- Fair Allocation of Indivisible Goods: Improvement
- Combinatorial Algorithm for Restricted Max-Min Fair Allocation
- Fair Packing of Independent Sets
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Fair Allocation of Indivisible Goods
- On Allocating Goods to Maximize Fairness
- An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On-line machine covering
- On cycle transversals and their connected variants in the absence of a small linear forest
This page was built for publication: Fair allocation of indivisible items with conflict graphs
