Tight Approximation Bounds for the Seminar Assignment Problem

DOI10.1007/978-3-319-51741-4_14MaRDI QIDQ2971167zbMATH OpenOpenAlexFDO

Authors Amotz Bar-Noy, George Rabanca

Publication date 4 April 2017

Published in Approximation and Online Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

budgeted maximum coveragegeneral assignmentseminar assignment problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Abstract: The seminar assignment problem is a variant of the generalized assignment problem in which items have unit size and the amount of space allowed in each bin is restricted to an arbitrary set of values. The problem has been shown to be NP-complete and to not admit a PTAS. However, the only constant factor approximation algorithm known to date is randomized and it is not guaranteed to always produce a feasible solution. In this paper we show that a natural greedy algorithm outputs a solution with value within a factor of $(1-e^{-1})$ of the optimal, and that unless $NPsubseteqDTIME(n^{loglogn})$, this is the best approximation guarantee achievable by any polynomial time algorithm.

Recommendations

• Tight approximation algorithms for maximum separable assignment problems
• Approximation algorithms for the partial assignment problem
• Lower bounds for the quadratic semi-assignment problem
• Brief announcement: Distributed approximations for the semi-matching problem
• scientific article; zbMATH DE number 5151388
• An efficient approximation for the generalized assignment problem
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem
• An approximation algorithm for the generalized assignment problem

Cites work

• A constant factor approximation for the generalized assignment problem with minimum quantities and unit size items
• A note on maximizing a submodular set function subject to a knapsack constraint
• A probabilistic analysis of the maximal covering location problem
• A survey of algorithms for the generalized assignment problem
• An approximation algorithm for the generalized assignment problem
• An efficient approximation for the generalized assignment problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The budgeted maximum coverage problem
• The generalized assignment problem with minimum quantities
• Tight approximation algorithms for maximum general assignment problems

Cited in

(6)

• Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem
• A constant factor approximation for the generalized assignment problem with minimum quantities and unit size items
• Tight approximation algorithms for maximum separable assignment problems
• Generalized assignment via submodular optimization with reserved capacity
• Online multiset submodular cover
• An efficient algorithm for large-scale dynamic assortment planning problems

This page was built for publication: Tight Approximation Bounds for the Seminar Assignment Problem

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