Bicriteria Online Matching: Maximizing Weight and Cardinality

详细信息    查看全文

• 作者：Nitish Korula (18)
  Vahab S. Mirrokni (18)
  Morteza Zadimoghaddam (19)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8289
• 期：1
• 页码：319-332
• 全文大小：281KB
• 作者单位：Nitish Korula (18)
  Vahab S. Mirrokni (18)
  Morteza Zadimoghaddam (19)
  
  18. Google Research, New York, NY, 10011, USA
  19. Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
  
• ISSN：1611-3349

文摘

Inspired by online ad allocation problems, many results have been developed for online matching problems. Most of the previous work deals with a single objective, but, in practice, there is a need to optimize multiple objectives. Here, as an illustrative example motivated by display ads allocation, we study a bi-objective online matching problem. In particular, we consider a set of fixed nodes (ads) with capacity constraints, and a set of online items (pageviews) arriving one by one. Upon arrival of an online item i, a set of eligible fixed neighbors (ads) for the item is revealed, together with a weight w ia for eligible neighbor a. The problem is to assign each item to an eligible neighbor online, while respecting the capacity constraints; the goal is to maximize both the total weight of the matching and the cardinality. In this paper, we present both approximation algorithms and hardness results for this problem. An ( -approximation for this problem is a matching with weight at least fraction of the maximum weighted matching, and cardinality at least fraction of maximum cardinality matching. We present a parametrized approximation algorithm that allows a smooth tradeoff curve between the two objectives: when the capacities of fixed nodes are large, we give a p(11/e 1/p ), (1p)(11/e 1/1p )-approximation for any 0p1, and prove a ardness curvecombining several inapproximability results. These upper and lower bounds are always close (with a maximum gap of 9%), and exactly coincide at the point (0.43, 0.43). For small capacities, we present a smooth parametrized approximation curve for the problem between (0,11/e) and (1/2,0) passing through a (1/3,0.3698)-approximation.