Xi Chen, Erik Waingarten
2019-04-10
We present an
-query algorithm that tests whether an unknown Boolean function is unate (i.e., every variable is either non-decreasing or non-increasing) or -far from unate. The upper bound is nearly optimal given the lower~bound of [CWX17a]. The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda
2019-01-20
We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain to polymer models derived from the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs. In this setting, Jenssen, Keevash and Perkins (2019) recently gave an FPTAS and an efficient sampling algorithm at sufficiently high fugacity and low temperature respectively. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. Our approach via the polymer model Markov chain circumvents the zero-free analysis and the generalization to complex parameters, and leads to a sampling algorithm with a fast running time of
for the Potts model and for the hard-core model, in contrast to typical running times of for algorithms based on Barvinok's polynomial interpolation method on graphs of maximum degree . We finally combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin Glauber dynamics restricted to even and odd or `red' dominant portions of the respective state spaces.
Nikhil Bansal
2018-11-05
We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems where iterated rounding has been useful.
Björn Feldkord, Friedhelm Meyer auf der Heide
2019-04-10
We introduce the mobile server problem, inspired by current trends to move computational tasks from cloud structures to multiple devices close to the end user. An example for this are embedded systems in autonomous cars that communicate in order to coordinate their actions. Our model is a variant of the classical Page Migration Problem. More formally, we consider a mobile server holding a data page. The server can move in the Euclidean space (of arbitrary dimension). In every round, requests for data items from the page pop up at arbitrary points in the space. The requests are served, each at a cost of the distance from the requesting point and the server, and the mobile server may move, at a cost
times the distance traveled for some constant . We assume a maximum distance the server is allowed to move per round. We show that no online algorithm can achieve a competitive ratio independent of the length of the input sequence in this setting. Hence we augment the maximum movement distance of the online algorithms to times the maximum distance of the offline solution. We provide a deterministic algorithm which is simple to describe and works for multiple variants of our problem. The algorithm achieves almost tight competitive ratios independent of the length of the input sequence. Our Algorithm also achieves a constant competitive ratio without resource augmentation in a variant where the distance between two consecutive requests is restricted to a constant smaller than the limit for the server.
Yanchen Deng, Ziyu Chen, Dingding Chen, Xingqiong Jiang, Qiang Li
2019-02-16
Asymmetric Distributed Constraint Optimization Problems (ADCOPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for ADCOPs can only use local knowledge to compute lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e.g., DPOP) for Distributed Constraint Optimization Problems (DCOPs) require only a linear number of messages, but they cannot be directly applied into ADCOPs due to a privacy concern. Therefore, in the paper, we consider the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and a tree-based complete search algorithm to exhaust the search space. We prove the correctness of our algorithm and the experimental results demonstrate its superiority over other state-of-the-art complete algorithms.
Janka Chlebíková, Cristina Bazgan, Clément Dallard, Thomas Pontoizeau
2019-03-15
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time
-approximation algorithm for the problem, where is the maximum degree of the graph. Finally, we prove that all Hamiltonian cubic graphs (except two) have a PDS of the maximum possible size which can be found in linear time if a Hamiltonian cycle is given in input.
Moustafa Nakechbandi, Jean-Yves Colin, Hervé Mathieu
2019-04-10
In this paper, we study weakly dynamic undirected graphs, that can be used to represent some logistic networks. The goal is to deliver all the delivery points in the network. The network exists in a mostly stable environment, except for a few edges known to be non-stable. The weight of each of these non-stable edges may change at any time (bascule or lift bridge, elevator, traffic congestion...). All other edges have stable weights that never change. This problem can be now considered as a Minimum Spanning Tree (MST) problem on a dynamic graph. We propose an efficient polynomial algorithm that computes in advance alternative MSTs for all possible configurations. No additional computation is then needed after any change in the problem because the MSTs are already known in all cases. We use these results to compute critical values for the non-stable weights and to pre-compute best paths. When the non-stable weights change, the appropriate MST may then directly and immediately be used without any recomputation.
Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga
2019-01-29
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string
of length has nodes and edges, and the string label of each edge is encoded by a pair of positions in . Thus, even after the tree is built, the input text needs to be kept stored and random access to is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a stand-alone' alternative to the suffix trees. Namely, the LST of a string  of length  occupies  total space, and supports pattern matching and other tasks in the same efficiency as the suffix tree without the need to store the input text . Crochemore et al. proposed an offline algorithm which transforms the suffix tree of  into the LST of  in  time and  space, where  is the alphabet size. In this paper, we present two types of online algorithms whichdirectly' construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access to the previously read symbols. The right-to-left construction algorithm works intime and space and the left-to-right construction algorithm works in time and space. The main feature of our algorithms is that the input text does not need to be stored.
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki
2019-04-10
The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algorithm for the problem on `almost' planar graphs: Given an
-vertex graph and its drawing with crossings, our algorithm runs in time . Previously, Dahn, Kriege and Mutzel (IWOCA 2018) obtained an algorithm that, given an -vertex graph and its -planar drawing with crossings, runs in time . Our result simultaneously improves the running time and removes the -planarity restriction.
Hsin-Hao Su, Hoa T. Vu
2019-01-02
Vizing showed that it suffices to color the edges of a simple graph using
colors, where is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithms are known for obtaining such a coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized -edge-coloring algorithm that runs in rounds by Chang et al. (SODA '18) and the deterministic -edge-coloring algorithm that runs in rounds by Ghaffari et al. (STOC '18). We present two distributed edge-coloring algorithms that run in rounds. The first algorithm, with randomization, uses only colors. The second algorithm is a deterministic algorithm that uses colors. Our approach is to reduce the distributed edge-coloring problem into an online, restricted version of balls-into-bins problem. If is the maximum load of the bins, our algorithm uses colors. We show how to achieve with randomization and without randomization.
