Data Structures And Algorithms
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient (1810.01726v2)
Surender Baswana, Shiv Kumar Gupta, Ayush Tulsyan
2018-10-03
We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.
Extending Chubanov algorithm to generic linear program: strong polynomial time (at least in not degenerated cases) (1901.08525v3)
Adrien Chan-Hon-Tong
2019-01-22
This short paper presents an algorithm which aims to solve generic linear program (
or ) using simple projections and call to a sub solver dedicated to linear feasibility ( ), recently, proven to be a strongly polynomial problem thank to Chubanov algorithm. Then, a complexity analysis states that this algorithm is strongly polynomial in not degenerated cases. Despite surely containing faults, this complexity analysis and this linear feasibility based algorithm call for a discussion.
Determining satisfiability of 3-SAT in polynomial time (1903.10081v2)
Ortho Flint, Asanka Wickramasinghe, Jason Brasse, Christopher Fowler
2019-03-24
In this paper, we provide a polynomial time (and space), algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies.
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.
Testing isomorphism of circular-arc graphs in polynomial time (1903.11062v1)
Roman Nedela, Ilia Ponomarenko, Peter Zeman
2019-03-26
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
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.