Improved algorithmic results for unsplittable stable allocation problems

DOI10.1007/S10878-015-9889-3MaRDI QIDQ326457zbMATH OpenOpenAlexFDO

Authors Ágnes Cseh, Brian C. Dean

Publication date 12 October 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

rotationsstable matchingsstable allocationsunsplittable assignments

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Abstract: The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is "stable" based on a set of underlying preference lists submitted by the jobs and machines. We study a natural "unsplittable" variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem. Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed iby McDermid and Manlove, we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce "relaxed" unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.

Recommendations

• Faster algorithms for stable allocation problems
• On a new algorithm for stable assignment^*
• The Generalized Stable Allocation Problem
• A new algorithm for stable assignments
• Improved Approximation Algorithms for Budgeted Allocations
• A new algorithm for stable assignment
• Exact algorithms for allocation problems
• scientific article; zbMATH DE number 4008097
• An improved approximation algorithm for \textsc{Resource Allocation}
• Improved Algorithms for Weighted and Unweighted Set Splitting Problems

Cites work

• scientific article; zbMATH DE number 437570 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• A PTAS for the multiple subset sum problem with different knapsack capacities
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• College Admissions and the Stability of Marriage
• Deferred acceptance algorithms: history, theory, practice, and open questions
• Faster algorithms for stable allocation problems
• Keeping partners together: Algorithmic results for the hospitals/residents problem with couples
• Matching with couples: a multidisciplinary survey
• On stable matchings and flows
• On the single-source unsplittable flow problem
• Some remarks on the stable matching problem
• The Stable Allocation (or Ordinal Transportation) Problem

Cited in

(2)

• A new algorithm for stable assignment
• A new algorithm for stable assignments

This page was built for publication: Improved algorithmic results for unsplittable stable allocation problems

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