Hasil untuk "cs.DS"

Julio Candanedo

Matrices and more generally multidimensional arrays, form the backbone of computational studies. In this paper we demonstrate increases in computational efficiency by performing partial-tracing/tensor-contractions on sparse-arrays. It was shown that sparse-arrays are really 3 dense-arrays (dense-shape, index-array, and data-array). Dense-array manipulations of these constituent arrays are used to determine the resulting partial-trace. Because computational arrays are used in a verity of different studies, these methods are broadly applicable.

Daniel Ting

Consider the fundamental problem of drawing a simple random sample of size k without replacement from [n] := {1, . . . , n}. Although a number of classical algorithms exist for this problem, we construct algorithms that are even simpler, easier to implement, and have optimal space and time complexity.

Vera Traub, Rico Zenklusen

We present an approximation algorithm for Weighted Tree Augmentation with approximation factor $1+\ln 2 + \varepsilon < 1.7$. This is the first algorithm beating the longstanding factor of $2$, which can be achieved through many standard techniques.

Václav Rozhoň

We present a simple analysis of k-means|| (Bahmani et al., PVLDB 2012) -- a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007). Moreover, the bound on the number of rounds is improved from $O(\log n)$ to $O(\log n / \log\log n)$, which we show to be tight.

Dekel Tsur

We study the puzzle game Buttons and Scissors in which the goal is to remove all buttons from an $n\times m$ grid by a series of horizontal and vertical cuts. We show that the corresponding parameterized problem has an algorithm with time complexity $2^{O(k^2 \log k)} (n+m)^{O(1)}$, where $k$ is an upper bound on the number of cuts.

Khaled Elbassioni

We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. We show how an integrality gap verifier for the linear programming relaxation of the non-robust version of the problem can be used to derive approximation algorithms for the robust version.

Shoupu Wan

Quicksort algorithm with Hoare's partition scheme is traditionally implemented with nested loops. In this article, we present loop programming and refactoring techniques that lead to simplified implementation for Hoare's quicksort algorithm consisting of a single loop. We believe that the techniques are beneficial for general programming and may be used for the discovery of more novel algorithms.

Gaurav Menghani, Dhruv Matani

A Level Ancestory query LA($u$, $d$) asks for the the ancestor of the node $u$ at a depth $d$. We present a simple solution, which pre-processes the tree in $O(n)$ time with $O(n)$ extra space, and answers the queries in $O(\log\ {n})$ time. Though other optimal algorithms exist, this is a simple enough solution that could be taught and implemented easily.

Xi Chen, Erik Waingarten

We present an $\tilde{O}(n^{2/3}/ε^2)$-query algorithm that tests whether an unknown Boolean function $f\colon\{0,1\}^n\rightarrow \{0,1\}$ is unate (i.e., every variable is either non-decreasing or non-increasing) or $ε$-far from unate. The upper bound is nearly optimal given the $\tildeΩ(n^{2/3})$ lower~bound of [CWX17a]. The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.

Bruno Grenet, Ilya Volkovich

We give a new simple and short ("one-line") analysis for the runtime of the well-known Euclidean Algorithm. While very short simple, the obtained upper bound in near-optimal.

Petros Drineas, Michael W. Mahoney

This chapter is based on lectures on Randomized Numerical Linear Algebra from the 2016 Park City Mathematics Institute summer school on The Mathematics of Data.

François Serre, Markus Püschel

We propose a way of characterizing the algorithms computing a Walsh-Hadamard transform that consist of a sequence of arrays of butterflies ($I_{2^{n-1}}\otimes \text{DFT}_2$) interleaved by linear permutations. Linear permutations are those that map linearly the binary representation of its element indices. We also propose a method to enumerate these algorithms.

Wouter Kuijper, Victor Ermolaev, Olivier Devillers

We present a new oblivious walking strategy for convex subdivisions. Our walk is faster than the straight walk and more generally applicable than the visibility walk. To prove termination of our walk we use a novel monotonically decreasing distance measure.

R. Krithika, N. S. Narayanaswamy

We describe an elegant O*(2^k) algorithm for the disjoint compression problem for Odd Cycle Transversal based on a reduction to Above Guarantee Vertex Cover. We believe that this algorithm refines the understanding of the Odd Cycle Transversal algorithm by Reed, Smith and Vetta.

Julian Arz, Johannes Fischer

We show how to compress string dictionaries using the Lempel-Ziv (LZ78) data compression algorithm. Our approach is validated experimentally on dictionaries of up to 1.5 GB of uncompressed text. We achieve compression ratios often outperforming the existing alternatives, especially on dictionaries containing many repeated substrings. Our query times remain competitive.

Ton Kloks, Sheung-Hung Poon, Chin-Ting Ung et al.

We show that there exist linear-time algorithms that compute the strong chromatic index of Halin graphs, of maximal outerplanar graphs and of distance-hereditary graphs.

Paul Bonsma, Daniel Lokshtanov

A mixed graph is a graph with both directed and undirected edges. We present an algorithm for deciding whether a given mixed graph on $n$ vertices contains a feedback vertex set (FVS) of size at most $k$, in time $2^{O(k)}k! O(n^4)$. This is the first fixed parameter tractable algorithm for FVS that applies to both directed and undirected graphs.

Catherine Doss, Michèle Thieullen

We consider a stochastic perturbation of a FitzHugh-Nagumo system. We show that it is possible to generate oscillations for values of parameters which do not allow oscillations for the deterministic system. We also study the appearance of a new equilibrium point and new bifurcation parameters due to the noisy component.

Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

We study the weighted generalization of the edge coloring problem where the weight of each color class (matching) equals to the weight of its heaviest edge and the goal is to minimize the sum of the colors' weights. We present a 3/2-approximation algorithm for trees.

Fedor V. Fomin, Serge Gaspers, Saket Saurabh et al.

This paper has been withdrawn by the author.