Find in Library

In this paper, we consider the online matching problem with two heterogeneous sensors <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>s</mi><mn>1</mn></msub></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>s</mi><mn>2</mn></msub></semantics></math></inline-formula> in a metric space <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>X</mi><mo>,</mo><mi>d</mi><mo>)</mo></mrow></semantics></math></inline-formula>. If a request <i>r</i> is assigned to sensor <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>s</mi><mn>1</mn></msub></semantics></math></inline-formula>, the service cost of <i>r</i> is the distance <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>d</mi><mo>(</mo><mi>r</mi><mo>,</mo><msub><mi>s</mi><mn>1</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula>. Otherwise, <i>r</i> is assigned to sensor <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>s</mi><mn>2</mn></msub></semantics></math></inline-formula>, and the service cost of <i>r</i> is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mrow><mi>d</mi><mo>(</mo><mi>r</mi><mo>,</mo><msub><mi>s</mi><mn>2</mn></msub><mo>)</mo></mrow><mi>w</mi></mfrac></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula> is the weight of sensor <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>s</mi><mn>2</mn></msub></semantics></math></inline-formula>. The goal is to minimize the maximum matching cost, we design an optimal online algorithm with a competitive ratio of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>+</mo><mi>w</mi><mo>+</mo><mfrac><mn>1</mn><mi>w</mi></mfrac></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>w</mi><mo>≤</mo><mn>1.839</mn></mrow></semantics></math></inline-formula>, and an optimal online algorithm with a competitive ratio of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mrow><mi>w</mi><mo>+</mo><mn>1</mn><mo>+</mo><msqrt><mrow><msup><mi>w</mi><mn>2</mn></msup><mo>+</mo><mn>6</mn><mi>w</mi><mo>+</mo><mn>1</mn></mrow></msqrt></mrow><mn>2</mn></mfrac></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mo>></mo><mn>1.839</mn></mrow></semantics></math></inline-formula>.