Dividing splittable goods evenly and with limited fragmentation

DOI10.1007/s00453-019-00643-zzbMath1436.05028OpenAlexW2981373410MaRDI QIDQ2309472

Peter Damaschke

Publication date: 1 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00643-z

zbMATH Keywords

approximation algorithmweighted graphfair divisionlinear-time algorithmparameterized algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Searching and sorting (68P10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Signed and weighted graphs (05C22) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 3/2-approximation algorithm for \(k_i\)-partitioning
• Graph editing to a given degree sequence
• The \(k\)-partitioning problem
• Time bounds for selection
• Building fences straight and high: an optimal algorithm for finding the maximum length you can cut \(k\) times from given sticks
• On the computability of equitable divisions
• On degree sequences of undirected, directed, and bidirected graphs
• An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints
• Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Exact Weight Subgraphs and the k-Sum Conjecture
• Cake cutting really is not a piece of cake

This page was built for publication: Dividing splittable goods evenly and with limited fragmentation