Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc
2019-04-19
We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching. Such stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight
-competitiveness for the random-order arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of has long been conjectured and remains a tantalizing open question. In this paper, we show improved results in the i.i.d arrival model. We show how the i.i.d model can be used to give substantially better algorithms: our main result is an -competitive algorithm in this model. Along the way we give a -competitive algorithm for the line and tree metrics. Both results imply a strict separation between the i.i.d model and the adversarial and random order models, both for general metrics and these much-studied metrics.
Eduardo Castelló Ferrer, Thomas Hardjono, Alex, Pentland
2019-04-19
Swarm robotics systems are envisioned to become an important component of both academic research and real-world applications. However, in order to reach widespread adoption, new models that ensure the secure cooperation of these systems need to be developed. This work proposes a novel model to encapsulate cooperative robotic missions in Merkle trees, one of the fundamental components of blockchain technology. With the proposed model, swarm operators can provide the "blueprint" of the swarm's mission without disclosing raw data about the mission itself. In other words, data verification can be separated from data itself. We propose a system where swarm robots have to "prove" their integrity to their peers by exchanging cryptographic proofs. This work analyzes and tests the proposed approach for two different robotic missions: foraging (where robots modify the environment) and maze formation (where robots become part of the environment). In both missions, robots were able to cooperate and carry out sequential operations in the correct order without having explicit knowledge about the mission's high-level goals or objectives. The performance, communication costs, and information diversity requirements for the proposed approach are analyzed. Finally, conclusions are drawn and future work directions are suggested.
Zhize Li
2019-04-19
We analyze stochastic gradient algorithms for optimizing nonconvex problems. In particular, our goal is to find local minima (second-order stationary points) instead of just finding first-order stationary points which may be some bad unstable saddle points. We show that a simple perturbed version of stochastic recursive gradient descent algorithm (called SSRGD) can find an
-second-order stationary point with stochastic gradient complexity for nonconvex finite-sum problems. As a by-product, SSRGD finds an -first-order stationary point with stochastic gradients. These results are almost optimal since Fang et al. [2018] provided a lower bound for finding even just an -first-order stationary point. We emphasize that SSRGD algorithm for finding second-order stationary points is as simple as for finding first-order stationary points just by adding a uniform perturbation sometimes, while all other algorithms for finding second-order stationary points with similar gradient complexity need to combine with a negative-curvature search subroutine (e.g., Neon2 [Allen-Zhu and Li, 2018]). Moreover, the simple SSRGD algorithm gets a simpler analysis. Besides, we also extend our results from nonconvex finite-sum problems to nonconvex online (expectation) problems, and prove the corresponding convergence results.
Jasper C. H. Lee, Paul Valiant
2019-04-19
Given a mixture between two populations of coins, "positive" coins that have (unknown and potentially different) probabilities of heads
and negative coins with probabilities , we consider the task of estimating the fraction of coins of each type to within additive error . We introduce new techniques to show a fully-adaptive lower bound of samples (for constant probability of success). We achieve almost-matching algorithmic performance of samples, which matches the lower bound except in the regime where . The fine-grained adaptive flavor of both our algorithm and lower bound contrasts with much previous work in distributional testing and learning.
Ilan Reuven Cohen, Binghui Peng, David Wajc
2019-04-19
Vizing's celebrated theorem asserts that any graph of maximum degree
admits an edge coloring using at most colors. In contrast, Bar-Noy, Naor and Motwani showed over a quarter century that the trivial greedy algorithm, which uses colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with , and they conjectured the existence of online algorithms using colors for . Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS'03 and Bahmani et al., SODA'10). We resolve the above conjecture for \emph{adversarial} vertex arrivals in bipartite graphs, for which we present a -edge-coloring algorithm for known a priori. Surprisingly, if is not known ahead of time, we show that no -edge-coloring algorithm exists. We then provide an optimal, -edge-coloring algorithm for unknown . Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.
Valery Shchesnovich
2019-04-03
The classical complexity of sampling from the probability distribution of quantum interference of
indistinguishable single bosons on unitary network with input and output ports is studied with the focus on how boson density for affects the number of computations required to produce a single sample. First, Glynn's formula is modified for computation of probabilities of output configurations with output ports occupied by bosons, requiring only computations. Second, it is found that in a unitary network chosen according to the Haar probability measure the tails of the distribution of the total number of output ports occupied by bosons are bounded by those of a binomial distribution. This fact allows to prove that for any with probability the number of computations scales at least as and at most as , where and . These bounds apply also to the leading order of the number of classical computations in the sampling algorithm of P. Clifford and R.Clifford, which is based on Glynn's formula and applies uniformly over the output configurations.
Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd
2019-04-19
While there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems. We develop new techniques for attacking these problems inspired by the continuous greedy method applied to the multi-linear extension of a submodular function. We first adapt the continuous greedy algorithm to work for general twice-continuously differentiable functions. The performance of the adapted algorithm depends on a new smoothness parameter. If
is one-sided -smooth, then the approximation factor only depends on . We apply the new algorithm to a broad class of quadratic supermodular functions arising in diversity maximization. The case captures metric diversity maximization. We also develop new methods (inspired by swap rounding and approximate integer decomposition) for rounding quadratics over a matroid polytope. Together with the adapted continuous greedy this leads to a -approximation. This is the best asymptotic approximation known for this class of diversity maximization and the evidence suggests that it may be tight. We then consider general (non-quadratic) functions. We give a broad parameterized family of monotone functions which include submodular functions and the just-discussed supermodular family of discrete quadratics. Such set functions are called \emph{ -meta-submodular}. We develop local search algorithms with approximation factors that depend only on . We show that the -meta-submodular families include well-known function classes including meta-submodular functions ( ), proportionally submodular ( ), and diversity functions based on negative-type distances or Jensen-Shannon divergence (both ) and (semi-)metric diversity functions.
Iago A. Carvalho, Thomas Erlebach, Kleitos Papadopoulos
2019-04-19
We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, initially positioned in a source node s, to a destination node y. The delivery is achieved by the collective effort of the autonomous mobile agents, which can carry and exchange the package among them. The objective is to compute a delivery schedule that minimizes the delivery time of the package. In this paper, we propose an O(kn log(kn) + k m) time algorithm for this problem. This improves the previous state-of-the-art O(k^2 m + k n^2 + APSP) time algorithm for this problem, where APSP stands for the running-time of an algorithm for the All-Pairs Shortest Paths problem.
Sungjin Im, Benjamin Moseley
2019-04-18
MapReduce (and its open source implementation Hadoop) has become the de facto platform for processing large data sets. MapReduce offers a streamlined computational framework by interleaving sequential and parallel computation while hiding underlying system issues from the programmer. Due to the popularity of MapReduce, there have been attempts in the theoretical computer science community to understand the power and limitations of the MapReduce framework. In the most widely studied MapReduce models each machine has memory sub-linear in the input size to the problem, hence cannot see the entire input. This restriction places many limitations on algorithms that can be developed for the model; however, the current understanding of these restrictions is still limited. In this paper, our goal is to work towards understanding problems which do not admit efficient algorithms in the MapReduce model. We study the basic question of determining if a graph is connected or not. We concentrate on instances of this problem where an algorithm is to determine if a graph consists of a single cycle or two disconnected cycles. In this problem, locally every part of the graph is similar and the goal is to determine the global structure of the graph. We consider a natural class of algorithms that can store/process/transfer the information only in the form of paths and show that no randomized algorithm cannot answer the decision question in a sub-logarithmic number of rounds. Currently, there are no absolute super constant lower bounds on the number of rounds known for any problem in MapReduce. We introduce some of the first lower bounds for a natural graph problem, albeit for a restricted class of algorithms. We believe our result makes progress towards understanding the limitations of MapReduce.
Michael Jarret, Brad Lackey, Aike Liu, Kianna Wan
2018-10-10
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian
with spectral gap . Assuming the existence of an oracle such that , we provide an algorithm that reliably performs QAO in time with oracle queries, where . Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle for the problem of finding the minimum point of the cost function , restricting ourselves to computational basis measurements and driving Hamiltonian . Requiring only that have a constant lower bound on its spectral gap and upper bound on its spectral ratio, our QAO algorithm returns with probability in time . This achieves a quantum advantage for all , and recovers Grover scaling up to logarithmic factors when . We implement the algorithm as a subroutine in an optimization procedure that produces with exponentially small failure probability and expected runtime even when is not known beforehand.
