coding interviews
Topic: data structures and algorithms
4
4.0
Jun 30, 2018
06/18
by
Massimo Cafaro; Marco Pulimeno; Piergiulio Tempesta
texts
eye 4
favorite 0
comment 0
We present a message-passing based parallel version of the Space Saving algorithm designed to solve the $k$--majority problem. The algorithm determines in parallel frequent items, i.e., those whose frequency is greater than a given threshold, and is therefore useful for iceberg queries and many other different contexts. We apply our algorithm to the detection of frequent items in both real and synthetic datasets whose probability distribution functions are a Hurwitz and a Zipf distribution...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1401.0702
5
5.0
Jun 30, 2018
06/18
by
Kun He; Pengli Ji; Chumin Li
texts
eye 5
favorite 0
comment 0
Given a set of rectangular modules with fixed area and variable dimensions, and a fixed rectangular circuit. The placement of Fixed-Outline Floorplanning with Soft Modules (FOFSM) aims to determine the dimensions and position of each module on the circuit. We present a two-stage Iterative Merging Placement (IMP) algorithm for the FOFSM with zero deadspace constraint. The first stage iteratively merges two modules with the least area into a composite module to achieve a final composite module,...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1401.3172
6
6.0
Jun 30, 2018
06/18
by
Rasmus Pagh; Morten Stöckel
texts
eye 6
favorite 0
comment 0
We consider the problem of multiplying sparse matrices (over a semiring) where the number of non-zero entries is larger than main memory. In the classical paper of Hong and Kung (STOC '81) it was shown that to compute a product of dense $U \times U$ matrices, $\Theta \left(U^3 / (B \sqrt{M}) \right)$ I/Os are necessary and sufficient in the I/O model with internal memory size $M$ and memory block size $B$. In this paper we generalize the upper and lower bounds of Hong and Kung to the sparse...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1403.3551
5
5.0
Jun 30, 2018
06/18
by
Cem Evrendilek; Ismail Hakki Toroslu; Sasan Hashemi
texts
eye 5
favorite 0
comment 0
Most large organizations, such as corporations, are hierarchical organizations. In hierarchical organizations each entity in the organization, except the root entity, is a sub-part of another entity. In this paper we study the task assignment problem to the entities of tree-like hierarchical organizations. The inherent tree structure introduces an interesting and challenging constraint to the standard assignment problem. When a task is assigned to an entity in a hierarchical organization, the...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1404.0783
5
5.0
Jun 30, 2018
06/18
by
Mamadou Moustapha Kanté; Vincent Limouzy; Arnaud Mary; Lhouari Nourine; Takeaki Uno
texts
eye 5
favorite 0
comment 0
The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size of all its minimal transversals, is a fifty years old open problem, and up to now there are few examples of hypergraph classes where the problem is solved. A minimal dominating set in a graph is a subset of its vertex set that has a non empty intersection with the closed neighborhood of every vertex. It is proved in...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1404.3501
5
5.0
Jun 30, 2018
06/18
by
Moran Feldman; Ola Svensson; Rico Zenklusen
texts
eye 5
favorite 0
comment 0
Only recently progress has been made in obtaining $o(\log(\mathrm{rank}))$-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a $O(\sqrt{\log(\mathrm{rank})})$-competitive procedure, and Lachish (2014) later presented a $O(\log\log(\mathrm{rank}))$-competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1404.4473
8
8.0
Jun 30, 2018
06/18
by
Dana Ron; Gilad Tsur
texts
eye 8
favorite 0
comment 0
We study a basic problem of approximating the size of an unknown set $S$ in a known universe $U$. We consider two versions of the problem. In both versions the algorithm can specify subsets $T\subseteq U$. In the first version, which we refer to as the group query or subset query version, the algorithm is told whether $T\cap S$ is non-empty. In the second version, which we refer to as the subset sampling version, if $T\cap S$ is non-empty, then the algorithm receives a uniformly selected...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1404.5568
6
6.0
Jun 30, 2018
06/18
by
Amihood Amir; Timothy Chan; Moshe Lewenstein; Noa Lewenstein
texts
eye 6
favorite 0
comment 0
Jumbled indexing is the problem of indexing a text $T$ for queries that ask whether there is a substring of $T$ matching a pattern represented as a Parikh vector, i.e., the vector of frequency counts for each character. Jumbled indexing has garnered a lot of interest in the last four years. There is a naive algorithm that preprocesses all answers in $O(n^2|\Sigma|)$ time allowing quick queries afterwards, and there is another naive algorithm that requires no preprocessing but has...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1405.0189
4
4.0
Jun 30, 2018
06/18
by
Michael X. Zhou
texts
eye 4
favorite 0
comment 0
In this short note, the dual problem for the traveling salesman problem is constructed through the classic Lagrangian. The existence of optimality conditions is expressed as a corresponding inverse problem. A general 4-cities instance is given, and the numerical experiment shows that the classic Lagrangian may not be applicable to the traveling salesman problem.
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1405.1298
7
7.0
Jun 30, 2018
06/18
by
Arka Bhattacharya
texts
eye 7
favorite 0
comment 0
The paper provides a description of the two recent approximation algorithms for the Asymmetric Traveling Salesman Problem, giving the intuitive description of the works of Feige-Singh[1] and Asadpour et.al\ [2].\newline [1] improves the previous $O(\log n)$ approximation algorithm, by improving the constant from 0.84 to 0.66 and modifying the work of Kaplan et. al\ [3] and also shows an efficient reduction from ATSPP to ATSP. Combining both the results, they finally establish an approximation...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1405.1781
5
5.0
Jun 30, 2018
06/18
by
Zhengjun Cao; Zhenfu Cao; Lihua Liu
texts
eye 5
favorite 0
comment 0
An efficient quantum modular exponentiation method is indispensible for Shor's factoring algorithm. But we find that all descriptions presented by Shor, Nielsen and Chuang, Markov and Saeedi, et al., are flawed. We also remark that some experimental demonstrations of Shor's algorithm are misleading, because they violate the necessary condition that the selected number $q=2^s$, where $s$ is the number of qubits used in the first register, must satisfy $n^2 \leq q < 2n^2$, where $n$ is the...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1408.6252
4
4.0
Jun 30, 2018
06/18
by
Jiecao Chen; Qin Zhang
texts
eye 4
favorite 0
comment 0
Modern data management systems often need to deal with massive, dynamic and inherently distributed data sources. We collect the data using a distributed network, and at the same time try to maintain a global view of the data at a central coordinator using a minimal amount of communication. Such applications have been captured by the distributed monitoring model which has attracted a lot of attention in recent years. In this paper we investigate the monitoring of the entropy functions, which are...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1409.4843
5
5.0
Jun 30, 2018
06/18
by
Fatemeh Rajabi-Alni; Alireza Bagheri; Behrouz Minaei-Bidgoli
texts
eye 5
favorite 0
comment 0
A matching between two sets A and B assigns some elements of A to some elements of B. Finding the similarity between two sets of elements by advantage of the matching is widely used in computational biology. Frequently, the capacities of the elements are limited. That is, the number of the elements that can be matched to each element should not exceed a given number. We describe the first O(n^3) time algorithm for matching two sets of elements with limited capacities. We use bipartite graphs to...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1410.3408
9
9.0
Jun 30, 2018
06/18
by
Roland Glantz; Henning Meyerhenke; Alexander Noe
texts
eye 9
favorite 0
comment 0
Static mapping is the assignment of parallel processes to the processing elements (PEs) of a parallel system, where the assignment does not change during the application's lifetime. In our scenario we model an application's computations and their dependencies by an application graph. This graph is first partitioned into (nearly) equally sized blocks. These blocks need to communicate at block boundaries. To assign the processes to PEs, our goal is to compute a communication-efficient bijective...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1411.0921
5
5.0
Jun 30, 2018
06/18
by
Khaled Elbassioni
texts
eye 5
favorite 0
comment 0
We give a polynomial delay algorithm, that for any graph $G$ and positive integer $k$, enumerates all connected induced subgraphs of $G$ of order $k$. Our algorithm enumerates each subgraph in at most $O((k\min\{(n-k),k\Delta\})^2(\Delta+\log k))$ and uses linear space $O(n+m)$, where $n$ and $m$ are respectively the number of vertices and edges of $G$ and $\Delta$ is the maximum degree.
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1411.2262
5
5.0
Jun 30, 2018
06/18
by
Ariel Gabizon; Daniel Lokshtanov; Michal Pilipczuk
texts
eye 5
favorite 0
comment 0
In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation" variable, where the original problem corresponds to setting this variable to a constant value. For instance, the problem of packing sets of size at most $p$ into a given universe generalizes the Maximum Matching problem, which is recovered by taking $p=2$. Most often, the complexity of the problem increases...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1411.6756
15
15
Jun 26, 2018
06/18
by
Sergio Cabello; Pablo Pérez-Lantero
texts
eye 15
favorite 0
comment 0
A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set $\mathbb{I}$ of intervals and we want to find an independent subset of intervals of largest cardinality. Let $\alpha(\mathbb{I})$ denote the cardinality of an optimal solution. We discuss the estimation of $\alpha(\mathbb{I})$ in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in $\{1,...,n...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1501.02285
13
13
Jun 26, 2018
06/18
by
Raphael Kramer; Nelson Maculan; Anand Subramanian; Thibaut Vidal
texts
eye 13
favorite 0
comment 0
We propose a new speed and departure time optimization algorithm for the Pollution-Routing Problem (PRP) which runs in quadratic time. This algorithm is embedded into an iterated local search-based metaheuristic to achieve a combined speed, scheduling and routing optimization. Extensive computational experiments are conducted on classic PRP benchmark instances. Allowing delayed departure times from the depot significantly increases the search space, and contributes to reduce CO 2 emissions by...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1501.05354
15
15
Jun 26, 2018
06/18
by
Derek G. Corneil; Jeremie Dusart; Michel Habib; Fabien de Montgolfier
texts
eye 15
favorite 0
comment 0
In this paper, we consider the problem of the recognition of various kinds of orderings produced by graph searches. To this aim, we introduce a new framework, the Tie-Breaking Label Search (TBLS), in order to handle a broad variety of searches. This new model is based on partial orders defined on the label set and it unifies the General Label Search (GLS) formalism of Krueger, Simonet and Berry (2011), and the "pattern-conditions" formalism of Corneil and Krueger (2008). It allows us...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1501.06148
15
15
Jun 26, 2018
06/18
by
Atalay Mert İleri; M. Oğuzhan Külekci; Bojian Xu
texts
eye 15
favorite 0
comment 0
Repeat finding in strings has important applications in subfields such as computational biology. Surprisingly, all prior work on repeat finding did not consider the constraint on the locality of repeats. In this paper, we propose and study the problem of finding longest repetitive substrings covering particular string positions. We propose an $O(n)$ time and space algorithm for finding the longest repeat covering every position of a string of size $n$. Our work is optimal since the reading and...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1501.06259
16
16
Jun 28, 2018
06/18
by
Moran Feldman; Rani Izsak
texts
eye 16
favorite 0
comment 0
In the Secretary Problem, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a random order, and one has to decide on the spot, whether to hire a candidate or continue interviewing. It is well known that the best candidate can be hired with a probability of 1/e (Dynkin, 1963). Recent works extend this problem to settings in which multiple candidates can be hired, subject to some constraint. Here, one wishes to hire a set of candidates maximizing a...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1507.06199
10
10.0
Jun 28, 2018
06/18
by
Anke van Zuylen
texts
eye 10
favorite 0
comment 0
We show improved approximation guarantees for the traveling salesman problem on cubic graphs, and cubic bipartite graphs. For cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi (2014) by giving a simple "local improvement" algorithm that finds a tour of length at most 5/4 n - 2. For 2-connected cubic graphs, we show that the techniques of Moemke and Svensson (2011) can be combined with the techniques of Correa, Larre and Soto (2012), to obtain a tour of...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1507.07121
20
20
Jun 28, 2018
06/18
by
Thibaut Vidal
texts
eye 20
favorite 0
comment 0
The Split algorithm is an essential building block for route-first cluster-second heuristics and modern genetic algorithms for vehicle routing problems. The recent survey of [Prins, Lacomme and Prodhon, Transport Res. C (40), 179-200] lists more than 70 articles that use this technique. In the vehicle routing literature, Split is usually assimilated to the search for a shortest path in a directed acyclic graph $\mathcal{G}$ and solved in $O(nB)$ using Bellman's algorithm, where $n$ is the...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1508.02759
27
27
Jun 28, 2018
06/18
by
Moritz von Looz; Henning Meyerhenke
texts
eye 27
favorite 0
comment 0
$\newcommand{\dist}{\operatorname{dist}}$ In this paper we define the notion of a probabilistic neighborhood in spatial data: Let a set $P$ of $n$ points in $\mathbb{R}^d$, a query point $q \in \mathbb{R}^d$, a distance metric $\dist$, and a monotonically decreasing function $f : \mathbb{R}^+ \rightarrow [0,1]$ be given. Then a point $p \in P$ belongs to the probabilistic neighborhood $N(q, f)$ of $q$ with respect to $f$ with probability $f(\dist(p,q))$. We envision applications in facility...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1509.01990
13
13
Jun 28, 2018
06/18
by
Shivam Garg; Geevarghese Philip
texts
eye 13
favorite 0
comment 0
We investigate the following above-guarantee parameterization of the classical Vertex Cover problem: Given a graph $G$ and $k\in\mathbb{N}$ as input, does $G$ have a vertex cover of size at most $(2LP-MM)+k$? Here $MM$ is the size of a maximum matching of $G$, $LP$ is the value of an optimum solution to the relaxed (standard) LP for Vertex Cover on $G$, and $k$ is the parameter. Since $(2LP-MM)\geq{LP}\geq{MM}$, this is a stricter parameterization than those---namely, above-$MM$, and...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1509.03990
12
12
Jun 28, 2018
06/18
by
David Gibb; Bruce Kapron; Valerie King; Nolan Thorn
texts
eye 12
favorite 0
comment 0
This paper considers fully dynamic graph algorithms with both faster worst case update time and sublinear space. The fully dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes, process an online sequence of edge insertions, edge deletions, and queries of the form "Is there a path between nodes a and b?" In 2013, the first data structure was presented with worst case time per operation which was polylogarithmic in n. In this paper, we shave off a...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1509.06464
11
11
Jun 28, 2018
06/18
by
Konrad Kułakowski
texts
eye 11
favorite 0
comment 0
The growing popularity of shared-memory multiprocessor machines has caused significant changes in the design of concurrent software. In this approach, the concurrently running threads communicate and synchronize with each other through data structures in shared memory. Hence, the efficiency of these structures is essential for the performance of concurrent applications. The need to find new concurrent data structures prompted the author some time ago to propose the cvEB array modeled on the van...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1509.06948
4
4.0
Jun 28, 2018
06/18
by
Sepehr Assadi; Sanjeev Khanna; Yang Li; Val Tannen
texts
eye 4
favorite 0
comment 0
In this paper, we introduce a new model for sublinear algorithms called \emph{dynamic sketching}. In this model, the underlying data is partitioned into a large \emph{static} part and a small \emph{dynamic} part and the goal is to compute a summary of the static part (i.e, a \emph{sketch}) such that given any \emph{update} for the dynamic part, one can combine it with the sketch to compute a given function. We say that a sketch is \emph{compact} if its size is bounded by a polynomial function...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1510.03252
5
5.0
Jun 29, 2018
06/18
by
Jérémy Barbay
texts
eye 5
favorite 0
comment 0
We describe an algorithm computing an optimal prefix free code for $n$ unsorted positive weights in time within $O(n(1+\lg \alpha))\subseteq O(n\lg n)$, where the alternation $\alpha\in[1..n-1]$ measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size $n$ and alternation $\alpha$. Such results refine the state of the art...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1602.00023
8
8.0
Jun 29, 2018
06/18
by
Cassio Neri
texts
eye 8
favorite 0
comment 0
Let integer be any C/C++ unsigned integer type up to 64-bits long. Given a Dyck word the following code returns the next Dyck word of the same size, provided it exists. integer next_dyck_word(integer w) { integer const a = w & -w; integer const b = w + a; integer c = w ^ b; c = (c / a >> 2) + 1; c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b; return c; }
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1602.06426
9
9.0
Jun 29, 2018
06/18
by
Dušan Knop; Martin Koutecký
texts
eye 9
favorite 0
comment 0
Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In 2014, Mnich and Wiese initiated a systematic study in this direction. In this paper we continue this study and show that several additional cases of fundamental scheduling problems are fixed parameter tractable for some natural parameters. Our main tool...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1603.02611
6
6.0
Jun 29, 2018
06/18
by
Fedor V. Fomin; Daniel Lokshtanov; Dániel Marx; Marcin Pilipczuk; Michał Pilipczuk; Saket Saurabh
texts
eye 6
favorite 0
comment 0
We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}$, where $n$ is...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1604.05999
8
8.0
Jun 29, 2018
06/18
by
Andre Linhares; Chaitanya Swamy
texts
eye 8
favorite 0
comment 0
We study the {\em min-cost chain-constrained spanning-tree} (abbreviated \mcst) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the {\em first} polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor {\em and} (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for {\em unweighted} \cst was known \cite{olver}, which...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1605.03203
6
6.0
Jun 29, 2018
06/18
by
Zhaosen Wang; Jean Honorio
texts
eye 6
favorite 0
comment 0
We present a randomized algorithm for reconstructing directed rooted trees of $n$ nodes and node degree at most $d$, by asking at most $O(dn\log^2 n)$ path queries. Each path query takes as input an origin node and a target node, and answers whether there is a directed path from the origin to the target. Our algorithm is only a factor of $O(d\log n)$ from the information-theoretic lower bound of $\Omega(n\log n)$ for any deterministic or randomized algorithm. We also present a $O(dn\log^3 n)$...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1606.05183
4
4.0
Jun 29, 2018
06/18
by
Andreas Björklund; Petteri Kaski; Ioannis Koutis
texts
eye 4
favorite 0
comment 0
We are motivated by a tantalizing open question in exact algorithms: can we detect whether an $n$-vertex directed graph $G$ has a Hamiltonian cycle in time significantly less than $2^n$? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant $0
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1607.04002
8
8.0
Jun 30, 2018
06/18
by
Mathias Bæk Tejs Knudsen
texts
eye 8
favorite 0
comment 0
Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is a subgraph $H$ that approximates all distances between pairs of nodes up to an additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic algorithm that constructs an additive $O\!\left(1\right)$-spanner with $O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be compared with the randomized Monte...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1704.04473
9
9.0
Jun 30, 2018
06/18
by
Samir Khuller; Jingling Li; Pascal Sturmfels; Kevin Sun; Prayaag Venkat
texts
eye 9
favorite 0
comment 0
In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et al. [Mathematics of Operations Research, Vol 22(3):513-544, 1997] and Garg et al. [Proc. of Foundations of Software Technology and Theoretical Computer Science, pp. 96-107, 2007], who show how to convert an offline approximation to an online scheme. Our framework uses two offline approximation algorithms (one for the...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1704.06677
15
15
Jun 27, 2018
06/18
by
Yann Disser; Max Klimm; Elisabeth Lübbecke
texts
eye 15
favorite 0
comment 0
We study the fundamental problem of scheduling bidirectional traffic along a path composed of multiple segments. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a segment, while jobs in opposing directions cannot cross a segment at the same time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by proving that it is NP-hard even for identical jobs. We complement this result...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1504.07129
23
23
Jun 27, 2018
06/18
by
Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai
texts
eye 23
favorite 0
comment 0
We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on $n$-node $m$-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach [JACM 1981]; it has $ O(1) $ query time and $ O (mn) $ total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1504.07959
15
15
Jun 27, 2018
06/18
by
Marek Chrobak; Mordecai Golin; J. Ian Munro; Neal E. Young
texts
eye 15
favorite 0
comment 0
In 1971, Knuth gave an $O(n^2)$-time algorithm for the classic problem of finding an optimal binary search tree. Knuth's algorithm works only for search trees based on 3-way comparisons, while most modern computers support only 2-way comparisons (e.g., $ $). Until this paper, the problem of finding an optimal search tree using 2-way comparisons remained open -- poly-time algorithms were known only for restricted variants. We solve the general case, giving (i) an $O(n^4)$-time algorithm and (ii)...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1505.00357
13
13
Jun 27, 2018
06/18
by
Christina Boucher; Alexander Bowe; Travis Gagie; Giovanni Manzini; Jouni Sirén
texts
eye 13
favorite 0
comment 0
Motivated by the problem of storing coloured de Bruijn graphs, we show how, if we can already support fast select queries on one string, then we can store a little extra information and support fairly fast select queries on a similar string.
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1506.03262
6
6.0
Jun 28, 2018
06/18
by
Jie You; Jianxin Wang; Yixin Cao
texts
eye 6
favorite 0
comment 0
A vertex set $X$ of a graph $G$ is an association set if each component of $G - X$ is a clique, or a dissociation set if each component of $G - X$ is a single vertex or a single edge. Interestingly, $G - X$ is then precisely a graph containing no induced $P_3$'s or containing no $P_3$'s, respectively. We observe some special structures and show that if none of them exists, then the minimum association set problem can be reduced to the minimum (weighted) dissociation set problem. This yields the...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1510.08276
4
4.0
Jun 29, 2018
06/18
by
Takaaki Nishimoto; Tomohiro I; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
texts
eye 4
favorite 0
comment 0
In this paper, we propose a new \emph{dynamic compressed index} of $O(w)$ space for a dynamic text $T$, where $w = O(\min(z \log N \log^*M, N))$ is the size of the signature encoding of $T$, $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of $T$, $N$ is the length of $T$, and $M \geq 3N$ is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern $P$ in $T$ in $O(|P| f_{\mathcal{A}} + \log w \log |P| \log^* M (\log N + \log |P|...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1605.09558
5
5.0
Jun 29, 2018
06/18
by
Yohei Ueki; Diptarama; Masatoshi Kurihara; Yoshiaki Matsuoka; Kazuyuki Narisawa; Ryo Yoshinaka; Hideo Bannai; Shunsuke Inenaga; Ayumi Shinohara
texts
eye 5
favorite 0
comment 0
We consider the longest common subsequence (LCS) problem with the restriction that the common subsequence is required to consist of at least $k$ length substrings. First, we show an $O(mn)$ time algorithm for the problem which gives a better worst-case running time than existing algorithms, where $m$ and $n$ are lengths of the input strings. Furthermore, we mainly consider the LCS in at least $k$ length order-isomorphic substrings problem. We show that the problem can also be solved in $O(mn)$...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1609.03668
66
66
Jun 27, 2018
06/18
by
Thore Husfeldt
texts
eye 66
favorite 0
comment 0
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1505.05825
18
18
Jun 28, 2018
06/18
by
Joe Cheriyan; Zhihan Gao
texts
eye 18
favorite 0
comment 0
In Part II, we study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum~of~Squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is $\leq \frac{3}{2}+\epsilon$, where $\epsilon>0$ can be any small constant. We obtain this result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee of ($\frac32+\epsilon$) relative to the SDP relaxation. The algorithm is combinatorial and...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1507.01309
41
41
Jun 28, 2018
06/18
by
Philip Bille; Anders Roy Christiansen; Patrick Hagge Cording; Inge Li Gørtz
texts
eye 41
favorite 0
comment 0
Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular compression schemes. Given a grammar, the random access problem is to compactly represent the grammar while supporting random access, that is, given a position in the original uncompressed string report the character at that position. In this paper we study the random access problem with the finger search property,...
Topics: Computing Research Repository, Data Structures and Algorithms
Source: http://arxiv.org/abs/1507.02853
6
6.0
Jun 30, 2018
06/18
by
Ivan Bliznets; Fedor V. Fomin; Marcin Pilipczuk; Michał Pilipczuk
texts
eye 6
favorite 0
comment 0
In the Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into an interval graph, i.e., a graph admitting an intersection model of intervals on a line. Motivated by applications in sparse matrix multiplication and molecular biology, Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] asked for a fixed-parameter algorithm solving this problem. This question was answer affirmatively more than a decade later by...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1402.3473
10
10.0
Jun 30, 2018
06/18
by
Neal E. Young
texts
eye 10
favorite 0
comment 0
We describe the first nearly linear-time approximation algorithms for explicitly given mixed packing/covering linear programs, and for (non-metric) fractional facility location. We also describe the first parallel algorithms requiring only near-linear total work and finishing in polylog time. The algorithms compute $(1+\epsilon)$-approximate solutions in time (and work) $O^*(N/\epsilon^2)$, where $N$ is the number of non-zeros in the constraint matrix. For facility location, $N$ is the number...
Topics: Data Structures and Algorithms, Computing Research Repository
Source: http://arxiv.org/abs/1407.3015
