Abstract
Online Matching has been a problem of considerable interest recently, particularly due to its applicability in Online Ad Allocation. In practice, there are usually multiple objectives which need to be simultaneously optimized, e.g., revenue and quality. We capture this motivation by introducing the problem of Biobjective Online Bipartite Matching. This is a strict generalization of the standard setting. In our problem, the graph has edges of two colors, Red and Blue. The goal is to find a single matching that contains a large number of edges of each color.
We first show how this problem is a departure from previous settings: In all previous problems, the Greedy algorithm gives a non-trivial ratio, typically 1/2. In the biobjective problem, we show that the competitive ratio of Greedy is 0, and in fact, any reasonable algorithm would have to skip vertices, i.e., not match some incoming vertices even though they have an edge available.
As our main result, we introduce an algorithm which randomly discards some edges of the graph in a particular manner – thus enabling the necessary skipping of vertices – and simultaneously runs the color-oblivious algorithm Ranking. We prove that this algorithm achieves a competitive ratio of \(3 - 4/\sqrt{e} \simeq 0.573\) for graphs which have a perfect matching of each color. This beats the upper bound of 1/2 for deterministic algorithms, and comes close to the upper bound of 1 − 1/e ≃ 0.63 for randomized algorithms, both of which we prove carry over to the bicriteria setting, even with the perfect matching restriction. The technical difficulty lies in analyzing the expected minimum number of blue and red edges in the matching (rather than the minimum of the two expectations). To achieve this, we introduce a charging technique which has a new locality property, i.e., misses are charged to nearby hits, according to a certain metric.
Along the way we develop and analyze simpler algorithms for the problem: a deterministic algorithm which achieves a ratio of 0.343, and a simpler randomized algorithm, which achieves, intriguingly, precisely the same ratio.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: SODA (2010)
Azar, P.D., Daskalakis, C., Micali, S., Matthew Weinberg, S.: Optimal and efficient parametric auctions. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, pp. 596–604 (2013)
Bhatnagar, N., Randall, D., Vazirani, V.V., Vigoda, E.: Random bichromatic matchings. Algorithmica 50(4), 418–445 (2008)
Buchbinder, N., Jain, K., Naor, J(S.): Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 253–264. Springer, Heidelberg (2007)
Daskalakis, C., Pierrakos, G.: Simple, optimal and efficient auctions. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 109–121. Springer, Heidelberg (2011)
Diakonikolas, I., Papadimitriou, C., Pierrakos, G., Singer, Y.: Efficiency-revenue trade-offs in auctions. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 488–499. Springer, Heidelberg (2012)
Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., Pál, M.: Online ad assignment with free disposal. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 374–385. Springer, Heidelberg (2009)
Flammini, M., Nicosia, G.: On multicriteria online problems. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 191–201. Springer, Heidelberg (2000)
Karande, C., Mehta, A., Srikant, R.: Optimizing budget constrained spend in search advertising. In: WSDM (2013)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for online bipartite matching. In: STOC (1990)
Karzanov, A.V.: Maximum matching of given weight in complete and complete bipartite graphs. In: Cybernetics and Systems Analysis (1987)
Korula, N., Mirrokni, V.S., Zadimoghaddam, M.: Bicriteria online matching: Maximizing weight and cardinality. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 305–318. Springer, Heidelberg (2013)
Korula, N., Pál, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 508–520. Springer, Heidelberg (2009)
Mehta, A.: Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science 8(4), 265–368 (2013)
Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. In: FOCS (2005)
Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: STOC (1987)
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: FOCS (2000)
Yi, T., Murty, K.G., Spera, C.: Matchings in colored bipartite networks. Discrete Applied Mathematics 121(1), 261–277 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Aggarwal, G., Cai, Y., Mehta, A., Pierrakos, G. (2014). Biobjective Online Bipartite Matching. In: Liu, TY., Qi, Q., Ye, Y. (eds) Web and Internet Economics. WINE 2014. Lecture Notes in Computer Science, vol 8877. Springer, Cham. https://doi.org/10.1007/978-3-319-13129-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-13129-0_16
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13128-3
Online ISBN: 978-3-319-13129-0
eBook Packages: Computer ScienceComputer Science (R0)