## SEARCH

#### Institution

##### ( see all 3214)

- University of California 79 (%)
- Tel Aviv University 58 (%)
- University of Waterloo 56 (%)
- Princeton University 53 (%)
- Max-Planck-Institut für Informatik 43 (%)

#### Author

##### ( see all 6163)

- Fomin, Fedor V. 20 (%)
- Saurabh, Saket 18 (%)
- Epstein, Leah 17 (%)
- Demaine, Erik D. 14 (%)
- Lee, D. T. 14 (%)

#### Subject

##### ( see all 10)

- Computer Science 2364 (%)
- Computer Systems Organization and Communication Networks 2364 (%)
- Data Structures, Cryptology and Information Theory 2364 (%)
- Theory of Computation 2364 (%)
- Algorithm Analysis and Problem Complexity 2238 (%)

## CURRENTLY DISPLAYING:

Most articles

Fewest articles

Showing 1 to 10 of 2637 matching Articles
Results per page:

## An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion

### Algorithmica (2012-09-01) 64: 170-188 , September 01, 2012

The *Pathwidth One Vertex Deletion* (POVD) problem asks whether, given an undirected graph *G* and an integer *k*, one can delete at most *k* vertices from *G* so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied *Feedback Vertex Set* (FVS) problem, where the deletion of at most *k* vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196–207, 2010) initiated the study of the parameterized complexity of *POVD*, showing a quartic kernel and an algorithm which runs in time 7^{k}*n*^{O(1)}. In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65^{k}*n*^{O(1)}, thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251–260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for *FVS*, due to Thomassé (ACM Trans. Algorithms 6(2), 2010).

## A minimum-area circuit forl-selection

### Algorithmica (1987-11-01) 2: 251-265 , November 01, 1987

We prove tight upper and lower bounds on the area of semelective, when-oblivious VLSI circuits for the problem of*l*-selection. The area required to select the*l*th smallest of*n**k*-bit integers is found to be heavily dependent on the relative sizes of*l*,*k*, and*n*. When*l*<2^{k}, the minimal area is*A* = Θ(min*n*,*l*(*k*-log*l*)). When*l*≥2^{k},*A* = Θ(2^{k}(log*l*-*k* + 1)).

## Motion Planning via Manifold Samples

### Algorithmica (2013-12-01) 67: 547-565 , December 01, 2013

We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with practical, considerably simpler sampling-based approaches that are appropriate for higher dimensions. In order to facilitate the transfer of advanced geometric algorithms into practical use, we suggest taking samples that are *entire low-dimensional manifolds of the configuration space* that capture the connectivity of the configuration space much better than isolated point samples. Geometric algorithms for analysis of low-dimensional manifolds then provide powerful primitive operations. The modular design of the framework enables independent optimization of each modular component. Indeed, we have developed, implemented and optimized a primitive operation for complete and exact combinatorial analysis of a certain set of manifolds, using arrangements of curves of rational functions and concepts of generic programming. This in turn enabled us to implement our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles. We show that this instance of the framework is probabilistically complete. Moreover, we demonstrate that the integration of several carefully engineered components leads to significant speedup over the popular PRM sampling-based algorithm, which represents the more simplistic approach that is prevalent in practice.

## Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation

### Algorithmica (2016-11-15): 1-53 , November 15, 2016

In this work, we show how to use indistinguishability obfuscation to build multiparty key exchange, efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting properties that have not been achievable before:

Our multiparty non-interactive key exchange protocol does not require a trusted setup. Moreover, the size of the published value from each user is independent of the total number of users.

Our broadcast encryption schemes support *distributed* setup, where users choose their own secret keys rather than be given secret keys by a trusted entity. The broadcast ciphertext size is *independent* of the number of users.

Our traitor tracing system is fully collusion resistant with short ciphertexts, secret keys, and public key. Ciphertext size is logarithmic in the number of users and secret key size is independent of the number of users. Our public key size is polylogarithmic in the number of users. The recent functional encryption system of Garg, Gentry, Halevi, Raykova, Sahai, and Waters also leads to a traitor tracing scheme with similar ciphertext and secret key size, but the construction in this paper is simpler and more direct. These constructions resolve an open problem relating to differential privacy.

Generalizing our traitor tracing system gives a private broadcast encryption scheme (where broadcast ciphertexts reveal minimal information about the recipient set) with optimal size ciphertext.

Several of our proofs of security introduce new tools for proving security using indistinguishability obfuscation.## Labeling Points with Weights

### Algorithmica (2004-02-01) 38: 341-362 , February 01, 2004

Annotating maps, graphs, and diagrams with pieces of text is an
important step in information visualization that is usually referred
to as label placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given a weight for
each point. There are two groups: fixed-position models and slider
models. We aim to maximize the weight sum of those points that
receive a label.
We first compare our models by giving bounds for the ratios between
the weights of maximum-weight labelings in different models. Then
we present algorithms for labeling *n* points with unit-height
rectangles. We show how an *O*(*n*\log *n*)-time factor-2 approximation
algorithm and a PTAS for fixed-position models can be extended to
handle the weighted case. Our main contribution is the first
algorithm for weighted sliding labels. Its approximation factor is
(2+\varepsilon), it runs in *O*(*n*^{2}/\varepsilon) time and uses
*O*(*n*/\varepsilon) space.
We show that other than for fixed-position models even the
projection to one dimension remains NP-hard.
For slider models we also investigate some special cases, namely
(a) the number of different point weights is bounded, (b) all labels
are unit squares, and (c) the ratio between maximum and minimum
label height is bounded.

## Sampling in Space Restricted Settings

### Algorithmica (2017-06-14): 1-20 , June 14, 2017

Space efficient algorithms play an important role in dealing with large amount of data. In such settings, one would like to analyze the large data using small amount of “working space”. One of the key steps in many algorithms for analyzing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings—(i) the streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) the query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in the above two settings:

In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using
$$O(\log n)$$
random bits and
$$O(\log n)$$
bits of space, where *n* is the number of elements seen so far. We can extend this to the case when elements have weights as well.

In the query model, there are *n* elements with weights
$$w_1, \ldots , w_n$$
(which are *w*-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using
$$nw +1 $$
bits of space (whereas, the information theoretic lower bound is *nw*). We consider the approximate sampling problem, where we are given an error parameter
$$\varepsilon $$
, and the sampling probability of an element can be off by an
$$\varepsilon $$
factor. We give matching upper and lower bounds for this problem.

## An algorithm for the three-dimensional packing problem with asymptotic performance analysis

### Algorithmica (1997-05-01) 18: 122-144 , May 01, 1997

The three-dimensional packing problem can be stated as follows. Given a list of boxes, each with a given length, width, and height, the problem is to pack these boxes into a rectangular box of fixed-size bottom and unbounded height, so that the height of this packing is minimized. The boxes have to be packed orthogonally and oriented in all three dimensions. We present an approximation algorithm for this problem and show that its asymptotic performance bound is between 2.5 and 2.67. This result answers a question raised by Li and Cheng [5] about the existence of an algorithm for this problem with an asymptotic performance bound less than 2.89.

## Maximal selection in tandem networks with symmetric hearing range

### Algorithmica (1989-06-01) 4: 343-364 , June 01, 1989

We consider an infinite tandem network in which every node is capable of hearing its neighbors up to a given distance*n*. At any moment of time every node may contain in the top of its queue a message destined to one of its neighbors. This network can be used as a model for a microwave or optic link with many users. For small and large*n* we investigate the maximal selection of nodes in the network, for which their transmissions are collision-free. For a large hearing range we show that the upper bound on the maximal selection, which is found herein, is asymptotically achievable. For small hearing ranges we show that a greedy selection is better but not asymptotically optimal. We also specify a sequence of upper bounds which converge to the maximal throughput.

## Choosing a Random Peer in Chord

### Algorithmica (2007-10-01) 49: 147-169 , October 01, 2007

We present two new algorithms, *Arc Length* and *Peer Count*, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both algorithms have latency *O*(log *n*) and send *O*(log *n*) messages. Moreover, we show empirically that the average latency and message cost of *Arc Length* is 10.01log *n* and that the average latency and message cost of *Peer Count* is 20.02log *n*. To the best of our knowledge, these two algorithms are the first fully distributed algorithms for choosing a peer uniformly at random from the set of all peers in a Distributed Hash Table (DHT). Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance.

## Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

### Algorithmica (2014-02-01) 68: 337-357 , February 01, 2014

Given an *n*-node, undirected and 2-edge-connected graph *G*=(*V*,*E*) with positive real weights on its *m* edges, given a set of *k**source* nodes *S*⊆*V*, and given a spanning tree *T* of *G*, the *routing cost from**S* of *T* is the sum of the distances in *T* from every source *s*∈*S* to all the other nodes of *G*. If an edge *e* of *T* undergoes a *transient* failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replace *e* by means of a *swap edge*, i.e., an edge in *G* reconnecting the two subtrees of *T* induced by the removal of *e*. Then, a *best swap edge* for *e* is a swap edge which minimizes the routing cost from *S* of the tree obtained after the swapping. As a natural extension, the *all-best swap edges* problem is that of finding a best swap edge for *every* edge of *T*, and this has been recently solved in *O*(*mn*) time and linear space. In this paper, we focus our attention on the relevant cases in which *k*=*O*(1) and *k*=*n*, which model realistic communication paradigms. For these cases, we improve the above result by presenting an
$\widetilde{O}(m)$
time and linear space algorithm. Moreover, for the case *k*=*n*, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input tree *T* has a routing cost from *V* which is a constant-factor away from that of a *minimum routing-cost spanning tree* (whose computation is a problem known to be in *APX*), and if in addition nodes in *T* enjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost from *V* which is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.