Arrow Research search

Author name cluster

Guy Even

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers
2 author rows

Possible papers

15

STOC Conference 2022 Conference Paper

An extendable data structure for incremental stable perfect hashing

  • Ioana Oriana Bercea
  • Guy Even

We consider the problem of dynamically assigning n elements unique indices, known as hashcodes , in the range [(1+ o (1)) n ]. This problem is known as perfect hashing and is considered a fundamental building block in the design of more involved data structures. The challenge we address is that of designing a data structure that meets several, seemingly opposing, requirements: (1) the range and the space of the data structure must be, at all times, proportional to the current cardinality n t of the input set, and (2) the hashcodes it assigns must be stable in that the hashcode of an element must not change while the element is continuously in the set. A simple argument shows that these two desiderata are impossible to achieve when arbitrary deletions and insertions are allowed. In this paper, we show that one can achieve them when only insertions occur and, more generally, when the hashcode range and the space are allowed to grow as a function of the maximum cardinality N t of the set until time t . The data structure executes all operations in worst case constant time with high probability and requires space that is within a constant factor of the lower bound. In particular, this leads to a hash table design that does not need to move elements as its size grows. More generally, we present, as an application, a cyclic sequence of reductions between data structures that lead to the following bootstrapping result. Let B ( u , n ) denote the lower bound on the space of a dictionary for n elements over a universe [ u ]. Given a compact dynamic dictionary (i.e., space O ( B ( u , n ))), we can use it to build a dynamic dictionary with space B ( u , n )+ O ( n loglog n ). This reduction increases the time per operation by an additive constant and applies both to the extendable and non-extendable settings (failure probability is 1/ poly ( n ) per insertion).

Details

TCS Journal 2021 Journal Article

Upper tail analysis of bucket sort and random tries

  • Ioana O. Bercea
  • Guy Even

Bucket Sort is known to run in expected linear time when the input keys are distributed independently and uniformly at random in the interval [ 0, 1 ). The analysis holds even when a quadratic time algorithm is used to sort the keys in each bucket. We show how to obtain linear time guarantees on the running time of Bucket Sort that hold with very high probability. Specifically, we investigate the asymptotic behavior of the exponent in the upper tail probability of the running time of Bucket Sort. We consider large additive deviations from the expectation, of the form cn for large enough (constant) c, where n is the number of keys that are sorted. Our analysis shows a profound difference between variants of Bucket Sort that use a quadratic time algorithm within each bucket and variants that use a Θ ( b log ⁡ b ) time algorithm for sorting b keys in a bucket. When a quadratic time algorithm is used to sort the keys in a bucket, the probability that Bucket Sort takes cn more time than expected is exponential in Θ ( n log ⁡ n ). When a Θ ( b log ⁡ b ) algorithm is used to sort the keys in a bucket, the exponent becomes Θ ( n ). We prove this latter theorem by showing an upper bound on the tail of a random variable defined on tries, a result which we believe is of independent interest. This result also enables us to analyze the upper tail probability of a well-studied trie parameter, the external path length, and show that the probability that it deviates from its expected value by an additive factor of cn is exponentially small in Θ ( n ).

Details DOI

TCS Journal 2013 Journal Article

Competitive and deterministic embeddings of virtual networks

  • Guy Even
  • Moti Medina
  • Gregor Schaffrath
  • Stefan Schmid

Network virtualization is an important concept to overcome the ossification of today’s Internet as it facilitates innovation also in the network core and as it promises a more efficient use of the given resources and infrastructure. Virtual networks (VNets) provide an abstraction of the physical network: multiple VNets may cohabit the same physical network, but can be based on completely different protocol stacks (also beyond IP). One of the main challenges in network virtualization is the efficient admission control and embedding of VNets. The demand for virtual networks (e. g. , for a video conference) can be hard to predict, and once the request is accepted, the specification/QoS guarantees must be ensured throughout the VNet’s lifetime. This requires an admission control algorithm which only selects high-benefit VNets in times of scarce resources, and an embedding algorithm which realizes the VNet in such a way that the likelihood that future requests can be embedded as well is maximized. This article describes a generic algorithm for the online VNet embedding problem which does not rely on any knowledge of the future VNet requests but whose performance is competitive to an optimal offline algorithm that has complete knowledge of the request sequence in advance: the so-called competitive ratio is, loosely speaking, logarithmic in the sum of the resources. Our algorithm is generic in the sense that it supports multiple traffic models, multiple routing models, and even allows for nonuniform benefits and durations of VNet requests.

Details DOI

TCS Journal 2012 Journal Article

Revisiting randomized parallel load balancing algorithms

  • Guy Even
  • Moti Medina

We deal with the well studied allocation problem of assigning n balls to n bins so that the maximum number of balls assigned to the same bin is minimized. We focus on randomized, constant-round, distributed, asynchronous algorithms for this problem. Adler et al. (1998) [1] presented lower bounds and upper bounds for this problem. A similar lower bound appears in Berenbrink et al. (1999) [2]. The general lower bound is based on a topological assumption. Our first contribution is the observation that the topological assumption does not hold for two algorithms presented by Adler etal. (1998) [1]. We amend this situation by presenting proofs of the lower bound for these two specific algorithms. We present an algorithm in which a ball that was not allocated in the first round retries with a new choice in the second round. We present tight bounds on the maximum load obtained by our algorithm. The analysis is based on analyzing the expectation and transforming it to a bound with high probability using martingale tail inequalities. Finally, we present a 3-round heuristic with a single synchronization point. We conducted experiments that demonstrate its advantage over parallel algorithms for 1 0 6 ≤ n ≤ 8 ⋅ 1 0 6 balls and bins. In fact, the obtained maximum load meets the best experimental results for sequential algorithms.

Details DOI

TCS Journal 2011 Journal Article

Parallel randomized load balancing: A lower bound for a more general model

  • Guy Even
  • Moti Medina

We extend the lower bound of Adler et al. (1998) [1] and Berenbrink et al. (1999) [2] for parallel randomized load balancing algorithms. The setting in these asynchronous and distributed algorithms is of n balls and n bins. The algorithms begin by each ball choosing d bins independently and uniformly at random. The balls and bins communicate to determine the assignment of each ball to a bin. The goal is to minimize the maximum load, i. e. , the number of balls that are assigned to the same bin. In Adler et al. (1998) [1] and Berenbrink et al. (1999) [2], a lower bound of Ω ( log n / log log n r ) is proved if the communication is limited to r rounds. Three assumptions appear in the proofs in Adler et al. (1998) [1] and Berenbrink et al. (1999) [2]: the topological assumption, random choices of confused balls, and symmetry. The topological assumption states that each ball’s decision is based only on collisions between choices of balls. The confused ball assumption states that if a ball obtains the same topological information from all its chosen bins, then the ball commits to one of the chosen bins by flipping a fair coin. The symmetry assumption states that all the balls run identical algorithms, the same assumption holds for the bins. We extend the proof of the lower bound so that it holds without these three assumptions. This lower bound applies to every parallel randomized load balancing algorithm we are aware of (Adler et al. , 1998 [1]; Berenbrink et al. , 1999 [2]; Stemann, 1996 [3]; Even and Medina, 2009 [4]).

Details DOI

TCS Journal 2009 Journal Article

Optimal conclusive sets for comparator networks

  • Guy Even
  • Tamir Levi
  • Ami Litman

A set of input vectors S is conclusive for a certain functionality if, for every comparator network, correct functionality for all input vectors is implied by correct functionality for all vectors in S. We consider four functionalities of comparator networks: sorting, merging, sorting of bitonic vectors, and halving. For each of these functionalities, we present two conclusive sets of minimal cardinality. The members of the first set are restricted to be binary, while the members of the second set are unrestricted. For all the above functionalities, except halving, the unrestricted conclusive set is much smaller than the binary one.

Details DOI

FOCS Conference 2002 Conference Paper

Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks

  • Guy Even
  • Zvi Lotker
  • Dana Ron
  • Shakhar Smorodinsky

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem called minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system (X, S), where each S /spl isin/ S is a subset of X. The output is a coloring X of the sets in S that satisfies the following constraint: for every x /spl isin/ X there exists a color i and a unique set S /spl isin/ S, such that x /spl isin/ S and /spl chi/(S) = i. The goal is to minimize the number of colors used by the coloring X. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and non-congruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle) regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally-symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). For rectangles and hexagons we obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also show that, even in the case of unit disks, /spl Theta/(log n) colors may be necessary.

Details

FOCS Conference 1996 Conference Paper

An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem

  • Guy Even
  • Joseph Naor
  • Leonid Zosin

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set. The input in this problem consists of an undirected graph G=(V, E) with vertex weights w(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset feedback vertex set with respect to S if it intersects every interesting cycle The goal is to find a minimum weight subset feedback vertex set. The best pervious algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset feedback vertex set problem generalizes two NP-Complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multi-commodity flow which we call relaxed multi-commodity flow. Relaxed multi-commodity flow is a hybrid of multi-commodity flow and multi-terminal flow.

Details

FOCS Conference 1995 Conference Paper

Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract)

  • Guy Even
  • Joseph Naor
  • Satish Rao
  • Baruch Schieber

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimisation problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound, /spl tau/, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modelled by our paradigm whose approximation factor is O (mi.

Details