100 research outputs found
The Covering Canadian Traveller Problem Revisited
No full textIn this paper, we consider the k-Covering Canadian Traveller Problem (k-CCTP), which can be seen as a variant of the Travelling Salesperson Problem. The goal of k-CCTP is finding the shortest tour for a traveller to visit a set of locations in a given graph and return to the origin. Crucially, unknown to the traveller, up to k edges of the graph are blocked and the traveller only discovers blocked edges online at one of their respective endpoints. The currently best known upper bound for k-CCTP is O(√k) which was shown in [Huang and Liao, ISAAC '12]. We improve this polynomial bound to a logarithmic one by presenting a deterministic O(log k)-competitive algorithm that runs in polynomial time. Further, we demonstrate the tightness of our analysis by giving a lower bound instance for our algorithm
Algorithmes en ligne et d'approximation : au-delà des paradigmes pire cas
No full textCette thèse explore le paysage évolutif de l'analyse des algorithmes, des mesures traditionnelles du pire cas au cadre innovant des algorithmes learning augmented. Alors que l'analyse traditionnelle du pire cas a été au cœur des avancées de l'informatique théorique au cours des 50 dernières années, il existe de nombreux problèmes et algorithmes du monde réel pour lesquels l'analyse du pire cas ne fournit pas d'explication convaincante. Un exemple bien connu est le problème de la pagination en ligne, ou de la mise en cache. Dans la mise en cache, l'analyse du pire cas ne peut pas faire la distinction entre les méthodes FIFO et LRU, même si la méthode LRU est clairement supérieure en pratique. Cela sert de motivation pour explorer des approches qui vont au-delà de l'analyse du pire cas avec un accent particulier sur le domaine émergent des algorithmes avec prédictions (algorithmes learning augmented), qui a été inspiré par les progrès récents de la communauté de l'apprentissage automatique. Les algorithmes d'apprentissage automatique ont la capacité d'apprendre à partir de données passées et d'exploiter les modèles sous-jacents dans le domaine d'application, conduisant à des solutions étonnamment efficaces. Dans le cadre learning augmented, on conçoit des algorithmes qui fonctionnent en conjonction avec un modèle d'apprentissage automatique en boîte noire, qui leur fournit des informations prédictives sur les données. Étant donné que ces prédictions peuvent être sujettes à des erreurs, l'algorithme doit les gérer avec soin, une tâche qui introduit divers défis. Le cœur de notre travail réside dans les algorithmes en ligne, qui doivent prendre des décisions sans connaissance complète de la séquence d'entrée. Nous commençons par un problème purement en ligne qui illustre la nécessité d'une analyse au-delà du pire des cas. Le chapitre suivant explore une nouvelle variante d'un problème en ligne classique qui donne plus de puissance à l'algorithme en ligne en fournissant des informations supplémentaires sur l'entrée. Dans les deux chapitres suivants, nous étudions deux problèmes en ligne différents à travers le prisme des algorithmes learning augmented. Nous concevons des algorithmes utilisant des prédictions qui surmontent les barrières computationnelles connues lorsque les prédictions sont suffisamment précises. Même lorsque les prédictions sont mauvaises, nos algorithmes maintiennent toujours des garanties du pire des cas qui sont proches des meilleures garanties réalisables sans prédictions. Enfin, nous introduisons des schémas d'approximation learning augmented pour les problèmes d'optimisation NP-difficiles. Nous montrons que même un petit nombre de prédictions suffit à améliorer le temps d'exécution d'algorithmes d'approximation bien connus, dépassant les limites de calcul connues de l'analyse du pire cas.This thesis explores the evolving landscape of algorithm analysis, from the traditional worst-case metrics to the innovative framework of learning-augmented algorithms. While traditional worst-case analysis has been the core of advancements in theoretical computer science over the past 50 years, there are many real-world problems and algorithms for which worst-case analysis does not provide a convincing explanation. A well-known example is the online paging problem, or caching. In caching, worst-case analysis cannot distinguish between the FIFO and LRU methods, even though the LRU method is clearly superior in practice. This serves as a motivation to explore approaches that go beyond worst-case analysis with a particular focus on the emerging field of algorithms with predictions (learning-augmented algorithms), which has been inspired by the recent progress in the machine learning community. Machine learning algorithms have the ability to learn from past data and exploit underlying patterns in the application domain, leading to surprisingly effective solutions. In the learning-augmented framework, one designs algorithms that work in conjunction with a black-box machine learning model, which provides them with predictive information about the data. Since these predictions can be error-prone, the algorithm must handle them with care, a task that introduces various challenges. The core of our work lies in online algorithms, which must make decisions without complete knowledge of the input sequence. We begin with a purely online problem that illustrates the necessity for beyond worst-case analysis. The subsequent chapter explores a new variant of a classical online problem that gives more power to the online algorithm by providing additional information about the input. In the next two chapters, we study two different online problems through the lens of learning-augmented algorithms. We design algorithms using predictions that overcome known computational barriers when the predictions are accurate enough. Even when the predictions are bad, our algorithms still maintain worst-case guarantees that are close to the best achievable guarantees without predictions. Finally, we introduce learning-augmented approximation schemes for NP-hard optimization problems. We show that even a small number of predictions suffices to improve the running time of well-known approximation algorithms, surpassing known computational limits of worst-case analysis
Algorithmes en ligne et d'approximation : au-delà des paradigmes pire cas
No full textThis thesis explores the evolving landscape of algorithm analysis, from the traditional worst-case metrics to the innovative framework of learning-augmented algorithms. While traditional worst-case analysis has been the core of advancements in theoretical computer science over the past 50 years, there are many real-world problems and algorithms for which worst-case analysis does not provide a convincing explanation. A well-known example is the online paging problem, or caching. In caching, worst-case analysis cannot distinguish between the FIFO and LRU methods, even though the LRU method is clearly superior in practice. This serves as a motivation to explore approaches that go beyond worst-case analysis with a particular focus on the emerging field of algorithms with predictions (learning-augmented algorithms), which has been inspired by the recent progress in the machine learning community. Machine learning algorithms have the ability to learn from past data and exploit underlying patterns in the application domain, leading to surprisingly effective solutions. In the learning-augmented framework, one designs algorithms that work in conjunction with a black-box machine learning model, which provides them with predictive information about the data. Since these predictions can be error-prone, the algorithm must handle them with care, a task that introduces various challenges. The core of our work lies in online algorithms, which must make decisions without complete knowledge of the input sequence. We begin with a purely online problem that illustrates the necessity for beyond worst-case analysis. The subsequent chapter explores a new variant of a classical online problem that gives more power to the online algorithm by providing additional information about the input. In the next two chapters, we study two different online problems through the lens of learning-augmented algorithms. We design algorithms using predictions that overcome known computational barriers when the predictions are accurate enough. Even when the predictions are bad, our algorithms still maintain worst-case guarantees that are close to the best achievable guarantees without predictions. Finally, we introduce learning-augmented approximation schemes for NP-hard optimization problems. We show that even a small number of predictions suffices to improve the running time of well-known approximation algorithms, surpassing known computational limits of worst-case analysis.Cette thèse explore le paysage évolutif de l'analyse des algorithmes, des mesures traditionnelles du pire cas au cadre innovant des algorithmes learning augmented. Alors que l'analyse traditionnelle du pire cas a été au cœur des avancées de l'informatique théorique au cours des 50 dernières années, il existe de nombreux problèmes et algorithmes du monde réel pour lesquels l'analyse du pire cas ne fournit pas d'explication convaincante. Un exemple bien connu est le problème de la pagination en ligne, ou de la mise en cache. Dans la mise en cache, l'analyse du pire cas ne peut pas faire la distinction entre les méthodes FIFO et LRU, même si la méthode LRU est clairement supérieure en pratique. Cela sert de motivation pour explorer des approches qui vont au-delà de l'analyse du pire cas avec un accent particulier sur le domaine émergent des algorithmes avec prédictions (algorithmes learning augmented), qui a été inspiré par les progrès récents de la communauté de l'apprentissage automatique. Les algorithmes d'apprentissage automatique ont la capacité d'apprendre à partir de données passées et d'exploiter les modèles sous-jacents dans le domaine d'application, conduisant à des solutions étonnamment efficaces. Dans le cadre learning augmented, on conçoit des algorithmes qui fonctionnent en conjonction avec un modèle d'apprentissage automatique en boîte noire, qui leur fournit des informations prédictives sur les données. Étant donné que ces prédictions peuvent être sujettes à des erreurs, l'algorithme doit les gérer avec soin, une tâche qui introduit divers défis. Le cœur de notre travail réside dans les algorithmes en ligne, qui doivent prendre des décisions sans connaissance complète de la séquence d'entrée. Nous commençons par un problème purement en ligne qui illustre la nécessité d'une analyse au-delà du pire des cas. Le chapitre suivant explore une nouvelle variante d'un problème en ligne classique qui donne plus de puissance à l'algorithme en ligne en fournissant des informations supplémentaires sur l'entrée. Dans les deux chapitres suivants, nous étudions deux problèmes en ligne différents à travers le prisme des algorithmes learning augmented. Nous concevons des algorithmes utilisant des prédictions qui surmontent les barrières computationnelles connues lorsque les prédictions sont suffisamment précises. Même lorsque les prédictions sont mauvaises, nos algorithmes maintiennent toujours des garanties du pire des cas qui sont proches des meilleures garanties réalisables sans prédictions. Enfin, nous introduisons des schémas d'approximation learning augmented pour les problèmes d'optimisation NP-difficiles. Nous montrons que même un petit nombre de prédictions suffit à améliorer le temps d'exécution d'algorithmes d'approximation bien connus, dépassant les limites de calcul connues de l'analyse du pire cas
Author Correction: RNAs coordinate nuclear envelope assembly and DNA replication through ELYS recruitment to chromatin
No full textIn the original version of this Article, the affiliation details for Antoine Aze, Michalis Fragkos, Stéphane Bocquet, Julien Cau and Marcel Méchali incorrectly omitted ‘CNRS and the University of Montpellier’. This has now been corrected in both the PDF and HTML versions of the Article.</jats:p
A child of the Academy? : investigating Euclid's philosophical background
No full textA prevalent idea among contemporary scholars is that Euclid belonged to, or was heavily influenced by the Platonic philosophical tradition. To a certain extent, this impression is not new; the quest for Euclid's philosophical background was probably triggered and enhanced by his late commentators, Greeks and Arabs, who appear confident that he had one. For instance, al-Qifti writes: 'Euclid...called the author of geometry, a philosopher of somewhat ancient date...' and al-Nadim in the Fihrist names Euclid as '...one of the mathematical philosophers...' Proclus, five centuries earlier than al-Nadim, was more specific: '[Euclid] was a follower of Plato by choice, and familiar with this philosophy'. In this paper, I propose to explore the extant accounts on Euclid's philosophical background. (Michalis Sialaros, University of London
Post - Independence Cypriot Dramaturgy (1960 Onwards)
No full textHow did playwriting evolve in Cyprus since independence (1960 and afterwards)? There is a systematic absence of studies on the subject. The author of this article analyzes the work of some of the most important playwrights of the period (Rina Katselli, Michalis Pitsillidis, Panos Ioannidis, Michalis Pasiardis and Yiorgos Neophytou) and describes their main carcteristics. Even though the writers of the 1960s continue to write in the naturalistic mode, others courageously follow more contemporary trends.How did playwriting evolve in Cyprus since independence (1960 and afterwards)? There is a systematic absence of studies on the subject. The author of this article analyzes the work of some of the most important playwrights of the period (Rina Katselli, Michalis Pitsillidis, Panos Ioannidis, Michalis Pasiardis and Yiorgos Neophytou) and describes their main carcteristics. Even though the writers of the 1960s continue to write in the naturalistic mode, others courageously follow more contemporary trends.Comment évolue l’écriture théâtrale pendant la période de l’indépendance (depuis 1960)? Il n’existe pas d’études systématiques sur ce sujet. Dans cet article sont analysées des œuvres de quelques auteurs dramatiques les plus représentatifs (Rina Katselli, Michalis Pitsillidis, Panos Ioannidis, Michalis Pasiardis et Yiorgos Neophytou) et sont résumées les lignes directrices de leur œuvre. Bien que les auteurs de la décennie 1960 continuent de créer en suivant la tradition du théâtre éthographique (théâtre de mœurs), on assiste à des efforts plus audacieux, qui tendent à une écriture théâtrale plus contemporaine
Canadian Traveller Problem with Predictions
No full textIn this work, we consider the -Canadian Traveller Problem (-CTP) under
the learning-augmented framework proposed by Lykouris & Vassilvitskii. -CTP
is a generalization of the shortest path problem, and involves a traveller who
knows the entire graph in advance and wishes to find the shortest route from a
source vertex to a destination vertex , but discovers online that some
edges (up to ) are blocked once reaching them. A potentially imperfect
predictor gives us the number and the locations of the blocked edges.
We present a deterministic and a randomized online algorithm for the
learning-augmented -CTP that achieve a tradeoff between consistency (quality
of the solution when the prediction is correct) and robustness (quality of the
solution when there are errors in the prediction). Moreover, we prove a
matching lower bound for the deterministic case establishing that the tradeoff
between consistency and robustness is optimal, and show a lower bound for the
randomized algorithm. Finally, we prove several deterministic and randomized
lower bounds on the competitive ratio of -CTP depending on the prediction
error, and complement them, in most cases, with matching upper bounds
Improved FPT Approximation for Non-metric TSP
No full textIn the Traveling Salesperson Problem (TSP) we are given a list of locations and the distances between each pair of them. The goal is to find the shortest possible tour that visits each location exactly once and returns to the starting location. Inspired by the fact that general TSP cannot be approximated in polynomial time within any constant factor, while metric TSP admits a (slightly better than) -approximation in polynomial time, Zhou, Li and Guo [Zhou et al., ISAAC \u2722] introduced a parameter that measures the distance of a given TSP instance from the metric case. They gave an FPT -approximation algorithm parameterized by , where is the number of triangles in which the edge costs violate the triangle inequality. In this paper, we design a -approximation algorithm that runs in FPT time, improving the result of [Zhou et al., ISAAC \u2722]
Parsimonious Learning-Augmented Approximations for Dense Instances of -hard Problems
No full textThe classical work of (Arora et al., 1999) provides a scheme that gives, for
any , a polynomial time approximation algorithm for
dense instances of a family of -hard problems, such as Max-CUT
and Max--SAT. In this paper we extend and speed up this scheme using a
logarithmic number of one-bit predictions. We propose a learning augmented
framework which aims at finding fast algorithms which guarantees approximation
consistency, smoothness and robustness with respect to the prediction error. We
provide such algorithms, which moreover use predictions parsimoniously, for
dense instances of various optimization problems
Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else
No full textWe study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric space. The goal is, starting from a particular point of the metric space (the origin), to serve all these requests while minimizing the total time spent. The server moves with unit speed or is "waiting" (zero speed) at some location. We consider two variants: in the open variant, the goal is achieved when the last request is served. In the closed one, the server additionally has to return to the origin. We adopt a prediction model, introduced for OLTSP on the line [Gouleakis et al., 2023], in which the predictions correspond to the locations of the requests and extend it to more general metric spaces.
We first propose an oracle-based algorithmic framework, inspired by previous work [Bampis et al., 2023]. This framework allows us to design online algorithms for general metric spaces that provide competitive ratio guarantees which, given perfect predictions, beat the best possible classical guarantee (consistency). Moreover, they degrade gracefully along with the increase in error (smoothness), but always within a constant factor of the best known competitive ratio in the classical case (robustness).
Having reduced the problem to designing suitable efficient oracles, we describe how to achieve this for general metric spaces as well as specific metric spaces (rings, trees and flowers), the resulting algorithms being tractable in the latter case. The consistency guarantees of our algorithms are tight in almost all cases, and their smoothness guarantees only suffer a linear dependency on the error, which we show is necessary. Finally, we provide robustness guarantees improving previous results
- …
