Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram
2019-04-26
We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices, so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps using an exact combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.
Xianghui Zhong
2018-09-27
One way to speed up the calculation of optimal TSP tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so several edge elimination approaches have been proposed in the past. In this work we investigate two of them in the scenario where the input consists of
independently distributed random points with bounded density function from above and below by arbitrary positive constants. We show that after the edge elimination procedure of Hougardy and Schroeder the expected number of remaining edges is , while after that of Jonker and Volgenant the expected number of remaining edges is .
Shantanav Chakraborty, Kyle Luh, Jérémie Roland
2019-04-26
The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. We also make novel inroads into a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. This notion of quantum mixing has been explored for a handful of specific graphs and the derived upper bound for this quantity has been faster than its classical counterpart for some graphs while being slower for others. In this article, using several results in random matrix theory, we prove an upper bound on the quantum mixing time of Erd"os-Renyi random graphs: graphs of
nodes where each edge exists with probability independently. For example for dense random graphs, where is a constant, we show that the quantum mixing time is . Consequently, this allows us to obtain an upper bound on the quantum mixing time for \textit{almost all graphs}, i.e.\ the fraction of graphs for which this bound holds, goes to one in the asymptotic limit.
Karoliina Lehtinen, Sven Schewe, Dominik Wojtczak
2019-04-26
Parys has recently proposed a quasi-polynomial version of Zielonka's recursive algorithm for solving parity games. In this brief note we suggest a variation of his algorithm that improves the complexity to meet the state-of-the-art complexity of broadly
, while providing polynomial bounds when the number of colours is logarithmic.
Weiming Feng, Kun He, Xiaoming Sun, Yitong Yin
2019-04-26
The Markov chain Monte Carlo (MCMC) methods are the primary tools for sampling from graphical models, e.g. Markov random fields (MRF). Traditional MCMC sampling algorithms are focused on a classic static setting, where the input is fixed. In this paper we study the problem of sampling from an MRF when the graphical model itself is changing dynamically with time. The problem is well motivated by the growing volume and velocity of data in today's applications of the MCMC methods. For the two major MCMC approaches, respectively for the approximate and perfect sampling, namely, the Gibbs sampling and the coupling from the past (CFTP), we give dynamic versions for the respective MCMC sampling algorithms. On MRF with
variables and bounded maximum degrees, these dynamic sampling algorithms can maintain approximate or perfect samples, while the MRF is dynamically changing. Furthermore, our algorithms are efficient with space cost, and incremental time cost upon each local update to the input MRF, as long as certain decay conditions are satisfied in each step by natural couplings of the corresponding single-site chains. These decay conditions were well known in the literature of couplings for rapid mixing of Markov chains, and now for the first time, are used to imply efficient dynamic sampling algorithms. Consequently, we have efficient dynamic sampling algorithms for the following models: (1) general MRF satisfying the Dobrushin-Shlosman condition (for approximate sampling); (2) Ising model with temperature where (for both approximate and perfect samplings); (3) hardcore model with fugacity (for both approximate and perfect samplings); (4) proper -coloring with: (for approximate sampling); or (for perfect sampling).
Joseph, Naor, Seeun William Umboh, David P. Williamson
2019-04-26
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an
-vertex spanning tree and an additional set of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links such that every terminal pair that has arrived so far is -edge-connected in . This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic -competitive algorithm and showed an lower bound on the competitive ratio of randomized algorithms. The case when is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic -competitive algorithm for online WTAP, which is tight up to constant factors.
Andreas Emil Feldmann
2011-11-29
Two kinds of approximation algorithms exist for the k-BALANCED PARTITIONING problem: those that are fast but compute unsatisfying approximation ratios, and those that guarantee high quality ratios but are slow. In this paper we prove that this tradeoff between runtime and solution quality is necessary. For the problem a minimum number of edges in a graph need to be found that, when cut, partition the vertices into k equal-sized sets. We develop a reduction framework which identifies some necessary conditions on the considered graph class in order to prove the hardness of the problem. We focus on two combinatorially simple but very different classes, namely trees and solid grid graphs. The latter are finite connected subgraphs of the infinite 2D grid without holes. First we use the framework to show that for solid grid graphs it is NP-hard to approximate the optimum number of cut edges within any satisfying ratio. Then we consider solutions in which the sets may deviate from being equal-sized. Our framework is used on grids and trees to prove that no fully polynomial time algorithm exists that computes solutions in which the sets are arbitrarily close to equal-sized. This is true even if the number of edges cut is allowed to increase the more stringent the limit on the set sizes is. These are the first bicriteria inapproximability results for the problem.
Andreas Emil Feldmann
2016-05-09
We consider the
-Center problem and some generalizations. For -Center a set of center vertices needs to be found in a graph with edge lengths, such that the distance from any vertex of to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by Abraham et al. [SODA 2010]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any computing a -approximation is W[2]-hard for parameter and NP-hard for graphs with highway dimension . The latter does not rule out fixed-parameter -approximations for the highway dimension parameter , but implies that such an algorithm must have at least doubly exponential running time in if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of by combining the parameters and : we develop a fixed-parameter -approximation with running time . Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter -approximations for only the parameter . We also provide similar fixed-parameter approximations for the weighted -Center and -Partition problems, which generalize -Center.
Jan-Hendrik Lorenz, Julian Nickerl
2019-04-26
This work analyses the potential of restarts for probSAT, a quite successful algorithm for k-SAT, by estimating its runtime distributions on random 3-SAT instances that are close to the phase transition. We estimate an optimal restart time from empirical data, reaching a potential speedup factor of 1.39. Calculating restart times from fitted probability distributions reduces this factor to a maximum of 1.30. A spin-off result is that the Weibull distribution approximates the runtime distribution for over 93% of the used instances well. A machine learning pipeline is presented to compute a restart time for a fixed-cutoff strategy to exploit this potential. The main components of the pipeline are a random forest for determining the distribution type and a neural network for the distribution's parameters. ProbSAT performs statistically significantly better than Luby's restart strategy and the policy without restarts when using the presented approach. The structure is particularly advantageous on hard problems.
Arturo I. Merino, José A. Soto
2019-04-26
We study the minimum weight basis problem on matroid when elements' weights are uncertain. For each element we only know a set of possible values (an uncertainty area) that contains its real weight. In some cases there exist bases that are uniformly optimal, that is, they are minimum weight bases for every possible weight function obeying the uncertainty areas. In other cases, computing such a basis is not possible unless we perform some queries for the exact value of some elements. Our main result is a polynomial time algorithm for the following problem. Given a matroid with uncertainty areas and a query cost function on its elements, find the set of elements of minimum total cost that we need to simultaneously query such that, no matter their revelation, the resulting instance admits a uniformly optimal base. We also provide combinatorial characterizations of all uniformly optimal bases, when one exists; and of all sets of queries that can be performed so that after revealing the corresponding weights the resulting instance admits a uniformly optimal base.
