标题： 带有完全分配和度约束的第二价格匹配 显示英文标题

标题： Second Price Matching with Complete Allocation and Degree Constraints

摘要： 我们研究了由Azar、Birnbaum、Karlin和Nguyen在2009年提出的Second Price Matching问题。在这个问题中，给定一个二分图（竞标者和商品），匹配的利润是包含一个未匹配竞标者的匹配数量。最大化利润已被证明是APX难的，目前最好的近似保证是$1/2$。即使所有度数都被常数限制，APX难性仍然成立。在本文中，我们研究了在正则度约束下的该问题的近似性。我们的主要结果是，在$(3,2)$正则图中Second Price Matching的改进近似保证为$9/10$，以及在$(d,2)$正则图中如果$d\geq 4$，则有一个精确的多项式时间算法。我们的算法及其分析基于非二分匹配中的结构结果，特别是Tutte-Berge公式结合新颖的组合增强方法。我们还引入了一个Second Price Matching的变体，其中所有商品都必须被匹配，这模拟了到期商品的情况。我们证明了这个问题在优于$(1-1/e)$因子内难以近似，并表明通过在matroid约束下最大化一个子模函数，可以将该问题近似到紧密的$(1-1/e)$因子。然后我们表明，我们的算法也可以在上述的正则度约束图上精确解决这个问题。 显示英文摘要

摘要： We study the Second Price Matching problem, introduced by Azar, Birnbaum, Karlin, and Nguyen in 2009. In this problem, a bipartite graph (bidders and goods) is given, and the profit of a matching is the number of matches containing a second unmatched bidder. Maximizing profit is known to be APX-hard and the current best approximation guarantee is $1/2$. APX-hardness even holds when all degrees are bounded by a constant. In this paper, we investigate the approximability of the problem under regular degree constraints. Our main result is an improved approximation guarantee of $9/10$ for Second Price Matching in $(3,2)$-regular graphs and an exact polynomial-time algorithm for $(d,2)$-regular graphs if $d\geq 4$. Our algorithm and its analysis are based on structural results in non-bipartite matching, in particular the Tutte-Berge formula coupled with novel combinatorial augmentation methods. We also introduce a variant of Second Price Matching where all goods have to be matched, which models the setting of expiring goods. We prove that this problem is hard to approximate within a factor better than $(1-1/e)$ and show that the problem can be approximated to a tight $(1-1/e)$ factor by maximizing a submodular function subject to a matroid constraint. We then show that our algorithm also solves this problem exactly on regular degree constrained graphs as above.