AF: Small: Algorithms for Matching, Auction, and Scheduling Problems

本研究针对二部匹配问题的有效算法的设计和分析。 加权和未加权的问题进行了研究，以及稳定的匹配变量的基础上顺序的偏好。 动态变量也被认为是这里的目标是快速更新的最优解时，一个小的变化是对input.There是一个密切的联系之间的加权二部匹配和一类组合拍卖称为单位需求拍卖。例如，在密封投标单位需求拍卖中分配和定价项目的问题的一个基本方法涉及计算相应的二分图中的最大权重匹配。 本研究主要探讨多轮投标下单位需求拍卖的设计与分析。 这种“动态”拍卖比密封投标拍卖更难分析，但提供了重要的实际优势。某些调度问题也与二部匹配密切相关。这个项目解决的设计和分析的算法为bipartite matching problems.In尽管几十年的研究组合拍卖，主要的拍卖形式提供给公众拍卖消费品仍然是单一项目的动态第二价格格式，推广由eBay。 本研究旨在设计一个可扩展的基础设施，以支持更具表现力的动态单位需求拍卖类。 这种基础设施的主要潜在好处是提高了经济效率，也就是说，使拍卖物品更好地与最看重这些物品的投标人相匹配。这种效率的提高为社会带来了直接的好处。 此外，在这个项目中解决的匹配和调度问题是基本的性质，并有许多实际应用。

This research addresses the design and analysis of efficient algorithms for bipartite matching problems. Weighted and unweighted problems are investigated, as well as stable matching variants based on ordinal preferences. Dynamic variants are also considered; here the goal is to rapidly update an optimal solution when a small change is made to the input.There is an intimate connection between weighted bipartite matching and a class of combinatorial auctions known as unit-demand auctions. For example, one fundamental approach to the problem of allocating and pricing items in a sealed-bid unit-demand auction involves computing a maximum-weight matching in a corresponding bipartite graph. This project addresses the design and analysis of unit-demand auctions with multiple rounds of bidding. Such "dynamic" auctions are substantially more difficult to analyze than their sealed-bid counterparts, but offer important practical advantages.Certain scheduling problems are also closely related to bipartite matching. This project addresses the design and analysis of algorithms for scheduling-related variants of bipartite matching problems.In spite of decades of research on combinatorial auctions, the predominant auction format available to the general public for auctioning consumer goods remains the single-item dynamic second-price format, as popularized by eBay. This research addresses the design of a scalable infrastructure for supporting the more expressive class of dynamic unit-demand auctions. The key potential benefit of such an infrastructure is enhanced economic efficiency, that is, improved matching of auction items to the bidders who value them the most. Such enhanced efficiency offers direct benefits to society. In addition, the matching and scheduling problems addressed in this project are fundamental in nature and have numerous practical applications.