42 citations
- Centre National de la Recherche ScientifiqueFR4 papers
- Sorbonne UniversitéFR2 papers
- Carnegie Mellon UniversityUS1 paper
- Centre d'études et de recherche en informatique et communicationsFR1 paper
- Charles UniversityCZ1 paper
- Chinese University of Hong KongHK1 paper
- Corvinus University of BudapestHU1 paper
- Decision ResearchUS1 paper
- Decision Sciences (United States)US1 paper
- Decision Systems (United States)US1 paper
- Département d'InformatiqueFR1 paper
- École Normale Supérieure - PSLFR1 paper
8 papers · 1 filter
On the Fixed-Parameter Tractability of Capacitated Clustering
Vincent Cohen-Addad, Jason Li
We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best…
Competitive Sequencing with Noisy Advice
Spyros Angelopoulos, Diogo Arsénio, Shahin Kamali
Several well-studied online resource allocation problems can be formulated in terms of infinite, increasing sequences of positive values, in which each element is associated with a…
Online Search with Maximum Clearance
Spyros Angelopoulos, Malachi Voss
We study the setting in which a mobile agent must locate a hidden target in a bounded or unbounded environment, with no information about the hider's position. In particular, we co…
Periodic Scheduling and Packing Problems
Claire Hanen, Zdenek Hanzalek
This paper is motivated by periodic data transmission in autonomous cars. We considered periodic tasks (with different periods) on one or several machines. After reviewing the lite…
Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs
Andreas Emil Feldmann, David Saulpic
We study clustering problems such as k-Median, k-Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It wa…
A Fast Approximation Scheme for Low-Dimensional -Means
Vincent Cohen-Addad
We consider the popular -means problem in -dimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed…