Abstract: Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, Mohammad R. Salavatipour

Clustering problems are well studied in a variety of fields, such as data science, operations research, and computer science. Such problems include variants of center location problems, k-median and k-means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. For instance, some points may arise from noise in a dataset or one might be willing to discard a certain fraction of the points to avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering problems with outliers. More specifically, we look at uncapacitated facility location (UFL), k-median, and k-means. PubDate: Mon, 18 Feb 2019 00:00:00 GMT

Convergence rate and stability of a solution concept are classically measured in terms of “eventually” and “forever,” respectively. In the wake of recent computational criticisms to this approach, we study whether these timeframes can be updated to have states computed “quickly” and stable for “long enough”. Logit dynamics allows irrationality in players’ behavior and may take time exponential in the number of players n to converge to a stable state (i.e., a certain distribution over pure strategy profiles). We prove that every potential game, for which the behavior of the logit dynamics is not chaotic as n increases, admits distributions stable for a super-polynomial number of steps in n no matter the players’ irrationality and the starting profile of the dynamics. PubDate: Wed, 06 Feb 2019 00:00:00 GMT

Abstract: Nikhil Bansal, Marek Eliéš, Łukasz Jeż, Grigorios Koumoutsos

We study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k-server algorithms are roughly (1+1/ε)-competitive when k=(1+ε) h, for any ε> 0. Surprisingly, however, no o(h)-competitive algorithm is known even for HSTs of depth 2 and even when k/h is arbitrarily large. We obtain several new results for the problem. First, we show that the known k-server algorithms do not work even on very simple metrics. PubDate: Wed, 06 Feb 2019 00:00:00 GMT

Abstract: Veli Mäkinen, Alexandru I. Tomescu, Anna Kuosmanen, Topi Paavilainen, Travis Gagie, Rayan Chikhi

The minimum path cover problem asks us to find a minimum-cardinality set of paths that cover all the nodes of a directed acyclic graph (DAG). We study the case when the size k of a minimum path cover is small, that is, when the DAG has a small width. This case is motivated by applications in pan-genomics, where the genomic variation of a population is expressed as a DAG. We observe that classical alignment algorithms exploiting sparse dynamic programming can be extended to the sequence-against-DAG case by mimicking the algorithm for sequences on each path of a minimum path cover and handling an evaluation order anomaly with reachability queries. PubDate: Wed, 06 Feb 2019 00:00:00 GMT

Abstract: Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k+1 quantifiers takes time O(mk) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O(mk−ε) time for any ε> 0. (Here,>m represents the size of the input structure, i.e., the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to mk/2Θ (√ log n), i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. PubDate: Tue, 18 Dec 2018 00:00:00 GMT

We present a simple deterministic single-pass (2+ε)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves on the currently best known approximation ratio of (4+ε). Our algorithm uses O(nlog2 n) bits of space for constant values of ε. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree G=(V,E), an additional set of edges L ⊑ V× V disjoint from E called links and a cost vector c∈ R≥ 0L, WTAP asks to find a minimum-cost set F⊑ L with the property that (V,E∪ F) is 2-edge connected. The special case where cℓ = 1 for all ℓ ∈ L is called the Tree Augmentation Problem (TAP). For the class of bounded cost vectors, we present the first improved approximation algorithm for WTAP in more than three decades. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

Abstract: David Adjiashvili, Andrea Baggio, Rico Zenklusen

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this article. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

In this article, we show how to compute for n-vertex planar graphs in O(n11/6 polylog(n)) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In O(n15/8 polylog(n)) expected time, we can also compute the number of pairs of vertices at distances smaller than a given threshold. These are the first algorithms for these problems using time O(nc) for some constant c< 2, even when restricted to undirected, unweighted planar graphs. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

Abstract: Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek

The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat: We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

Abstract: Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. PubDate: Fri, 16 Nov 2018 00:00:00 GMT