1 Search Results for "Lam, Chi-Kit"

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.28

Bipartite Matching with Linear Edge Weights

Authors: Nevzat Onur Domanic, Chi-Kit Lam, and C. Gregory Plaxton

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

Consider a complete weighted bipartite graph G in which each left vertex u has two real numbers intercept and slope, each right vertex v has a real number quality, and the weight of any edge (u, v) is defined as the intercept of u plus the slope of u times the quality of v. Let m (resp., n) denote the number of left (resp., right) vertices, and assume that m geq n. We develop a fast algorithm for computing a maximum weight matching (MWM) of such a graph. Our algorithm begins by computing an MWM of the subgraph induced by the n right vertices and an arbitrary subset of n left vertices; this step is straightforward to perform in O(n log n) time. The remaining m - n left vertices are then inserted into the graph one at a time, in arbitrary order. As each left vertex is inserted, the MWM is updated. It is relatively straightforward to process each such insertion in O(n) time; our main technical contribution is to improve this time bound to O(sqrt{n} log^2 n). This result has an application related to unit-demand auctions. It is well known that the VCG mechanism yields a suitable solution (allocation and prices) for any unit-demand auction. The graph G may be viewed as encoding a special kind of unit-demand auction in which each left vertex u represents a unit-demand bid, each right vertex v represents an item, and the weight of an edge (u, v) represents the offer of bid u on item v. In this context, our fast insertion algorithm immediately provides an O(sqrt{n} log^2 n)-time algorithm for updating a VCG allocation when a new bid is received. We show how to generalize the insertion algorithm to update (an efficient representation of) the VCG prices within the same time bound.

Cite as

Nevzat Onur Domanic, Chi-Kit Lam, and C. Gregory Plaxton. Bipartite Matching with Linear Edge Weights. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{domanic_et_al:LIPIcs.ISAAC.2016.28,
  author =	{Domanic, Nevzat Onur and Lam, Chi-Kit and Plaxton, C. Gregory},
  title =	{{Bipartite Matching with Linear Edge Weights}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.28},
  URN =		{urn:nbn:de:0030-drops-67989},
  doi =		{10.4230/LIPIcs.ISAAC.2016.28},
  annote =	{Keywords: Weighted bipartite matching, Unit-demand auctions, VCG allocation and pricing}
}

Refine by Author
1 Domanic, Nevzat Onur
1 Lam, Chi-Kit
1 Plaxton, C. Gregory

Refine by Classification

Refine by Keyword
1 Unit-demand auctions
1 VCG allocation and pricing
1 Weighted bipartite matching

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Lam, Chi-Kit"

Bipartite Matching with Linear Edge Weights

Abstract

Cite as

Thanks for your feedback!

Could not send message