3
3.0

Oct 10, 2019
10/19

by
Shilo, Benny, 1951- author

texts

######
eye 3

######
favorite 0

######
comment 0

xvi, 174 pages : 24 cm

Topics: Embryonic Development, Embryonic Structures -- cytology

7
7.0

Oct 11, 2019
10/19

by
Temples

image

######
eye 7

######
favorite 0

######
comment 0

Sun Structures is the first studio album by Temples, released February 5, 2014. It was rereleased with a second disc as Sun Restructured on November 10, 2014.

Topics: Sun Structures, Sun Restructured, Temples

0
0.0

Jun 30, 2018
06/18

by
Enrico Angelelli; Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh

texts

######
eye 0

######
favorite 0

######
comment 0

We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm.

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Hyung-Chan An; Mohit Singh; Ola Svensson

texts

######
eye 0

######
favorite 0

######
comment 0

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Daniel Hsu

texts

######
eye 0

######
favorite 0

######
comment 0

This note gives a simple analysis of the randomized approximation scheme for matrix multiplication of Drineas et al (2006) with a particular sampling distribution over outer products. The result follows from a matrix version of Bernstein's inequality. To approximate the matrix product $AB^\top$ to spectral norm error $\varepsilon\|A\|\|B\|$, it suffices to sample on the order of $(\mathrm{sr}(A) \vee \mathrm{sr}(B)) \log(\mathrm{sr}(A) \wedge \mathrm{sr}(B)) / \varepsilon^2$ outer products,...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Travis Gagie; Gonzalo Navarro; Yakov Nekrich; Alberto Ordóñez

texts

######
eye 0

######
favorite 0

######
comment 0

Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many applications, the storage space used to represent the prefix code itself can be an issue. In this paper we introduce and compare several techniques to store prefix codes. Let $N$ be the sequence length and $n$ be the alphabet size. Then a naive storage of an optimal prefix code uses $O(n\log n)$ bits. Our first technique...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Arka Bhattacharya

texts

######
eye 1

######
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

0
0.0

Jun 30, 2018
06/18

by
Glencora Borradaile; W. Sean Kennedy; Gordon Wilfong; Lisa Zhang

texts

######
eye 0

######
favorite 0

######
comment 0

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following {\sc tree augmentation} problem. Consider a mixed graph where some edges are directed and some...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Abhinav Srivastav; Denis Trystram

texts

######
eye 0

######
favorite 0

######
comment 0

We consider the classical problem of scheduling $n$ jobs with release dates on both single and identical parallel machines. We measure the quality of service provided to each job by its stretch, which is defined as the ratio of its response time to processing time. Our objective is to schedule these jobs non-preemptively so as to minimize sum stretch. So far, there have been very few results for sum stretch minimization especially for the non-preemptive case. For the preemptive version, the...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Łukasz Kowalik; Arkadiusz Socała

texts

######
eye 0

######
favorite 0

######
comment 0

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $\ell$-bounded Channel Assignment (when the edge weights are bounded by $\ell$) running in time $O^*((2\sqrt{\ell+1})^n)$. This is the first algorithm which breaks the $(O(\ell))^n$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. A major open problem asks whether Channel Assignment admits a $O(c^n)$-time...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Lin Chen; Nicole Megow; Kevin Schewior

texts

######
eye 1

######
favorite 0

######
comment 0

We consider the online resource minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule on a minimum number of machines. We rigorously study this problem and derive various algorithms with small constant competitive ratios for interesting restricted problem variants. As the most important special case, we consider scheduling jobs with agreeable deadlines. We provide the first constant ratio competitive...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Konstantin Makarychev; Yury Makarychev

texts

######
eye 0

######
favorite 0

######
comment 0

We give a bi-criteria approximation algorithm for the Minimum Nonuniform Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar (2014). In this problem, we are given a graph $G=(V,E)$ on $n$ vertices and $k$ numbers $\rho_1,\dots, \rho_k$. The goal is to partition the graph into $k$ disjoint sets $P_1,\dots, P_k$ satisfying $|P_i|\leq \rho_i n$ so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of $O(\sqrt{\log n...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Petra Berenbrink; Ralf Klasing; Adrian Kosowski; Frederik Mallmann-Trenn; Przemyslaw Uznanski

texts

######
eye 1

######
favorite 0

######
comment 0

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of $n$ processors is connected into a $d$-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Saeid Sahraei; Michael C. Gastpar

texts

######
eye 0

######
favorite 0

######
comment 0

The Shortest Lattice Vector (SLV) problem is in general hard to solve, except for special cases (such as root lattices and lattices for which an obtuse superbase is known). In this paper, we present a new class of SLV problems that can be solved efficiently. Specifically, if for an $n$-dimensional lattice, a Gram matrix is known that can be written as the difference of a diagonal matrix and a positive semidefinite matrix of rank $k$ (for some constant $k$), we show that the SLV problem can be...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Gábor Rétvári; János Tapolcai; Attila Kőrösi; András Majdán; Zalán Heszberger

texts

######
eye 0

######
favorite 0

######
comment 0

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community, by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 30, 2018
06/18

by
Carl Barton; Alice Heliou; Laurent Mouchard; Solon P. Pissis

texts

######
eye 3

######
favorite 0

######
comment 0

An absent word of a word y of length n is a word that does not occur in y. It is a minimal absent word if all its proper factors occur in y. Minimal absent words have been computed in genomes of organisms from all domains of life; their computation provides a fast alternative for measuring approximation in sequence comparison. There exists an O(n)-time and O(n)-space algorithm for computing all minimal absent words on a fixed-sized alphabet based on the construction of suffix automata...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Michael B. Cohen; Gary L. Miller; Jakub W. Pachocki; Richard Peng; Shen Chen Xu

texts

######
eye 1

######
favorite 0

######
comment 0

We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discounting highly stretched edges by taking their $p$-th power for some $0 < p < 1$, is directly related to performances of existing algorithms. This discounting of high-stretch edges allows us to treat many classes of edges with coarser granularity. It leads to a two-pass approach that combines bottom-up clustering...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Miguel A. Lerma

texts

######
eye 1

######
favorite 0

######
comment 0

We find large lower bounds for a certain family of algorithms, and prove that such bounds are limited only by natural computability arguments.

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Raed Jaberi

texts

######
eye 0

######
favorite 0

######
comment 0

Let $G$ be a directed graph. A \textit{$2$-directed block} in $G$ is a maximal vertex set $C^{2d}\subseteq V$ with $|C^{2d}|\geq 2$ such that for each pair of distinct vertices $x,y \in C^{2d}$, there exist two vertex-disjoint paths from $x$ to $y$ and two vertex-disjoint paths from $y$ to $x$ in $G$. In contrast to the $2$-vertex-connected components of $G$, the subgraphs induced by the $2$-directed blocks may consist of few or no edges. In this paper we present two algorithms for computing...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Yi-Kai Wang

texts

######
eye 0

######
favorite 0

######
comment 0

The theoretical models providing mathematical abstractions for several significant optimization problems in machine learning, combinatorial optimization, computer vision and statistical physics have intrinsic similarities. We propose a unified framework to model these computation tasks where the structures of these optimization problems are encoded by functions attached on the vertices and edges of a graph. We show that computing MAX 2-CSP admits polynomial-time approximation scheme (PTAS) on...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Faisal N. Abu-Khzam; Édouard Bonnet; Florian Sikora

texts

######
eye 0

######
favorite 0

######
comment 0

In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs $G_1$ and $G_2$, one looks for a graph with the maximum number of vertices being both an induced subgraph of $G_1$ and $G_2$. MCIS is among the most studied classical NP-hard problems. It remains NP-hard on many graph classes including forests. In this paper, we study the parameterized complexity of MCIS. As a generalization of \textsc{Clique}, it is W[1]-hard parameterized by the size of the solution. Being...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Raed Jaberi

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper we consider the problem of computing the $2$-vertex-connected components ($2$-vccs) of directed graphs. We present two new algorithms for solving this problem. The first algorithm runs in $O(mn^{2})$ time, the second in $O(nm)$ time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in $O(nm^{2})$ time. In this paper, we investigate the relationship between $2$-vccs and dominator trees. We also present an algorithm for computing the $3$-vertex-connected...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Søren Dahlgaard; Mikkel Thorup

texts

######
eye 0

######
favorite 0

######
comment 0

A random hash function $h$ is $\varepsilon$-minwise if for any set $S$, $|S|=n$, and element $x\in S$, $\Pr[h(x)=\min h(S)]=(1\pm\varepsilon)/n$. Minwise hash functions with low bias $\varepsilon$ have widespread applications within similarity estimation. Hashing from a universe $[u]$, the twisted tabulation hashing of P\v{a}tra\c{s}cu and Thorup [SODA'13] makes $c=O(1)$ lookups in tables of size $u^{1/c}$. Twisted tabulation was invented to get good concentration for hashing based sampling....

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Djamal Belazzougui; Travis Gagie; Simon Gog; Giovanni Manzini; Jouni Sirén

texts

######
eye 0

######
favorite 0

######
comment 0

Intuitively, if two strings $S_1$ and $S_2$ are sufficiently similar and we already have an FM-index for $S_1$ then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for $S_2$. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Antonios Antoniadis; Chien-Chung Huang; Sebastian Ott

texts

######
eye 0

######
favorite 0

######
comment 0

We study classical deadline-based preemptive scheduling of tasks in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each task is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Bo Peng; Zhipeng Lu; T. C. E. Cheng

texts

######
eye 0

######
favorite 0

######
comment 0

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to tackle the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure and a reference solution determination method. To test the performance of TS/PR, we apply it to tackle almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Tomas Flouri; Emanuele Giaquinta; Kassian Kobert; Esko Ukkonen

texts

######
eye 1

######
favorite 0

######
comment 0

The longest common substring with $k$-mismatches problem is to find, given two strings $S_1$ and $S_2$, a longest substring $A_1$ of $S_1$ and $A_2$ of $S_2$ such that the Hamming distance between $A_1$ and $A_2$ is $\le k$. We introduce a practical $O(nm)$ time and $O(1)$ space solution for this problem, where $n$ and $m$ are the lengths of $S_1$ and $S_2$, respectively. This algorithm can also be used to compute the matching statistics with $k$-mismatches of $S_1$ and $S_2$ in $O(nm)$ time...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Alex Gavryushkin; Bakhadyr Khoussainov; Mikhail Kokho; Jiamou Liu

texts

######
eye 0

######
favorite 0

######
comment 0

We investigate dynamic algorithms for the interval scheduling problem. Our algorithm runs in amortised time $O(\log n)$ for query operation and $O(d\log^2 n)$ for insertion and removal operations, where $n$ and $d$ are the maximal numbers of intervals and pairwise overlapping intervals respectively. We also show that for a monotonic set, that is when no interval properly contains another interval, the amortised complexity is $O(\log n)$ for both query and update operations. We compare the two...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Tamal K. Dey; Pan Peng; Alfred Rossi; Anastasios Sidiropoulos

texts

######
eye 0

######
favorite 0

######
comment 0

A popular graph clustering method is to consider the embedding of an input graph into R^k induced by the first k eigenvectors of its Laplacian, and to partition the graph via geometric manipulations on the resulting metric space. Despite the practical success of this methodology, there is limited understanding of several heuristics that follow this framework. We provide theoretical justification for one such natural and computationally efficient variant. Our result can be summarized as follows....

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Ivan Bliznets; Fedor V. Fomin; Marcin Pilipczuk; Michał Pilipczuk

texts

######
eye 0

######
favorite 0

######
comment 0

In the Proper 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 a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999], who showed an algorithm for the problem working in $O(16^k (n + m))$ time....

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Svante Janson; Alfredo Viola

texts

######
eye 0

######
favorite 0

######
comment 0

We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on q-calculus) to...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Zhengjun Cao; Lihua Liu

texts

######
eye 1

######
favorite 0

######
comment 0

We put forth a new string matching algorithm which matches the pattern from neither the left nor the right end, instead a special position. Comparing with the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm, the new algorithm is more flexible to pick the position for starting comparisons. The option really brings it a saving in cost.

Topics: Data Structures and Algorithms, Computing Research Repository

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

99
99

texts

######
eye 99

######
favorite 0

######
comment 0

Tension leg platforms (TLP) are used for deep water oil exploration. Their behavior are highly nonlinear due to large structural displacements and fluid motion-structure interaction. Therefore the nonlinear dynamic characteristics of TLP under hydrodynamic forces is necessary for determining the maximum deformations and stresses. In this paper, numerical studies are conducted to compare the coupled responses of the triangular TLP with that of the square TLP. A numerical study...

Topics: Compliant Structures, Coupling Effect, Hydrodynamic Wave Forces

0
0.0

Jun 30, 2018
06/18

by
Sukhpal Singh Ghuman; Emanuele Giaquinta; Jorma Tarhio

texts

######
eye 0

######
favorite 0

######
comment 0

We present two variations of Duval's algorithm for computing the Lyndon factorization of a word. The first algorithm is designed for the case of small alphabets and is able to skip a significant portion of the characters of the string, for strings containing runs of the smallest character in the alphabet. Experimental results show that it is faster than Duval's original algorithm, more than ten times in the case of long DNA strings. The second algorithm computes, given a run-length encoded...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Alexandr Andoni; Robert Krauthgamer; David P. Woodruff

texts

######
eye 0

######
favorite 0

######
comment 0

We study the problem of sketching an input graph, so that given the sketch, one can estimate the weight of any cut in the graph within factor $1+\epsilon$. We present lower and upper bounds on the size of a randomized sketch, focusing on the dependence on the accuracy parameter $\epsilon>0$. First, we prove that for every $\epsilon > 1/\sqrt n$, every sketch that succeeds (with constant probability) in estimating the weight of all cuts $(S,\bar S)$ in an $n$-vertex graph (simultaneously),...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Zengfeng Huang; Wai Ming Tai; Ke Yi

texts

######
eye 0

######
favorite 0

######
comment 0

The traditional requirement for a randomized streaming algorithm is just {\em one-shot}, i.e., algorithm should be correct (within the stated $\eps$-error bound) at the end of the stream. In this paper, we study the {\em tracking} problem, where the output should be correct at all times. The standard approach for solving the tracking problem is to run $O(\log m)$ independent instances of the one-shot algorithm and apply the union bound to all $m$ time instances. In this paper, we study if this...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Piotr Indyk; Michael Kapralov

texts

######
eye 0

######
favorite 0

######
comment 0

We give an algorithm for $\ell_2/\ell_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of \cite{DIPW} for non-adaptive algorithms up to constant factors for any $k\leq N^{1-\delta}$. The algorithm runs in $\tilde O(N)$ time. Our algorithm extends to higher dimensions, leading to sample complexity of $O_d(k\log N)$, which is optimal up to constant factors for any $d=O(1)$. These are the first sample optimal algorithms for these problems. A...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Xingfu Li; Daming Zhu

texts

######
eye 0

######
favorite 0

######
comment 0

This paper focuses on finding a spanning tree of a graph to maximize the number of its internal vertices. We present an approximation algorithm for this problem which can achieve a performance ratio $\frac{4}{3}$ on undirected simple graphs. This improves upon the best known approximation algorithm with performance ratio $\frac{5}{3}$ before. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree, which reveals that a spanning tree of an...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Takanori Maehara; Mitsuru Kusumoto; Ken-ichi Kawarabayashi

texts

######
eye 1

######
favorite 0

######
comment 0

SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for computing SimRank, their computational costs are very high. In this paper, we propose a new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem. By using this technique, we can solve many SimRank problems, such as single-pair...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Eric Price

texts

######
eye 0

######
favorite 0

######
comment 0

Given a database, a common problem is to find the pairs or $k$-tuples of items that frequently co-occur. One specific problem is to create a small space "sketch" of the data that records which $k$-tuples appear in more than an $\epsilon$ fraction of rows of the database. We improve the lower bound of Liberty, Mitzenmacher, and Thaler [LMT14], showing that $\Omega(\frac{1}{\epsilon}d \log (\epsilon d))$ bits are necessary even in the case of $k=2$. This matches the sampling upper bound...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Jonathan Ullman

texts

######
eye 0

######
favorite 0

######
comment 0

A wide variety of fundamental data analyses in machine learning, such as linear and logistic regression, require minimizing a convex function defined by the data. Since the data may contain sensitive information about individuals, and these analyses can leak that sensitive information, it is important to be able to solve convex minimization in a privacy-preserving way. A series of recent results show how to accurately solve a single convex minimization problem in a differentially private...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
John Fearnley; Rahul Savani

texts

######
eye 1

######
favorite 0

######
comment 0

The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE-complete to find the solution that is computed by...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Russell A. Brown

texts

######
eye 1

######
favorite 0

######
comment 0

The original description of the k-d tree recognized that rebalancing techniques, such as are used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in order to build a balanced k-d tree, it is necessary to find the median of the data for each recursive subdivision of those data. The sort or selection that is used to find the median for each subdivision strongly influences the computational complexity of building a k-d tree. This paper discusses an alternative...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Travis Gagie; Simon J. Puglisi

texts

######
eye 0

######
favorite 0

######
comment 0

The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advantage of the similarity between those genomes. Several authors have recently suggested searching or indexing only one reference genome and the parts of the other genomes where they differ. In this paper we survey the twenty-year history of this idea and discuss its relation to kernelization in parameterized complexity.

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Srikrishnan Divakaran

texts

######
eye 1

######
favorite 0

######
comment 0

For the static list update problem, given an ordered list $\rho_0$ (an ordering of the list $L$ = \{ $a_a, a_2, ..., a_l$ \}), and a sequence $\sigma = (\sigma_1, \sigma_2, ..., \sigma_m)$ of requests for items in $L$, we characterize the list reorganizations in an optimal offline solution in terms of an initial permutation of the list followed by a sequence of $m$ {\em element transfers}, where an element transfer is a type of list reorganization where only the requested item can be moved....

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Joseph; Naor; David Wajc

texts

######
eye 0

######
favorite 0

######
comment 0

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(1-\frac{1}{e})$-competitive (\cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by Buchbinder et al.~\cite{buchbinder2007online}, graphs which we call...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 30, 2018
06/18

by
Shuchi Chawla; Konstantin Makarychev; Tselil Schramm; Grigory Yaroslavtsev

texts

######
eye 1

######
favorite 0

######
comment 0

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: - For complete graphs our appoximation is $2.06 - \varepsilon$ for a fixed constant $\varepsilon$, which almost matches the previously known integrality gap of $2$. - For complete $k$-partite graphs our approximation is $3$. We also show a matching integrality gap. - For complete graphs with edge weights...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Danupon Nanongkai

texts

######
eye 0

######
favorite 0

######
comment 0

A distributed network is modeled by a graph having $n$ nodes (processors) and diameter $D$. We study the time complexity of approximating {\em weighted} (undirected) shortest paths on distributed networks with a $O(\log n)$ {\em bandwidth restriction} on edges (the standard synchronous \congest model). The question whether approximation algorithms help speed up the shortest paths (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 30, 2018
06/18

by
Neal E. Young

texts

######
eye 0

######
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

2
2.0

Jun 30, 2018
06/18

by
Maxim Babenko; Paweł Gawrychowski; Tomasz Kociumaka; Tatiana Starikovskaya

texts

######
eye 2

######
favorite 0

######
comment 0

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size $\sigma\leq n$, our method builds the wavelet tree in $O(n \log \sigma/ \sqrt{\log{n}})$ time, improving upon the state-of-the-art algorithm by a factor of $\sqrt{\log n}$. As a consequence, given an array of n integers we can construct in $O(n \sqrt{\log n})$ time a data structure consisting...

Topics: Data Structures and Algorithms, Computing Research Repository

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