Efficient cost-sharing mechanisms for prize-collecting problems

• 成果类型: Article
• 署名作者: Gupta, A.; Koenemann, J.; Leonardi, S.; Ravi, R.; Schaefer, G.
• 署名单位: Carnegie Mellon University; University of Waterloo; Sapienza University Rome; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0781-1
• 发表日期: 2015
• 页码: 147-188
• 关键词: minimizing submodular functions; forest problems; steiner problem; Network design; approximation; algorithm; hardness; time; TREE

摘要

We consider the problem of designing efficient mechanisms to share the cost of providing some service to a set of self-interested customers. In this paper, we mainly focus on cost functions that are induced by prize-collecting optimization problems. Such cost functions arise naturally whenever customers can be served in two different ways: either by being part of a common service solution or by being served individually. One of our main contributions is a general lifting technique that allows us to extend the social cost approximation guarantee of a Moulin mechanism for the respective non-prize-collecting problem to its prize-collecting counterpart. Our lifting technique also suggests a generic design template to derive Moulin mechanisms for prize-collecting problems. The approach is particularly suited for cost-sharing methods that are based on primal-dual algorithms. We illustrate the applicability of our approach by deriving Moulin mechanisms for prize-collecting variants of submodular cost-sharing, facility location and Steiner forest problems. All our mechanisms are essentially best possible with respect to budget balance and social cost approximation guarantees. Finally, we show that the Moulin mechanism by Konemann et al. (SIAM J Comput 37(5):1319-1341, 2008) for the Steiner forest problem is -approximate. Our approach adds a novel methodological contribution to existing techniques by showing that such a result can be proved by embedding the graph distances into random hierarchically separated trees.