Search

This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this problem, we are given an $n$-point metric space, where requests arrive in an online fashion. The goal is to minimise the matching cost for an even number of requests. However, contrary to traditional online matching problems, a request does not have to be paired immediately at the time of its arrival. Instead, the decision of whether to match a request can be postponed for time $t$ at a delay cost of $t$. For this reason, the goal of the MPMD is to minimise the overall sum of distance and delay costs. Interestingly, for adversarially generated requests, no online algorithm can achieve a competitive ratio better than $O(\log n/\log \log n)$ (Ashlagi et al., APPROX/RANDOM'17). Here, we consider a stochastic version of the MPMD problem where the input requests follow a Poisson arrival process. For such a problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms, which, in expectation, are constant-competitive. The first one is a simple greedy algorithm that matches any two requests once the sum of their delay costs exceeds their connection cost, i.e., the distance between them. The second algorithm builds on the tools used to analyse the first one in order to obtain even better performance guarantees. This result is rather surprising as the greedy approach for the adversarial model achieves a competitive ratio of $\Omega(m^{\log \frac{3}{2}+\varepsilon})$, where $m$ denotes the number of requests served (Azar et al., TOCS'20). Finally, we prove that it is possible to obtain similar results for the general case when the delay cost follows an arbitrary positive and non-decreasing function, as well as for the MPMD variant with penalties to clear pending requests., Comment: 32 pages, 7 figures

We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences. In this paper, we present a $(2+\epsilon)$-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 6. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to $2+\epsilon$. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to $O(1/\epsilon)$ line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR., Comment: 41 pages, updates the previous version which had a 3-approximation algorithm

The greedy approach is natural for the design of algorithms. It is fast, easy to implement, has a good performance on average, and is applicable to many optimization problems in various settings. For those reasons, it is an important heuristic in practice. In this thesis, we present greedy algorithms for three different NP-hard optimization problems. We discuss the relation between those algorithms, their proof techniques and the structure of the problems under study. In the first part of this thesis, we focus on the Maximum Coverage problem with a connectivity constraint, which comes up for the design of wireless networks. We show that the problem is NP-hard, even when the coverage and the connectivity are induced by a set of unit disks in the plane. For that special case, we show that greedily picking two disks so as to maximize the marginal area covered while correctness achieves a 2-approximation. We further improve the approximation ratio by providing a PTAS for this problem with a small resource augmentation, using Arora’s shifted grid dissection technique. In the second part of this thesis, we focus on the Maximum Independent Set problem. A natural approach is to repeatedly pick a vertex of minimum degree, and remove it and its neighbours from the graph. We present a new technique to analyze the performance of this greedy approach in various classes of graphs and address the following question: if there are several minimun-degree vertices, what vertex should the greedy algorithm pick in order to maximise the size of the final solution ? With this tool, we design an ”ultimate tie-breaking” rule that leads to the best possible approximation ratio for sub-cubic graphs and for this type of greedy algorithms. We complement this by lower bound results that show that designing good tie-breaking rules is a difficult task. The third and last part of the thesis is devoted to the Maximum Integral Multiflows problem. The problem is difficult and well-studied. For instance, a constant factor approximation is unlikely to exist even when the supply graph is planar and cubic. In the special case where the supply graph together with the demand edges form a bounded genus graph, we present a constant factor approximation algorithm. The algorithm consists of a succession of greedy procedures that exploit topological properties of graphs and curves on surfaces., L’approche gloutonne est naturelle pour concevoir un algorithme. Elle permet la conception d’algorithmes rapides, faciles à implémenter, qui produisent en moyenne des solutions de qualité, pour de nombreux problèmes d’optimisation. Pour ces raisons, c’est une heuristique importante en pratique. Dans cette thèse, nous présentons des algorithmes gloutons pour trois problèmes d’optimisation NP-difficiles. Nous discutons les relations entre ces algorithmes, leurs techniques de preuve et la structure des problèmes étudiés. Dans la première partie de cette thèse, on se concentre sur le problème de la couverture maximale avec une contrainte de connexité, contrainte que l’on rencontre lors de la conception de réseaux sans fil. Nous montrons que le problème est NP-difficile, même quand la couverture et la connexité proviennent d’un ensemble de disques unité dans le plan. Pour ce cas particulier, nous montrons que choisir de manière gloutonne deux disques qui maximisent le gain marginal tout en maintenant la solution connexe réalise une 2-approximation. Nous améliorons ce ratio d’approximation en donnant un schéma d’approximation en temps polynomial avec une légère augmentation de ressource, basé sur la technique d’Arora pour le voyageur de commerce euclidien. Dans la deuxième partie de cette thèse, on se concentre sur le problème du stable maximum. Une approche naturelle est de successivement choisir un sommet de degré minimum, le placer dans la solution en construction, puis le retirer avec ses voisins du graphe. Nous présentons une nouvelle technique pour analyser la performance de cette approche gloutonne dans différentes classes de graphes et abordons la question suivante : s’il y a plusieurs sommets de degré minimum, lequel l’algorithme devrait-il choisir pour maximiser la taille de la solution finale ? Avec cet outil, nous concevons une règle pour briser les cas d’égalité, qui conduit à la meilleure approximation possible dans les graphes sous-cubiques et pour ce type d’algorithmes gloutons. Nous complémentons ces résultats par des résultats négatifs qui suggèrent que la conception de bonnes règles brisant les cas d’égalité est une tâche difficile. La troisième et dernière partie de la thèse est consacrée au problème du multiflot entier maximum. Ce problème est difficile et a été très étudié. Par exemple, une approximation de facteur constant est probablement impossible même quand le graphe d’offre est planaire et cubique. Dans le cas particulier où le graphe d’offre et les arêtes de demande forment ensemble un graphe de genre borné, nous présentons un algorithme avec un facteur d’approximation constant. L’algorithme consiste en une succession de procédures gloutonnes qui exploitent les propriétés topologiques des graphes et des lacets sur des surfaces.

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles., LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 80:1-80:18

Given a set D of n unit disks in the plane and an integer k

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in a streaming setting. In such a setting, elements arrive sequentially and at any point in time, and the algorithm can store only a small fraction of the elements that have arrived so far. For the special case that all elements have unit sizes (i.e., the cardinality-constraint case), one can find a $$(0.5-\varepsilon )$$ -approximate solution in $$O(K\varepsilon ^{-1})$$ space, where K is the knapsack capacity (Badanidiyuru et al. KDD 2014). The approximation ratio is recently shown to be optimal (Feldman et al. STOC 2020). In this work, we propose a $$(0.4-\varepsilon )$$ -approximation algorithm for the knapsack-constrained problem, using space that is a polynomial of K and $$\varepsilon $$ . This improves on the previous best ratio of $$0.363-\varepsilon $$ with space of the same order. Our algorithm is based on a careful combination of various ideas to transform multiple-pass streaming algorithms into a single-pass one.