Data Structures And Algorithms
Malleable scheduling beyond identical machines (1903.11016v1)
Dimitris Fotakis, Jannik Matuschke, Orestis Papadigenopoulos
2019-03-26
In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job
on a set of allocated machines depends on the total speed of for . For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than , unless . On the positive side, we present polynomial-time algorithms with approximation ratios for machines with unrelated speeds, for machines with uniform speeds, and for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding and result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of for unrelated speeds ( is the golden ratio) and for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms (i) for minimizing the sum of weighted completion times; and (ii) a variant where we determine the effective speed of a set of allocated machines based on the norm of their speeds.
A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost (1903.10983v1)
Benjamin Doerr
2019-03-26
We prove that the compact genetic algorithm (cGA) with hypothetical population size
with high probability finds the optimum of any -dimensional jump function with jump size in iterations. Since it is known that the cGA with high probability needs at least iterations to optimize the unimodal OneMax function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. Our runtime guarantee improves over the recent upper bound valid for of Hasen"ohrl and Sutton (GECCO 2018). For the best choice of the hypothetical population size, this result gives a runtime guarantee of , whereas ours gives . We also provide a simple general method based on parallel runs that, under mild conditions, (i)~overcomes the need to specify a suitable population size, but gives a performance close to the one stemming from the best-possible population size, and (ii)~transforms EDAs with high-probability performance guarantees into EDAs with similar bounds on the expected runtime.
Survey of Consistent Software-Defined Network Updates (1609.02305v3)
Klaus-Tycho Foerster, Stefan Schmid, Stefano Vissicchio
2016-09-08
Computer networks have become a critical infrastructure. In fact, networks should not only meet strict requirements in terms of correctness, availability, and performance, but they should also be very flexible and support fast updates, e.g., due to policy changes, increasing traffic, or failures. This paper presents a structured survey of mechanism and protocols to update computer networks in a fast and consistent manner. In particular, we identify and discuss the different desirable consistency properties that should be provided throughout a network update, the algorithmic techniques which are needed to meet these consistency properties, and the implications on the speed and costs at which updates can be performed. We also explain the relationship between consistent network update problems and classic algorithmic optimization ones. While our survey is mainly motivated by the advent of Software-Defined Networks (SDNs) and their primary need for correct and efficient update techniques, the fundamental underlying problems are not new, and we provide a historical perspective of the subject as well.
Syntactic View of Sigma-Tau Generation of Permutations (1903.10701v1)
Wojciech Rytter, Wiktor Zuba
2019-03-26
We give a syntactic view of the Sawada-Williams
-generation of permutations. The corresponding sequence of -operations, of length is shown to be highly compressible: it has bit description. Using this compact description we design fast algorithms for ranking and unranking permutations.
On the tractability of the maximum independent set problem (1903.10700v1)
R. Dharmarajan, D. Ramachandran
2019-03-26
The maximum independent set problem is a classical NP-complete problem in graph theory and has important practical applications in many domains. In this paper we show, in a partially non-constructive way, the existence of an exact polynomial-time algorithm for this problem. We outline the algorithm in pseudo-code style. Then we prove its exactness and efficiency by analysis.
Algorithms to compute the Burrows-Wheeler Similarity Distribution (1903.10583v1)
Felipe A. Louza, Guilherme P. Telles, Simon Gog, Liang Zhao
2019-03-25
The Burrows-Wheeler transform (BWT) is a well studied text transformation widely used in data compression and text indexing. The BWT of two strings can also provide similarity measures between them, based on the observation that the more their symbols are intermixed in the transformation, the more the strings are similar. In this article we present two new algorithms to compute similarity measures based on the BWT for string collections. In particular, we present practical and theoretical improvements to the computation of the Burrows-Wheeler similarity distribution for all pairs of strings in a collection. Our algorithms take advantage of the BWT computed for the concatenation of all strings, and use compressed data structures that allow reducing the running time with a small memory footprint, as shown by a set of experiments with real and artificial datasets.
Lower Bounds for Electrical Reduction on Surfaces (1707.04683v2)
Hsien-Chih Chang, Marcos Cossarini, Jeff Erickson
2017-07-15
We strengthen the connections between electrical transformations and homotopy from the planar setting---observed and studied since Steinitz---to arbitrary surfaces with punctures. As a result, we improve our earlier lower bound on the number of electrical transformations required to reduce an
-vertex graph on surface in the worst case [SOCG 2016] in two different directions. Our previous lower bound applies only to facial electrical transformations on plane graphs with no terminals. First we provide a stronger lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus. Our second result extends our earlier lower bound to the wider class of planar electrical transformations, which preserve the planarity of the graph but may delete cycles that are not faces of the given embedding. This new lower bound follows from the observation that the defect of the medial graph of a planar graph is the same for all its planar embeddings.
Flow-Based Local Graph Clustering with Better Seed Set Inclusion (1811.12280v2)
Nate Veldt, Christine Klymko, David Gleich
2018-11-29
Flow-based methods for local graph clustering have received significant recent attention for their theoretical cut improvement and runtime guarantees. In this work we present two improvements for using flow-based methods in real-world semi-supervised clustering problems. Our first contribution is a generalized objective function that allows practitioners to place strict and soft penalties on excluding specific seed nodes from the output set. This feature allows us to avoid the tendency, often exhibited by previous flow-based methods, to contract a large seed set into a small set of nodes that does not contain all or even most of the seed nodes. Our second contribution is a fast algorithm for minimizing our generalized objective function, based on a variant of the push-relabel algorithm for computing preflows. We make our approach very fast in practice by implementing a global relabeling heuristic and employing a warm-start procedure to quickly solve related cut problems. In practice our algorithm is faster than previous related flow-based methods, and is also more robust in detecting ground truth target regions in a graph, thanks to its ability to better incorporate semi-supervised information about target clusters.
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings (1903.10445v1)
Nathaniel Lahn, Sharath Raghvendra
2019-03-25
We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph
with edge weights of or . Let be an upper bound on the weight of any matching in . Consider the subgraph induced by all the edges of with a weight . Suppose every connected component in this subgraph has vertices and edges. We present an algorithm to compute a maximum cardinality matching in in time. When all the edge weights are (symmetrically when all weights are ), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in time. However, if we can carefully assign weights of and on its edges such that both and are sub-linear in and for , then we can compute maximum cardinality matching in in time. Using our algorithm, we obtain a new time algorithm to compute an -approximate bottleneck matching of and an time algorithm for computing -approximate bottleneck matching in -dimensions. All previous algorithms take time. Given any graph that has an easily computable balanced vertex separator for every subgraph of size , for , we can apply our algorithm to compute a maximum matching in time improving upon the time taken by the HK-Algorithm.
Two Mutual Exclusion Algorithms for Shared Memory (1903.10402v1)
Jordi Bataller Mascarell
2019-03-25
In this paper, we introduce two algorithms that solve the mutual exclusion problem for concurrent processes that communicate through shared variables, [2]. Our algorithms guarantee that any process trying to enter the critical section, eventually, does enter it. They are formally proven to be correct. The first algorithm uses a special coordinator process in order to ensure equal chances to processes waiting for the critical section. In the second algorithm, with no coordinator, the process exiting the critical section is in charge to fairly elect the following one. In the case that no process is waiting, the turn is marked free and will be determined by future waiting processes. The type of shared variables used are a turn variable, readable and writable by all processes; and a flag array, readable by all with flag[i] writable only by process i. There is a version of the first algorithm where no writable by all variable is used. The bibliography reviewed for this paper is [4] and [3], all the rest is original work.