Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Joshua Brakensiek, Venkatesan Guruswami
The Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture. This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an “almost Unique” version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we call V Label Cover. PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Christian Coester, Elias Koutsoupias, Philip Lazos
We study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the resource augmentation version of the k-server problem, also known as the (h,k)-server problem, in which an online algorithm with k servers competes against an offline algorithm with h servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the (h,k)-server problem has bounded competitive ratio for some k=O(h). PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran
Finding locally optimal solutions for MAX-CUT and MAX-k-CUT are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for max-cut in complete graphs is (OΦ5n15.1), where Φ is an upper bound on the random edge-weight density and Φ is the number of vertices in the input graph. PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Caterina Viola, Christian Coester
Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over infinite-domains. This extends a result of Brakensiek and Guruswami (SODA’20) for promise (non-valued) CSPs (on finite domains). PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Jacob Focke, Leslie Ann Goldberg, Stanislav Živný
A retraction is a homomorphism from a graph G to an induced subgraph H of G that is the identity on H. In a long line of research, retractions have been studied under various algorithmic settings. Recently, the problem of approximately counting retractions was considered. We give a complete trichotomy for the complexity of approximately counting retractions to all square-free graphs (graphs that do not contain a cycle of length 4). It turns out there is a rich and interesting class of graphs for which this problem is complete in the class #BIS. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi
In this article, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and there is a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, which has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Boris Aronov, Mark De Berg, Joachim Gudmundsson, Michael Horton
Let V be a set of n points in mathcal Rd, called voters. A point p ∈ mathcal Rd is a plurality point for V when the following holds: For every q ∈ mathcal Rd, the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets, a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points, except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0< β ⩽ 1. PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Karl Bringmann, Marvin KüNnemann, André Nusser
The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length n in the plane, the fastest known algorithm runs in time Õ(n5) [12]. This is achieved by constructing an arrangement of disks of size Õ(n4), and then traversing its faces while updating reachability in a directed grid graph of size N := Õ(n5), which can be done in time Õ(√ N) per update [27]. The contribution of this article is two-fold. First, although it is an open problem to solve dynamic reachability in directed grid graphs faster than Õ(√ N), we improve this part of the algorithm: We observe that an offline variant of dynamic s-t-reachability in directed grid graphs suffices, and we solve this variant in amortized time Õ(N1/3) per update, ... PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Daniel Lokshtanov, Andreas BjÖrklund, Saket Saurabh, Meirav Zehavi
Recently, Brand et al. [STOC 2018] gave a randomized mathcal O(4kmε-2-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ε based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner [IWPEC 2009, TALG 2010], and obtain the following results: • We present a deterministic 4k+ O(√k(log k+log2ε-1))m-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. PubDate: Mon, 12 Jul 2021 00:00:00 GMT
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Hybrid journal (It can contain Open Access articles)
[83 journals]
