Tight Approximation Bounds for the Seminar Assignment Problem

DOI10.1007/978-3-319-51741-4_14zbMath1484.68327arXiv1610.04785OpenAlexW2536885665MaRDI QIDQ2971167

George Rabanca, Amotz Bar-Noy

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

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

Related Items

Unnamed Item

Cites Work

• The generalized assignment problem with minimum quantities
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• An efficient approximation for the generalized assignment problem
• A survey of algorithms for the generalized assignment problem
• An approximation algorithm for the generalized assignment problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• A probabilistic analysis of the maximal covering location problem
• A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and Unit Size Items
• Tight approximation algorithms for maximum general assignment problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms