## Abstract

In the online matching on the line problem, the task is to match a set of requests R online to a given set of servers S. The distance metric between any two points in is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and – despite recent improvements – there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is -competitive, while the best known deterministic lower bound is 9.001. The lower and upper bounds for randomized algorithms are 4.5 and respectively.

We prove that any deterministic online algorithm which in each round: (i) bases the matching decision only on information local to the current request, and (ii) is symmetric (in the sense that the decision corresponding to the mirror image of some instance I is the mirror image of the decision corresponding to instance I), must be

-competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of on the competitive ratio for a large class of “natural” algorithms. This class includes all deterministic online algorithms found in the literature so far.

Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The

-barrier on the competitive ratio holds for this class of algorithms as well.

We prove that any deterministic online algorithm which in each round: (i) bases the matching decision only on information local to the current request, and (ii) is symmetric (in the sense that the decision corresponding to the mirror image of some instance I is the mirror image of the decision corresponding to instance I), must be

-competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of on the competitive ratio for a large class of “natural” algorithms. This class includes all deterministic online algorithms found in the literature so far.

Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The

-barrier on the competitive ratio holds for this class of algorithms as well.

Original language | English |
---|---|

Title of host publication | LATIN 2018: Theoretical Informatics |

Subtitle of host publication | 13th Latin American Symposium Buenos Aires, Argentina, April 16–19, 2018 Proceedings |

Editors | Michael A. Bender, Martín Farach-Colton, Miguel A. Mosteiro |

Place of Publication | Switzerland |

Publisher | Springer |

Pages | 52–65 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-319-77404-6 |

ISBN (Print) | 978-3-319-77403-9 |

DOIs | |

Publication status | E-pub ahead of print/First online - 13 Mar 2018 |

Externally published | Yes |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 10807 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- n/a OA procedure