Zobrazeno 1 - 6
of 6
pro vyhledávání: '"Baligacs, Julia"'
Autor:
Baligács, Júlia, MacManus, Joseph
We study a generalization of the well-known disjoint paths problem which we call the metric Menger problem, denoted MM(r,k), where one is given two subsets of a graph and must decide whether they can be connected by $k$ paths of pairwise distance at
Externí odkaz:
http://arxiv.org/abs/2403.05630
In the Tricolored Euclidean Traveling Salesperson problem, we are given~$k=3$ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on ``patching'' for the case $k=1$ an
Externí odkaz:
http://arxiv.org/abs/2402.13938
Autor:
Alidou, Abdou Majeed, Baligács, Júlia, Hahn-Klimroth, Max, Hązła, Jan, Hintze, Lukas, Scheftelowitsch, Olga
Polarization and unexpected correlations between opinions on diverse topics (including in politics, culture and consumer choices) are an object of sustained attention. However, numerous theoretical models do not seem to convincingly explain these phe
Externí odkaz:
http://arxiv.org/abs/2402.08446
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to
Externí odkaz:
http://arxiv.org/abs/2308.06823
Publikováno v:
LNCS volume 13538 (2022) 154-171
We consider the open online dial-a-ride problem, where transportation requests appear online in a metric space and need to be served by a single server. The objective is to minimize the completion time until all requests have been served. We present
Externí odkaz:
http://arxiv.org/abs/2210.13854
In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on
Externí odkaz:
http://arxiv.org/abs/2210.13850