14
14

Jul 1, 2015
07/15

by
Eng.ABAHO G Gershome

texts

######
eye 14

######
favorite 0

######
comment 0

PhD-RESEARCH AREA

Topics: Corrosion, reinforcement, structures

94
94

Apr 2, 2015
04/15

by
Innovative Research Publications

texts

######
eye 94

######
favorite 0

######
comment 0

In this paper we introduce the notion of a ternary Γ- semigroup is introduced and some examples are given. Further the terms commutative ternary Γ-semigroup, quasi commutative ternary Γ-semigroup, normal ternary Γ- semigroup, left pseudo commutative ternary Γ-semigroup, right pseudo commutative ternary Γ-semigroup are introduced and characterized them. In section 2, the terms; ternary Γ-subsemigroup, ternary Γ-subsemigroup generated by a subset, cyclic ternary Γ-subsemigroup of a...

Topics: ternary Γ-semigroup, Algebraic structures

0
0.0

Jun 28, 2018
06/18

by
Jie You; Jianxin Wang; Yixin Cao

texts

######
eye 0

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

3
3.0

Jun 28, 2018
06/18

by
Yin Tat Lee; Richard Peng; Daniel A. Spielman

texts

######
eye 3

######
favorite 0

######
comment 0

We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations. We show that these matrices have constant-factor approximations of the form $L L^{T}$, where $L$ is a lower-triangular matrix with a number of nonzero entries linear in its dimension. Furthermore linear systems in $L$ and $L^{T}$ can be solved in $O (n)$ work and $O(\log{n}\log^2\log{n})$ depth, where $n$ is the dimension of the matrix. We present...

Topics: Computing Research Repository, Data Structures and Algorithms

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

4
4.0

Jun 28, 2018
06/18

by
David Gibb; Bruce Kapron; Valerie King; Nolan Thorn

texts

######
eye 4

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

1
1.0

Jun 28, 2018
06/18

by
Daniel Lokshtanov

texts

######
eye 1

######
favorite 0

######
comment 0

In the Integer Quadratic Programming problem input is an n*n integer matrix Q, an m*n integer matrix A and an m-dimensional integer vector b. The task is to find a vector x in Z^n, minimizing x^TQx, subject to Ax

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 27, 2018
06/18

by
Raphael Reitzig; Sebastian Wild

texts

######
eye 2

######
favorite 0

######
comment 0

Proportional apportionment is the problem of assigning seats to parties according to their relative share of votes. Divisor methods are the de-facto standard solution, used in many countries. In recent literature, there are two algorithms that implement divisor methods: one by Cheng and Eppstein (ISAAC, 2014) has worst-case optimal running time but is complex, while the other (Pukelsheim, 2014) is relatively simple and fast in practice but does not offer worst-case guarantees. We demonstrate...

Topics: Data Structures and Algorithms, Computing Research Repository

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

5
5.0

Jun 28, 2018
06/18

by
Mark Braverman; Ran Gelles; Jieming Mao; Rafail Ostrovsky

texts

######
eye 5

######
favorite 0

######
comment 0

We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol. In this more general noise model,...

Topics: Computing Research Repository, Data Structures and Algorithms

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

3
3.0

Jun 27, 2018
06/18

by
Yann Disser; Max Klimm; Elisabeth Lübbecke

texts

######
eye 3

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

1
1.0

Jun 28, 2018
06/18

by
Andreas Björklund; Petteri Kaski; Łukasz Kowalik

texts

######
eye 1

######
favorite 0

######
comment 0

The gist of many (NP-)hard combinatorial problems is to decide whether a universe of $n$ elements contains a witness consisting of $k$ elements that match some prescribed pattern. For some of these problems there are known advanced algebra-based FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NO-decision oracle into an algorithm for extracting a single witness, with an objective to obtain practical scalability for...

Topics: Computing Research Repository, Data Structures and Algorithms

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

0
0.0

Jun 26, 2018
06/18

by
Fedor V. Fomin; Petr A. Golovach; Nikolay Karpov; Alexander S. Kulikov

texts

######
eye 0

######
favorite 0

######
comment 0

The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure, which is the total weight of vertices in its closed neighborhood. In order to minimize the risk of intercepting the information, we are interested in selecting a secluded path, i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph...

Topics: Data Structures and Algorithms, Computing Research Repository

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

4
4.0

Jun 28, 2018
06/18

by
Stephen Alstrup; Inge Li Gørtz; Esben Bistrup Halvorsen; Ely Porat

texts

######
eye 4

######
favorite 0

######
comment 0

We consider distance labeling schemes for trees: given a tree with $n$ nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the distance in the tree between the two nodes. A lower bound by Gavoille et. al. (J. Alg. 2004) and an upper bound by Peleg (J. Graph Theory 2000) establish that labels must use $\Theta(\log^2 n)$ bits\footnote{Throughout this paper we use $\log$ for $\log_2$.}. Gavoille et. al. (ESA...

Topics: Computing Research Repository, Data Structures and Algorithms

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

0
0.0

Jun 28, 2018
06/18

by
Paweł Gawrychowski; Tomohiro I; Shunsuke Inenaga; Dominik Köppl; Florin Manea

texts

######
eye 0

######
favorite 0

######
comment 0

For $\alpha\geq 1$, an $\alpha$-gapped repeat in a word $w$ is a factor $uvu$ of $w$ such that $|uv|\leq \alpha |u|$; the two factors $u$ in such a repeat are called arms, while the factor $v$ is called gap. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right or, respectively, to the left. In this paper we show that the number of maximal $\alpha$-gapped repeats that may occur in a word is upper bounded by $18\alpha n$. This allows us...

Topics: Data Structures and Algorithms, Computing Research Repository

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

10
10.0

Jun 28, 2018
06/18

by
Akanksha Agrawal; Sudeshna Kolay; Daniel Lokshtanov; Saket Saurabh

texts

######
eye 10

######
favorite 0

######
comment 0

A graph $G$ is called a \emph{block graph} if each maximal $2$-connected component of $G$ is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective of fixed parameter tractable (FPT) and kernelization algorithm. In particular, an input to Block Graph Vertex Deletion consists of a graph $G$ and a positive integer $k$ and the objective to check whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that the graph induced on $V(G)\setminus S$ is a...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 28, 2018
06/18

by
Sahar Bsaybes; Alain Quilliot; Annegret K. Wagler; Jan-Thierry Wegener

texts

######
eye 0

######
favorite 0

######
comment 0

In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the numbers of free places and cars in each station. This leads to the problem of relocating cars between stations, which can be modeled within the framework of a metric task system. In this paper, we focus on the Static Relocation Problem, where the...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 28, 2018
06/18

by
Luís M. S. Russo

texts

######
eye 0

######
favorite 0

######
comment 0

We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence. We reduce this claim to a regular access bound, which seems plausible and might be easier to prove. This approach may be useful to establish dynamic optimality.

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 28, 2018
06/18

by
Alexandr Andoni; Jiecao Chen; Robert Krauthgamer; Bo Qin; David P. Woodruff; Qin Zhang

texts

######
eye 0

######
favorite 0

######
comment 0

We undertake a systematic study of sketching a quadratic form: given an $n \times n$ matrix $A$, create a succinct sketch $\textbf{sk}(A)$ which can produce (without further access to $A$) a multiplicative $(1+\epsilon)$-approximation to $x^T A x$ for any desired query $x \in \mathbb{R}^n$. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size $\Theta(\epsilon^{-2} n)$, via the Johnson-Lindenstrauss lemma, achieving the...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 28, 2018
06/18

by
Takuya Takagi; Shunsuke Inenaga; Hiroki Arimura

texts

######
eye 1

######
favorite 0

######
comment 0

In this paper, we consider fully-online construction of indexing data structures for multiple texts. Let $T = {T_1, ..., T_K}$ be a collection of texts. By fully on-line, we mean that a new character can be appended to any text in $T$ at any time. This is a natural generalization of semi-online construction of indexing data structures for multiple texts in which, after a new character is appended to the $k$th text $T_k$, then its previous texts $T_1, ..., T_{k-1}$ will remain static. Our fully...

Topics: Computing Research Repository, Data Structures and Algorithms

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

0
0.0

Jun 28, 2018
06/18

by
Zhengyu Wang

texts

######
eye 0

######
favorite 0

######
comment 0

We present a randomized algorithm for dynamic graph connectivity. With failure probability less than $1/n^c$ (for any constant $c$ we choose), our solution has worst case running time $O(\log^3 n)$ per edge insertion, $O(\log^4 n)$ per edge deletion, and $O(\log n/\log\log n)$ per query, where $n$ is the number of vertices. The previous best algorithm has worst case running time $O(\log^4 n)$ per edge insertion and $O(\log^5 n)$ per edge deletion. The improvement is made by reducing the...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 28, 2018
06/18

by
Takuro Fukunaga

texts

######
eye 3

######
favorite 0

######
comment 0

Given an undirected graph on a node set $V$ and positive integers $k$ and $m$, a $k$-connected $m$-dominating set ($(k,m)$-CDS) is defined as a subset $S$ of $V$ such that each node in $V \setminus S$ has at least $m$ neighbors in $S$, and a $k$-connected subgraph is induced by $S$. The weighted $(k,m)$-CDS problem is to find a minimum weight $(k,m)$-CDS in a given node-weighted graph. The problem is called the unweighted $(k,m)$-CDS problem if the objective is to minimize the cardinality of a...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 28, 2018
06/18

by
Tsvi Kopelowitz; Ely Porat

texts

######
eye 1

######
favorite 0

######
comment 0

The algorithmic tasks of computing the Hamming distance between a given pattern of length $m$ and each location in a text of length $n$ is one of the most fundamental algorithmic tasks in string algorithms. Unfortunately, there is evidence that for a text $T$ of size $n$ and a pattern $P$ of size $m$, one cannot compute the exact Hamming distance for all locations in $T$ in time which is less than $\tilde O(n\sqrt m)$. However, Karloff~\cite{karloff} showed that if one is willing to suffer a...

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 27, 2018
06/18

by
Stefan Fafianie; Stefan Kratsch

texts

######
eye 2

######
favorite 0

######
comment 0

We investigate whether kernelization results can be obtained if we restrict kernelization algorithms to run in logarithmic space. This restriction for kernelization is motivated by the question of what results are attainable for preprocessing via simple and/or local reduction rules. We find kernelizations for d-Hitting Set(k), d-Set Packing(k), Edge Dominating Set(k) and a number of hitting and packing problems in graphs, each running in logspace. Additionally, we return to the question of...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 27, 2018
06/18

by
Martin Wimmer; Jakob Gruber; Jesper Larsson Träff; Philippas Tsigas

texts

######
eye 1

######
favorite 0

######
comment 0

Priority queues are data structures which store keys in an ordered fashion to allow efficient access to the minimal (maximal) key. Priority queues are essential for many applications, e.g., Dijkstra's single-source shortest path algorithm, branch-and-bound algorithms, and prioritized schedulers. Efficient multiprocessor computing requires implementations of basic data structures that can be used concurrently and scale to large numbers of threads and cores. Lock-free data structures promise...

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 26, 2018
06/18

by
Sergio Cabello; Pablo Pérez-Lantero

texts

######
eye 2

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

4
4.0

Jun 28, 2018
06/18

by
Joe Cheriyan; Zhihan Gao

texts

######
eye 4

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

0
0.0

Jun 26, 2018
06/18

by
Christos Boutsidis; Edo Liberty; Maxim Sviridenko

texts

######
eye 0

######
favorite 0

######
comment 0

This paper defines weak-$\alpha$-supermodularity for set functions. Many optimization objectives in machine learning and data mining seek to minimize such functions under cardinality constrains. We prove that such problems benefit from a greedy extension phase. Explicitly, let $S^*$ be the optimal set of cardinality $k$ that minimizes $f$ and let $S_0$ be an initial solution such that $f(S_0)/f(S^*) \le \rho$. Then, a greedy extension $S \supset S_0$ of size $|S| \le |S_0| + \lceil \alpha k...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 27, 2018
06/18

by
Alexandros Efentakis; Dieter Pfoser

texts

######
eye 3

######
favorite 0

######
comment 0

Quite recently, the algorithmic community has focused on solving multiple shortest-path query problems beyond simple vertex-to-vertex queries, especially in the context of road networks. Unfortunately, this research cannot be generalized for large-scale graphs, e.g., social or collaboration networks, or to efficiently answer Reverse k-Nearest Neighbor (RkNN) queries, which are of practical relevance to a wide range of applications. To remedy this, we propose ReHub, a novel main-memory algorithm...

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 28, 2018
06/18

by
Jasper C. H. Lee; Paul Valiant

texts

######
eye 2

######
favorite 0

######
comment 0

We introduce a polynomial time algorithm for optimizing the class of star-convex functions, under no restrictions except boundedness on a region about the origin, and Lebesgue measurability. The algorithm's performance is polynomial in the requested number of digits of accuracy, contrasting with the previous best known algorithm of Nesterov and Polyak that has exponential dependence, and that further requires Lipschitz second differentiability of the function, but has milder dependence on the...

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 28, 2018
06/18

by
Jon Lee; Viswanath Nagarajan; Xiangkun Shen

texts

######
eye 0

######
favorite 0

######
comment 0

An instance of the graph-constrained max-cut (GCMC) problem consists of (i) an undirected graph G and (ii) edge-weights on a complete undirected graph on the same vertex set. The objective is to find a subset of vertices satisfying some graph-based constraint in G that maximizes the total weight of edges in the cut. The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 27, 2018
06/18

by
Greg Bodwin; Virginia Vassilevska Williams

texts

######
eye 1

######
favorite 0

######
comment 0

We make improvements to the upper bounds on several popular types of distance preserving graph sketches. These sketches are all various restrictions of the {\em additive pairwise spanner} problem, in which one is given an undirected unweighted graph $G$, a set of node pairs $P$, and an error allowance $+\beta$, and one must construct a sparse subgraph $H$ satisfying $\delta_H(u, v) \le \delta_G(u, v) + \beta$ for all $(u, v) \in P$. The first part of our paper concerns {\em pairwise distance...

Topics: Computing Research Repository, Data Structures and Algorithms

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

1
1.0

Jun 27, 2018
06/18

by
Kyle Fox; Philip N. Klein; Shay Mozes

texts

######
eye 1

######
favorite 0

######
comment 0

Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge costs between the parts is minimized. We give a polynomial time bicriteria approximation scheme for bisection on planar graphs. Specifically, let $W$ be the total weight of all nodes in a planar graph $G$. For any constant $\varepsilon > 0$, our algorithm outputs a bipartition of the nodes such that each part...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 27, 2018
06/18

by
Marc Bury; Chris Schwiegelshohn

texts

######
eye 3

######
favorite 0

######
comment 0

This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using $\tilde{O}(n^{4/5})$ space which also extends to weighted matching. Using previous...

Topics: Computing Research Repository, Data Structures and Algorithms

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

2
2.0

Jun 27, 2018
06/18

by
Christian Konrad

texts

######
eye 2

######
favorite 0

######
comment 0

We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass $2$-approximation streaming algorithm can be easily obtained with space $O(n \log n)$, where $n$ denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space $O(n^{3/2-\delta})$ is granted, for every $\delta >...

Topics: Computing Research Repository, Data Structures and Algorithms

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

2
2.0

Jun 27, 2018
06/18

by
Sepehr Assadi; Sanjeev Khanna; Yang Li; Grigory Yaroslavtsev

texts

######
eye 2

######
favorite 0

######
comment 0

We resolve the space complexity of linear sketches for approximating the maximum matching problem in dynamic graph streams where the stream may include both edge insertion and deletion. Specifically, we show that for any $\epsilon > 0$, there exists a one-pass streaming algorithm, which only maintains a linear sketch of size $\tilde{O}(n^{2-3\epsilon})$ bits and recovers an $n^\epsilon$-approximate maximum matching in dynamic graph streams, where $n$ is the number of vertices in the graph....

Topics: Computing Research Repository, Data Structures and Algorithms

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

4
4.0

Jun 27, 2018
06/18

by
Elisabetta Bergamini; Henning Meyerhenke

texts

######
eye 4

######
favorite 0

######
comment 0

Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of betweenness in evolving networks. In previous work we proposed the first semi-dynamic algorithms that recompute an approximation of betweenness in...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 27, 2018
06/18

by
Talya Eden; Amit Levi; Dana Ron; C. Seshadhri

texts

######
eye 3

######
favorite 0

######
comment 0

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a {\em sublinear-time\/} algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter $0

Topics: Data Structures and Algorithms, Computing Research Repository

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

13
13

Jun 26, 2018
06/18

by
Jeffrey Ling; Kai Xiao; Dai Yang

texts

######
eye 13

######
favorite 0

######
comment 0

In this paper we study a variety of novel online algorithm problems inspired by the game Mousehunt. We consider a number of basic models that approximate the game, and we provide solutions to these models using Markov Decision Processes, deterministic online algorithms, and randomized online algorithms. We analyze these solutions' performance by deriving results on their competitive ratios.

Topics: Data Structures and Algorithms, Computing Research Repository

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

0
0.0

Jun 27, 2018
06/18

by
Matthew Sackman

texts

######
eye 0

######
favorite 0

######
comment 0

Consistent Hashing functions are widely used for load balancing across a variety of applications. However, the original presentation and typical implementations of Consistent Hashing rely on randomised allocation of hash codes to keys which results in a flawed and approximately-uniform allocation of keys to hash codes. We analyse the desired properties and present an algorithm that perfectly achieves them without resorting to any random distributions. The algorithm is simple and adds to our...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 26, 2018
06/18

by
Satoru Iwata; Shin-ichi Tanigawa; Yuichi Yoshida

texts

######
eye 1

######
favorite 0

######
comment 0

This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $\max\{1/3, 1/(1+a)\}$-approximation by Ward and \v{Z}ivn\'y~(SODA'14), where $a=\max\{1, \sqrt{(k-1)/4}\}$. We also show that for monotone $k$-submodular functions there is a polynomial-time $k/(2k-1)$-approximation algorithm while for any $\varepsilon>0$ a $((k+1)/2k+\varepsilon)$-approximation algorithm for maximizing monotone...

Topics: Data Structures and Algorithms, Computing Research Repository

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

1
1.0

Jun 28, 2018
06/18

by
Niv Buchbinder; Moran Feldman

texts

######
eye 1

######
favorite 0

######
comment 0

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the...

Topics: Computing Research Repository, Data Structures and Algorithms

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

1
1.0

Jun 28, 2018
06/18

by
Mithilesh Kumar; Daniel Lokshtanov

texts

######
eye 1

######
favorite 0

######
comment 0

A tournament is a directed graph T such that every pair of vertices are connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the Feedback Vertex Set problem in tournaments. Here input is a tournament T and integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for Feedback Vertex Set in Tournaments. The running time of our algorithm is upper bounded by...

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 26, 2018
06/18

by
Laura Rebollo-Neira

texts

######
eye 2

######
favorite 0

######
comment 0

Cooperative Greedy Pursuit Strategies are considered for approximating a signal partition subjected to a global constraint on sparsity. The approach aims at producing a high quality sparse approximation of the whole signal, using highly coherent redundant dictionaries. The cooperation takes place by ranking the partition units for their sequential stepwise approximation, and is realized by means of i)forward steps for the upgrading of an approximation and/or ii) backward steps for the...

Topics: Computing Research Repository, Data Structures and Algorithms

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

2
2.0

Jun 27, 2018
06/18

by
Shay Mozes; Eyal E. Skop

texts

######
eye 2

######
favorite 0

######
comment 0

We consider distance queries in vertex labeled planar graphs. For any fixed $0 < \epsilon \leq 1/2$ we show how to preprocess a planar graph with vertex labels and edge lengths into a data structure that answers queries of the following form. Given a vertex $u$ and a label $\lambda$ return a $(1+O(\epsilon))$-approximation of the distance between $u$ and its closest vertex with label $\lambda$. For an undirected $n$-vertex planar graph the preprocessing time is $O(\epsilon^{-2}n\lg^{3}{n})$,...

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 28, 2018
06/18

by
Veli Mäkinen; Valeria Staneva; Alexandru Tomescu; Daniel Valenzuela

texts

######
eye 2

######
favorite 0

######
comment 0

In the classical interval scheduling type of problems, a set of $n$ jobs, characterized by their start and end time, need to be executed by a set of machines, under various constraints. In this paper we study a new variant in which the jobs need to be assigned to at most $k$ identical machines, such that the minimum number of machines that are busy at the same time is maximized. This is relevant in the context of genome sequencing and haplotyping, specifically when a set of DNA reads aligned to...

Topics: Computing Research Repository, Data Structures and Algorithms

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

3
3.0

Jun 27, 2018
06/18

by
Ali Alatabbi; Costas S. Iliopoulos; Alessio Langiu; M. Sohel Rahman

texts

######
eye 3

######
favorite 0

######
comment 0

In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple $O(\sigma~ n^2)$ time algorithm, where $n$ is the length of the strings and $\sigma$ is the alphabet size, and a sub-quadratic running time solution for the binary string case, both having linear space requirement. Furthermore, we present a modified algorithm applying some interesting tricks and experimentally show that the resulting algorithm runs faster.

Topics: Data Structures and Algorithms, Computing Research Repository

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

2
2.0

Jun 27, 2018
06/18

by
Viswanath Nagarajan; Cong Shi

texts

######
eye 2

######
favorite 0

######
comment 0

We consider the following two deterministic inventory optimization problems over a finite planning horizon $T$ with non-stationary demands. (a) Submodular Joint Replenishment Problem: This involves multiple item types and a single retailer who faces demands. In each time step, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is find a sequence of orders that...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 27, 2018
06/18

by
Marc Tedder

texts

######
eye 3

######
favorite 0

######
comment 0

Comparability graphs are the undirected graphs whose edges can be directed so that the resulting directed graph is transitive. They are related to posets and have applications in scheduling theory. This paper considers the problem of finding a transitive orientation of a comparability graph, a requirement for many of its applications. A linear-time algorithm is presented based on an elegant partition refinement scheme developed elsewhere for the problem. The algorithm is intended as a simpler...

Topics: Data Structures and Algorithms, Computing Research Repository

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

3
3.0

Jun 27, 2018
06/18

by
Mikkel Thorup

texts

######
eye 3

######
favorite 0

######
comment 0

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees. Simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of $c$ characters and we have precomputed character tables $h_1,...,h_c$ mapping characters to random hash...

Topics: Computing Research Repository, Data Structures and Algorithms

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

3
3.0

Jun 28, 2018
06/18

by
Guido Hartmann

texts

######
eye 3

######
favorite 0

######
comment 0

We present numerical results for the probability of bad cases for Quicksort, i.e. cases of input data for which the sorting cost considerably exceeds that of the average. Dynamic programming was used to compute solutions of the recurrence for the frequency distributions of comparisons. From these solutions, probabilities of numbers of comparisons above certain thresholds relative to the average were extracted. Computations were done for array sizes up to n = 500 elements and for several methods...

Topics: Computing Research Repository, Data Structures and Algorithms

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

3
3.0

Jun 27, 2018
06/18

by
Sebastian Maneth; Fabian Peternek

texts

######
eye 3

######
favorite 0

######
comment 0

We present an informal survey (meant to accompany another paper) on graph compression methods. We focus on lossless methods, briefly list available pproaches, and compare them where possible or give some indicators on their compression ratios. We also mention some relevant results from the field of lossy compression and algorithms specialized for the use on large graphs. --- Note: The comparison is by no means complete. This document is a first draft and will be updated and extended.

Topics: Data Structures and Algorithms, Computing Research Repository

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