January 25, 2020

Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s,t)-Cuts

  • Bergé P.
  • Salaun L.

The k-Canadian Traveller Problem consists in finding the optimal way from a source s to a target t on an undirected weighted graph G, knowing that at most k edges are blocked. The traveller, guided by a strategy, sees an edge is blocked when he visits one of its endpoints. A major result established by Westphal is that the competitive ratio of any deterministic strategy for this problem is at least 2k+1. Reposition and Comparison strategies achieve this bound. We refine this analysis by focusing on graphs with a maximum (s,t)-cut size mumax less than k. A strategy called Detour is proposed and its competitive ratio is 2mumax + sqrt{2}(k-mumax) + 1 when mumax < k which is strictly less than 2k+1. Moreover, when mumax >= k, the competitive ratio of Detour is 2k+1 and is optimal. Therefore, Detour improves the competitiveness of the deterministic strategies known up to now.

View Original Article

Recent Publications

August 01, 2019

Protecting photonic quantum states using topology

  • Blanco-Redondo A.

The use of topology to protect quantum information is well-known to the condensed-matter community and, indeed, topological quantum computing is a bursting field of research and one of the competing avenues to demonstrate that quantum computers can complete certain problems that classical computers cannot. In photonics, however, we are only ...

May 01, 2019

Digital networks at the nexus of productivity growth

  • Kamat S.
  • Prakash S.
  • Saniee I.
  • Weldon M.

This paper takes a fresh look at the debate over the relationship between digital technology and productivity. The argument of economic historian Robert J. Gordon is that digital technology will not lead to increases in productivity such as we saw in the last century, based on his analysis of the ...

January 01, 2019

Friendly, appealing or both? Characterising user experience in sponsored search landing pages

  • Bron M.
  • Chute M.
  • Evans H.
  • Lalmas M.
  • Redi M.
  • Silvestri F.

© 2017 International World Wide Web Conference Committee (IW3C2), published under Creative Commons CC BY 4.0 License. Many of today's websites have recognised the importance of mobile friendly pages to keep users engaged and to provide a satisfying user experience. However, next to the experience provided by the sites themselves, ...