{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T10:41:15Z","timestamp":1762080075301,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T00:00:00Z","timestamp":1670544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["12071417"],"award-info":[{"award-number":["12071417"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>In this paper, we consider the online matching problem with two heterogeneous sensors s1 and s2 in a metric space (X,d). If a request r is assigned to sensor s1, the service cost of r is the distance d(r,s1). Otherwise, r is assigned to sensor s2, and the service cost of r is d(r,s2)w, where w\u22651 is the weight of sensor s2. The goal is to minimize the maximum matching cost, we design an optimal online algorithm with a competitive ratio of 1+w+1w for 1\u2264w\u22641.839, and an optimal online algorithm with a competitive ratio of w+1+w2+6w+12 for w&gt;1.839.<\/jats:p>","DOI":"10.3390\/computation10120217","type":"journal-article","created":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T03:02:37Z","timestamp":1670814157000},"page":"217","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Bottleneck Matching Problem with Two Heterogeneous Sensors in a Metric Space"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2443-6768","authenticated-orcid":false,"given":"Man","family":"Xiao","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming 650504, China"}]},{"given":"Yaru","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming 650504, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3094-4347","authenticated-orcid":false,"given":"Weidong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming 650504, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1006\/jagm.1993.1026","article-title":"Online weighted matching","volume":"14","author":"Kalyanasundaram","year":"1993","journal-title":"J. Algorithms"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","article-title":"On-line algorithms for weighted bipartite matching and stable marriages","volume":"127","author":"Khuller","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Nanavati, A., and Poplawski, L. (2006, January 22\u201324). Randomized online algorithms for minimum metric bipartite matching. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), Miami, FL, USA.","DOI":"10.1145\/1109557.1109662"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","article-title":"A randomized O(log2 k)-competitive algorithm for metric bipartite matching","volume":"68","author":"Bansal","year":"2014","journal-title":"Algorithmica"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Gupta, A., and Lewi, K. (2012, January 9\u201313). The online metric matching problem for doubling metrics. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), Warwick, UK.","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.tcs.2004.10.028","article-title":"Online matching on a line","volume":"332","author":"Fuchs","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2917","DOI":"10.1007\/s00453-019-00565-w","article-title":"A o(n)-competitive deterministic algorithm for online matching on a line","volume":"81","author":"Antoniadis","year":"2019","journal-title":"Algorithmica"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Nayyar, K., and Raghvendra, S. (2017, January 15\u201317). An input sensitive online algorithm for the metric bipartite matching problem. Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2017.53"},{"key":"ref_9","unstructured":"Raghvendra, S. (2016, January 16\u201318). A robust and optimal online algorithm for minimum metric bipartite matching. Proceedings of the International Conference on Approximation, Randomization, and Combinatorial Optimization\u2014Algorithms and Techniques (APPROX\/RANDOM 2016), Seattle, WA, USA."},{"key":"ref_10","unstructured":"Raghvendra, S. (2017, January 14\u201317). Optimal analysis of an online algorithm for the bipartite matching problem on a line. Proceedings of the 34th International Symposium on Computational Geometry, College Park, MD, USA."},{"key":"ref_11","unstructured":"Peserico, E., and Scquizzato, M. (2021, January 12\u201316). Matching on the line admits no o(log\u00a0n)-competitive algorithm. Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), Glasgow, Scotland."},{"key":"ref_12","unstructured":"Idury, R., and Schaffer, A.A. (2022, September 29). A Better Lower Bound for On-Line Bottleneck Matching. Manuscript, Available online: http:\/\/www.ncbi.nlm.nih.gov\/core\/assets\/cbb\/files\/Firehouse.pdf."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/s10878-012-9581-9","article-title":"Online bottleneck matching","volume":"27","author":"Anthony","year":"2014","journal-title":"J. Comb. Optim."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1137\/S0895480198342310","article-title":"The online transportation problem","volume":"13","author":"Kalyanasundaram","year":"2000","journal-title":"SIAM J. Discret. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.tcs.2019.08.011","article-title":"Online facility assignment","volume":"806","author":"Ahmed","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2150156","DOI":"10.1142\/S1793830921501561","article-title":"Competitive analysis for two variants of online metric matching problem","volume":"13","author":"Itoh","year":"2021","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Xiao, M., and Li, W.D. (2022, January 22\u201324). Online semi-matching problem with two heterogeneous sensors in a metric space. Proceedings of the 28th International Computing and Combinatorics Conference (COCOON), Shenzhen, China.","DOI":"10.1007\/978-3-031-22105-7_39"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Xiao, M., Zhao, S., Li, W.D., and Yang, J.H. (2021, January 17\u201319). Online Bottleneck Semi-matching. Proceedings of the 15th Annual International Conference on Combinatorial Optimization and Applications (COCOA), Tianjin, China.","DOI":"10.1007\/978-3-030-92681-6_35"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/10\/12\/217\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:37:34Z","timestamp":1760146654000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/10\/12\/217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,9]]},"references-count":18,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["computation10120217"],"URL":"https:\/\/doi.org\/10.3390\/computation10120217","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2022,12,9]]}}}