0
0.0

Nov 5, 2019
11/19

by
Deepali Srivastava

texts

######
eye 0

######
favorite 0

######
comment 0

4. Stack and Queue data structures and algorithms Deepali Srivastava

Topic: data structures and algorithms

1
1.0

Jun 29, 2018
06/18

by
Cewei Cui; Zhe Dang

texts

######
eye 1

######
favorite 0

######
comment 0

This paper develops two heuristic algorithms to solve graph isomorphism, using free energy encoding. The first algorithm uses four types of encoding refinement techniques such that every graph can be distinguished by a canonical number computed by the algorithm. The second algorithm injects energy into the graph to conduct individualization such that the correspondence relation between a pair of isomorphic graphs can be found. The core principle behind the two algorithms is encoding discrete...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1605.07220

3
3.0

Jun 28, 2018
06/18

by
Marek Cygan; Daniel Lokshtanov; Marcin Pilipczuk; Michał Pilipczuk; Saket Saurabh

texts

######
eye 3

######
favorite 0

######
comment 0

In the Closest String problem one is given a family $\mathcal S$ of equal-length strings over some fixed alphabet, and the task is to find a string $y$ that minimizes the maximum Hamming distance between $y$ and a string from $\mathcal S$. While polynomial-time approximation schemes (PTASes) for this problem are known for a long time [Li et al., J. ACM'02], no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. In this paper, we prove that the existence of an EPTAS...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1509.05809

0
0.0

Jun 29, 2018
06/18

by
Yoichi Iwata

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we propose an algorithm that, given an undirected graph $G$ of $m$ edges and an integer $k$, computes a graph $G'$ and an integer $k'$ in $O(k^4 m)$ time such that (1) the size of the graph $G'$ is $O(k^2)$, (2) $k'\leq k$, and (3) $G$ has a feedback vertex set of size at most $k$ if and only if $G'$ has a feedback vertex set of size at most $k'$. This is the first linear-time polynomial-size kernel for Feedback Vertex Set. The size of our kernel is $2k^2+k$ vertices and $4k^2$...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1608.01463

0
0.0

Jun 30, 2018
06/18

by
Matt Challacombe; Nicolas Bock

texts

######
eye 0

######
favorite 0

######
comment 0

We report an N-Body approach to computing the Fock exchange matrix with and without permutational symmetry. The method achieves an O(N lg N) computational complexity through an embedded metric-query, allowing hierarchical application of direct SCF criteria. The advantages of permutational symmetry are found to be 4-fold for small systems, but decreasing with increasing system size and/or more permissive neglect criteria. This work sets the stage for: (1) the introduction of range queries in...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1401.6961

1
1.0

Jun 30, 2018
06/18

by
Moses Charikar; Neha Gupta; Roy Schwartz

texts

######
eye 1

######
favorite 0

######
comment 0

Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min $s-t$ Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization. Here, we are given a graph with edges labeled $+$ or $-$ and the goal is to produce a clustering that agrees with the labels as much as possible: $+$ edges within clusters and $-$ edges across clusters. The classical approach towards Correlation Clustering (and other graph cut problems) is to optimize a...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1704.00355

4
4.0

Jun 27, 2018
06/18

by
F. Bruce Shepherd; Adrian Vetta

texts

######
eye 4

######
favorite 0

######
comment 0

We consider single-sink network flow problems. An instance consists of a capacitated graph (directed or undirected), a sink node $t$ and a set of demands that we want to send to the sink. Here demand $i$ is located at a node $s_i$ and requests an amount $d_i$ of flow capacity in order to route successfully. Two standard objectives are to maximise (i) the number of demands (cardinality) and (ii) the total demand (throughput) that can be routed subject to the capacity constraints. Furthermore, we...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1504.00627

2
2.0

Jun 28, 2018
06/18

by
Hadrien Cambazard; Deepak Mehta; Barry O'Sullivan; Helmut Simonis

texts

######
eye 2

######
favorite 0

######
comment 0

Bin packing is a well studied problem involved in many applications. The classical bin packing problem is about minimising the number of bins and ignores how the bins are utilised. We focus in this paper, on a variant of bin packing that is at the heart of efficient management of data centres. In this context, servers can be viewed as bins and virtual machines as items. The efficient management of a data-centre involves minimising energy costs while ensuring service quality. The assignment of...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1509.06712

2
2.0

Jun 28, 2018
06/18

by
Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin

texts

######
eye 2

######
favorite 0

######
comment 0

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph $G$ to graph $H$ cannot be done in time $|V(H)|^{o(|V(G)|)}$. Combined with the reduction of Cygan, Pachocki, and Soca{\l}a, our result rules out (subject to ETH) a possibility of $|V(G)|^{o(|V(G)|)}$-time algorithm deciding if graph $H$ is a subgraph of $G$. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1507.03738

1
1.0

Jun 30, 2018
06/18

by
David Eppstein; Michael T. Goodrich; Nil Mamano

texts

######
eye 1

######
favorite 0

######
comment 0

We study a discrete version of a geometric stable marriage problem originally proposed in a continuous setting by Hoffman, Holroyd, and Peres, in which points in the plane are stably matched to cluster centers, as prioritized by their distances, so that each cluster center is apportioned a set of points of equal area. We show that, for a discretization of the problem to an $n\times n$ grid of pixels with $k$ centers, the problem can be solved in time $O(n^2 \log^5 n)$, and we experiment with...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1704.02303

0
0.0

Jun 29, 2018
06/18

by
Didem Gözüpek; Mordechai Shalom

texts

######
eye 0

######
favorite 0

######
comment 0

In an edge-colored graph, a traversal cost occurs at a vertex along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the traversed edges. This concept leads to two global cost measures, namely the \emph{reload cost} and the \emph{changeover cost}, that have been studied in the literature and have various applications in telecommunications, transportation networks, and energy distribution networks. Previous work...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1607.06751

0
0.0

Jun 29, 2018
06/18

by
Alejandro López-Ortiz; Jazmín Romero

texts

######
eye 0

######
favorite 0

######
comment 0

In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound [17,5,11,8]. In this paper, we introduce the $\Pi$-Packing with $\alpha()$-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let $\mathcal{V}^r$ be all possible subsets of vertices of $V(G)$ each of size at most $r$, and $\alpha: \mathcal{V}^r \times \mathcal{V}^r \to \{0,1\}$ be a function. The...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1601.03676

0
0.0

Jun 29, 2018
06/18

by
Tobias Maier; Peter Sanders; Roman Dementiev

texts

######
eye 0

######
favorite 0

######
comment 0

Concurrent hash tables are one of the most important concurrent data structures with numerous applications. Since hash table accesses can dominate the execution time of the overall application, we need implementations that achieve good speedup. Unfortunately, currently available concurrent hashing libraries turn out to be far away from this requirement in particular when contention on some elements occurs. Our starting point for better performing data structures is a fast and simple lock-free...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1601.04017

1
1.0

Jun 29, 2018
06/18

by
Joshimar Cordova; Gonzalo Navarro

texts

######
eye 1

######
favorite 0

######
comment 0

The fully-functional succinct tree representation of Navarro and Sadakane (ACM Transactions on Algorithms, 2014) supports a large number of operations in constant time using $2n+o(n)$ bits. However, the full idea is hard to implement. Only a simplified version with $O(\log n)$ operation time has been implemented and shown to be practical and competitive. We describe a new variant of the original idea that is much simpler to implement and has worst-case time $O(\log\log n)$ for the operations....

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1601.06939

0
0.0

Jun 29, 2018
06/18

by
Tomasz Kociumaka

texts

######
eye 0

######
favorite 0

######
comment 0

For a text given in advance, the substring minimal suffix queries ask to determine the lexicographically minimal non-empty suffix of a substring specified by the location of its occurrence in the text. We develop a data structure answering such queries optimally: in constant time after linear-time preprocessing. This improves upon the results of Babenko et al. (CPM 2014), whose trade-off solution is characterized by $\Theta(n\log n)$ product of these time complexities. Next, we extend our...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1601.08051

0
0.0

Jun 29, 2018
06/18

by
Søren Dahlgaard

texts

######
eye 0

######
favorite 0

######
comment 0

Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that: -- No...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1602.06705

0
0.0

Jun 28, 2018
06/18

by
Christos Kalaitzis

texts

######
eye 0

######
favorite 0

######
comment 0

We study the Maximum Budgeted Allocation problem, which is the problem of assigning indivisible items to players with budget constraints. In its most general form, an instance of the MBA problem might include many different prices for the same item among different players, and different budget constraints for every player. So far, the best approximation algorithms we know for the MBA problem achieve a $3/4$-approximation ratio, and employ a natural LP relaxation, called the Assignment-LP. In...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1511.09293

0
0.0

Jun 28, 2018
06/18

by
Carsten Fischer; Heiko Röglin

texts

######
eye 0

######
favorite 0

######
comment 0

In the bin covering problem, the goal is to fill as many bins as possible up to a certain minimal level with a given set of items of different sizes. Online variants, in which the items arrive one after another and have to be packed immediately on their arrival without knowledge about the future items, have been studied extensively in the literature. We study the simplest possible online algorithm Dual Next-Fit, which packs all arriving items into the same bin until it is filled and then...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1512.04719

0
0.0

Jun 28, 2018
06/18

by
Mika Göös; Juho Hirvonen; Reut Levi; Moti Medina; Jukka Suomela

texts

######
eye 0

######
favorite 0

######
comment 0

This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1512.05411

0
0.0

Jun 29, 2018
06/18

by
Alina Ene; Gary Miller; Jakub Pachocki; Aaron Sidford

texts

######
eye 0

######
favorite 0

######
comment 0

We introduce the notion of balance for directed graphs: a weighted directed graph is $\alpha$-balanced if for every cut $S \subseteq V$, the total weight of edges going from $S$ to $V\setminus S$ is within factor $\alpha$ of the total weight of edges going from $V\setminus S$ to $S$. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with $\alpha = 1$) and residual graphs of $(1+\epsilon)$-approximate undirected maximum flows (with $\alpha=O(1/\epsilon)$)....

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1603.09009

0
0.0

Jun 29, 2018
06/18

by
Zengfeng Huang; Pan Peng

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper we study graph problems in dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require $\Omega(n)$ space, where $n$ is the number of vertices, existing works mainly focused on designing $\tilde{O}(n)$ space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e.g. $n$ is huge or the graph is sparse). In this work, we give single-pass...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1605.00089

1
1.0

Jun 29, 2018
06/18

by
Sara Ahmadian; Chaitanya Swamy

texts

######
eye 1

######
favorite 0

######
comment 0

We consider clustering problems with {\em non-uniform lower bounds and outliers}, and obtain the {\em first approximation guarantees} for these problems. We have a set $\F$ of facilities with lower bounds $\{L_i\}_{i\in\F}$ and a set $\D$ of clients located in a common metric space $\{c(i,j)\}_{i,j\in\F\cup\D}$, and bounds $k$, $m$. A feasible solution is a pair $\bigl(S\sse\F,\sigma:\D\mapsto S\cup\{\mathsf{out}\}\bigr)$, where $\sigma$ specifies the client assignments, such that $|S|\leq k$,...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1608.01700

0
0.0

Jun 29, 2018
06/18

by
Noriyuki Kurosawa

texts

######
eye 0

######
favorite 0

######
comment 0

The linear pivot selection algorithm, known as median-of-medians, makes the worst case complexity of quicksort be $\mathrm{O}(n\ln n)$. Nevertheless, it has often been said that this algorithm is too expensive to use in quicksort. In this article, we show that we can make the quicksort with this kind of pivot selection approach be efficient.

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1608.04852

0
0.0

Jun 29, 2018
06/18

by
Jérémy Barbay; Carlos Ochoa; Srinivasa Rao Satti

texts

######
eye 0

######
favorite 0

######
comment 0

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size $n$ and number of queries $q$ fixed (i.e., the query size). Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1608.06666

0
0.0

Jun 29, 2018
06/18

by
Md. Jawaherul Alam; Michael T. Goodrich; Timothy Johnson

texts

######
eye 0

######
favorite 0

######
comment 0

We describe a graph visualization tool for visualizing Java bytecode. Our tool, which we call J-Viz, visualizes connected directed graphs according to a canonical node ordering, which we call the sibling-first recursive (SFR) numbering. The particular graphs we consider are derived from applying Shiver's k-CFA framework to Java bytecode, and our visualizer includes helpful links between the nodes of an input graph and the Java bytecode that produced it, as well as a decompiled version of that...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1608.08970

0
0.0

Jun 29, 2018
06/18

by
Haotian Jiang

texts

######
eye 0

######
favorite 0

######
comment 0

Two-stage optimization with recourse model is an important and widely used model, which has been studied extensively these years. In this article, we will look at a new variant of it, called the two-stage optimization with recourse and revocation model. This new model differs from the traditional one in that one is allowed to revoke some of his earlier decisions and withdraw part of the earlier costs, which is not unlikely in many real applications, and is therefore considered to be more...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1610.06701

0
0.0

Jun 29, 2018
06/18

by
Sampath Kannan; Elchanan Mossel; Grigory Yaroslavtsev

texts

######
eye 0

######
favorite 0

######
comment 0

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1611.01879

0
0.0

Jun 29, 2018
06/18

by
Megha Khosla; Avishek Anand

texts

######
eye 0

######
favorite 0

######
comment 0

Hash tables are ubiquitous in computer science for efficient access to large datasets. However, there is always a need for approaches that offer compact memory utilisation without substantial degradation of lookup performance. Cuckoo hashing is an efficient technique of creating hash tables with high space utilisation and offer a guaranteed constant access time. We are given $n$ locations and $m$ items. Each item has to be placed in one of the $k\ge2$ locations chosen by $k$ random hash...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1611.07786

0
0.0

Jun 29, 2018
06/18

by
Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai

texts

######
eye 0

######
favorite 0

######
comment 0

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with $o(mn)$ total update time, where $m$ is the number of edges and $n$ is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different $m$ vs. $n$ trade-off. For the case of $m = \Theta(n^{1.5})$ the running time is $O(n^{2.47})$, just barely below...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1612.03856

0
0.0

Jun 29, 2018
06/18

by
Anubhav Baweja

texts

######
eye 0

######
favorite 0

######
comment 0

There are several data structures which can calculate the prefix sums of an array efficiently, while handling point updates on the array, such as Segment Trees and Binary Indexed Trees (BIT). Both these data structures can handle the these two operations (query and update) in $O(\log{n})$ time. In this paper, we present a data structure similar to the BIT, but with an even smaller constant. To do this, we use Zeckendorf's Theorem, a property of the Fibonacci sequence of numbers. The new data...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1612.09083

0
0.0

Jun 30, 2018
06/18

by
Yoichi Iwata; Yutaro Yamaguchi; Yuichi Yoshida

texts

######
eye 0

######
favorite 0

######
comment 0

A recent trend in the design of FPT algorithms is exploiting half-integrality of LP relaxations. That is, starting with a half-integral optimal solution to an LP relaxation, we assign integral values to variables one by one by branch and bound. This technique is general and the resulting time complexity has a small dependency on the parameter. However, the time complexity often becomes a large polynomial in the input size because we need to compute half-integral optimal LP solutions. In this...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1704.02700

0
0.0

Jun 28, 2018
06/18

by
Ger Yang; Evdokia Nikolova

texts

######
eye 0

######
favorite 0

######
comment 0

We consider optimal route planning when the objective function is a general nonlinear and non-monotonic function. Such an objective models user behavior more accurately, for example, when a user is risk-averse, or the utility function needs to capture a penalty for early arrival. It is known that as nonlinearity arises, the problem becomes NP-hard and little is known about computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1511.07412

0
0.0

Jun 29, 2018
06/18

by
Maryam Aliakbarpour; Amartya Shankha Biswas; Themistoklis Gouleakis; John Peebles; Ronitt Rubinfeld; Anak Yodpinyanee

texts

######
eye 0

######
favorite 0

######
comment 0

We study the problem of estimating the value of sums of the form $S_p \triangleq \sum \binom{x_i}{p}$ when one has the ability to sample $x_i \geq 0$ with probability proportional to its magnitude. When $p=2$, this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when $\{x_i\}$ is the degree sequence of a graph, which corresponds to counting the number of $p$-stars in a graph when one...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1601.04233

0
0.0

Jun 29, 2018
06/18

by
Blair D. Sullivan; Andrew van der Poel

texts

######
eye 0

######
favorite 0

######
comment 0

The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1603.04376

1
1.0

Jun 29, 2018
06/18

by
Andrea Lincoln; Virginia Vassilevska Williams; Joshua R. Wang; R. Ryan Williams

texts

######
eye 1

######
favorite 0

######
comment 0

Given a set of numbers, the $k$-SUM problem asks for a subset of $k$ numbers that sums to zero. When the numbers are integers, the time and space complexity of $k$-SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic self-reduction for the $k$-SUM problem which holds for both models, and has many...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1605.07285

0
0.0

Jun 30, 2018
06/18

by
Jérémy Barbay; Carlos Ochoa

texts

######
eye 0

######
favorite 0

######
comment 0

Refinements of the worst case complexity over instances of fixed input size consider the input order or the input structure, but rarely both at the same time. Barbay et al. [2016] described ``synergistic'' solutions on multisets, which take advantage of the input order and the input structure, such as to asymptotically outperform any comparable solution which takes advantage only of one of those features. We consider the extension of their results to the computation of the \textsc{Maxima Set}...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1702.08545

0
0.0

Jun 30, 2018
06/18

by
Karl Bringmann; Paweł Gawrychowski; Shay Mozes; Oren Weimann

texts

######
eye 0

######
favorite 0

######
comment 0

The edit distance between two rooted ordered trees with $n$ nodes labeled from an alphabet~$\Sigma$ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on a similar dynamic programming solution as...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1703.08940

3
3.0

Jun 26, 2018
06/18

by
Surender Baswana; Shreejit Ray Chaudhury; Keerti Choudhary; Shahbaz Khan

texts

######
eye 3

######
favorite 0

######
comment 0

Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining a DFS tree when the graph is undergoing {\em updates} (insertion and deletion of vertices or edges). We present the following results for this problem. (a) Fault tolerant DFS tree: There exists a data structure of size...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1502.02481

1
1.0

Jun 26, 2018
06/18

by
Jan-Philipp W. Kappmeier; Daniel R. Schmidt; Melanie Schmidt

texts

######
eye 1

######
favorite 0

######
comment 0

In recent years, there have been major efforts to develop data stream algorithms that process inputs in one pass over the data with little memory requirement. For the $k$-means problem, this has led to the development of several $(1+\varepsilon)$-approximations (under the assumption that $k$ is a constant), but also to the design of algorithms that are extremely fast in practice and compute solutions of high accuracy. However, when not only the length of the stream is high but also the...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1502.04265

1
1.0

Jun 27, 2018
06/18

by
Thomas Erlebach; Michael Hoffmann; Frank Kammer

texts

######
eye 1

######
favorite 0

######
comment 0

A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with $n$ nodes, we show that it is NP-hard to approximate TEXP with ratio...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1504.07976

0
0.0

Jun 30, 2018
06/18

by
Camil Demetrescu; Irene Finocchi; Giuseppe F. Italiano; Luigi Laura

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we describe the result of our experiments on Algorithms for the Food-Selection Problem, which is the fundamental problem first stated and addressed in the seminal paper \cite{pigout}. Because the key aspect of any experimental evaluation is the \textbf{reproducibility}, we detail deeply the setup of all our experiments, thus leaving to the interested eater the opportunity to reproduce all the results described in this paper. More specifically, we describe all the answers we...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1401.7591

0
0.0

Jun 30, 2018
06/18

by
Julián Mestre; José Verschae

texts

######
eye 0

######
favorite 0

######
comment 0

We consider a single machine scheduling problem that seeks to minimize a generalized cost function: given a subset of jobs we must order them so as to minimize $\sum f_j(C_j)$, where $C_j$ is the completion time of job $j$ and $f_j$ is a job-dependent cost function. This problem has received a considerably amount of attention lately, partly because it generalizes a large number of sequencing problems while still allowing constant approximation guarantees. In a recent paper, Cheung and Shmoys...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1403.0298

0
0.0

Jun 30, 2018
06/18

by
Leah Epstein; Asaf Levin

texts

######
eye 0

######
favorite 0

######
comment 0

We study classic scheduling problems on uniformly related machines. Efficient polynomial time approximation schemes (EPTAS's) are fast and practical approximation schemes. New methods and techniques are essential in developing such improved approximation schemes, and their design is a primary goal of this research agenda. We present EPTAS's for the scheduling problem of a set of jobs on uniformly related machines so as to minimize the total weighted completion time, both for the case with...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1404.1059

0
0.0

Jun 30, 2018
06/18

by
Sungjin Im; Janardhan Kulkarni; Kamesh Munagala; Kirk Pruhs

texts

######
eye 0

######
favorite 0

######
comment 0

We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online \emph{non-clairvoyant} setting. In this problem, a set of jobs $J$ arrive over time to be scheduled on a set of $M$ machines. Each job $j$ has processing length $p_j$, weight $w_j$, and is processed at a rate of $\ell_{ij}$ when scheduled on machine $i$. The online scheduler knows the values of $w_j$ and $\ell_{ij}$ upon arrival of the job, but is not aware of the quantity $p_j$. We...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1404.1943

0
0.0

Jun 30, 2018
06/18

by
Søren Dahlgaard; Mathias Bæk Tejs Knudsen; Eva Rotenberg; Mikkel Thorup

texts

######
eye 0

######
favorite 0

######
comment 0

The power of two choices is a classic paradigm for load balancing when assigning $m$ balls to $n$ bins. When placing a ball, we pick two bins according to two hash functions $h_0$ and $h_1$, and place the ball in the least loaded bin. Assuming fully random hash functions, when $m=O(n)$, Azar et al.~[STOC'94] proved that the maximum load is $\lg \lg n + O(1)$ with high probability. In this paper, we investigate the power of two choices when the hash functions $h_0$ and $h_1$ are implemented with...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1407.6846

0
0.0

Jun 27, 2018
06/18

by
Vladimir Braverman; Rafail Ostrovsky; Gregory Vorsanger

texts

######
eye 0

######
favorite 0

######
comment 0

Weighted sampling without replacement has proved to be a very important tool in designing new algorithms. Efraimidis and Spirakis (IPL 2006) presented an algorithm for weighted sampling without replacement from data streams. Their algorithm works under the assumption of precise computations over the interval [0,1]. Cohen and Kaplan (VLDB 2008) used similar methods for their bottom-k sketches. Efraimidis and Spirakis ask as an open question whether using finite precision arithmetic impacts the...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1506.01747

0
0.0

Jun 28, 2018
06/18

by
Pinyan Lu; Kuan Yang; Chihao Zhang

texts

######
eye 0

######
favorite 0

######
comment 0

Hardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic physics which connects microscopic particles and their interactions with their macroscopic and statistical properties of materials such as energy, entropy, ferromagnetism, etc. If each local interaction of the system involves only two particles, the system can be described by a graph. In this case, fully polynomial-time...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1509.05494

0
0.0

Jun 28, 2018
06/18

by
Anjeneya Swami Kare

texts

######
eye 0

######
favorite 0

######
comment 0

Let G=(V,E)(|V|=n and |E|=m) be an undirected graph with positive edge weights. Let P_{G}(s, t) be a shortest s-t path in G. Let l be the number of edges in P_{G}(s, t). The \emph{Edge Replacement Path} problem is to compute a shortest s-t path in G\{e}, for every edge e in P_{G}(s, t). The \emph{Node Replacement Path} problem is to compute a shortest s-t path in G\{v}, for every vertex v in P_{G}(s, t). In this paper we present an O(T_{SPT}(G)+m+l^2) time and O(m+l^2) space algorithm for both...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1511.06905

0
0.0

Jun 29, 2018
06/18

by
Yi Li; David P. Woodruff

texts

######
eye 0

######
favorite 0

######
comment 0

For any real number $p > 0$, we nearly completely characterize the space complexity of estimating $\|A\|_p^p = \sum_{i=1}^n \sigma_i^p$ for $n \times n$ matrices $A$ in which each row and each column has $O(1)$ non-zero entries and whose entries are presented one at a time in a data stream model. Here the $\sigma_i$ are the singular values of $A$, and when $p \geq 1$, $\|A\|_p^p$ is the $p$-th power of the Schatten $p$-norm. We show that when $p$ is not an even integer, to obtain a...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1604.08679

0
0.0

Jun 29, 2018
06/18

by
Anthony J. Cox; Fabio Garofalo; Giovanna Rosone; Marinella Sciortino

texts

######
eye 0

######
favorite 0

######
comment 0

The longest common prefix array is a very advantageous data structure that, combined with the suffix array and the Burrows-Wheeler transform, allows to efficiently compute some combinatorial properties of a string useful in several applications, especially in biological contexts. Nowadays, the input data for many problems are big collections of strings, for instance the data coming from "next-generation" DNA sequencing (NGS) technologies. In this paper we present the first lightweight...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1605.04098