Parameterized complexity of envy-free resource allocation in social networks

DOI10.1016/J.ARTINT.2022.103826MaRDI QIDQ2680801zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak

Publication date 4 January 2023

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2022.103826

zbMATH Keywords

clique-widthcomputational social choiceparameterized complexityresource allocationtreewidth

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• All structured programs have small tree width and good register allocation
• Approximating clique-width and branch-width
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
• Can you beat treewidth?
• Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
• Envy-free allocations respecting social networks
• Fair Allocation of Indivisible Goods
• Fundamentals of parameterized complexity
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. I. Excluding a forest
• Graph theory
• Group activity selection with few agent types
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the complexity of some colorful problems parameterized by treewidth
• Parameterized algorithms
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Sparsity. Graphs, structures, and algorithms
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• The rank-width of edge-coloured graphs
• Treewidth. Computations and approximations
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(8)

• On fair division with binary valuations respecting social networks
• Fair division with minimal withheld information in social networks
• Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network
• Approximate envy-freeness in graphical cake cutting
• Fair and efficient graphical resource allocation with matching-induced utilities
• MATE: masked optimal transport with dynamic selection for partial label graph learning
• Parameterized complexity of incomplete connected fair division
• The complexity of extending fair allocations of indivisible goods

This page was built for publication: Parameterized complexity of envy-free resource allocation in social networks

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