Arrow Research search

Author name cluster

Baruch Schieber

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.

38 papers
2 author rows

Possible papers

38

SODA Conference 2019 Conference Paper

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

  • Sepehr Assadi
  • Krzysztof Onak
  • Baruch Schieber
  • Shay Solomon

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et al. , STOC’18]. The algorithm is deterministic and its update time is O ( m 3/4 ), where m is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of O ( m 2/3 ) and O ( m 2/3 ), respectively. Du and Zhang also gave a randomized algorithm with update time. Moreover, they provided some partial (conditional) hardness results hinting that the update time of m 1/2– ε, and in particular n 1– ε for n -vertex dense graphs, is a natural barrier for this problem for any constant ε > 0, for deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an expected amortized update. We also show that a simpler variant of our algorithm can already achieve an Õ ( m 1/3 ) expected amortized update time, which results in an improved performance over our update time algorithm for sufficiently sparse graphs, and breaks the m 1/2 barrier of Du and Zhang for all values of m.

Details

ICML Conference 2019 Conference Paper

Scalable Fair Clustering

  • Arturs Backurs
  • Piotr Indyk
  • Krzysztof Onak
  • Baruch Schieber
  • Ali Vakilian
  • Tal Wagner

We study the fair variant of the classic k-median problem introduced by (Chierichetti et al. , NeurIPS 2017) in which the points are colored, and the goal is to minimize the same average distance objective as in the standard $k$-median problem while ensuring that all clusters have an “approximately equal” number of points of each color. (Chierichetti et al. , NeurIPS 2017) proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.

Details

STOC Conference 2018 Conference Paper

Fully dynamic maximal independent set with sublinear update time

  • Sepehr Assadi
  • Krzysztof Onak
  • Baruch Schieber
  • Shay Solomon

A maximal independent set (MIS) can be maintained in an evolving m -edge graph by simply recomputing it from scratch in O ( m ) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O (min{Δ, m 3/4 }), where Δ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O (min{Δ, m 3/4 }) amortized message complexity, and O (1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC’16) that required an assumption of a non-adaptive oblivious adversary.

Details

FOCS Conference 2007 Conference Paper

Non-Preemptive Min-Sum Scheduling with Resource Augmentation

  • Nikhil Bansal 0001
  • Ho-Leung Chan
  • Rohit Khandekar
  • Kirk Pruhs
  • Cliff Stein 0001
  • Baruch Schieber

We give the first O(l)-speed O(l) approximation polynomial-time algorithms for several nonpreemptive min-sum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(l)-speed O(l)-approximations for the non-preemptive scheduling problems; l|r j | Sigmaw j F j (weighted flow time), l |r j | SigmaT j (total tardiness), the broadcast version of 1 |r j | Sigmaw j F j, an O(I)-speed, 1-approximation for l |r j | Sigma U macr j (throughput maximization), and an O(l)-machine, O(l)-speed O(1)-approximation for l |r j | Sigmaw j T j (weighted tardiness). Our main contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine.

Details

STOC Conference 2006 Conference Paper

A quasi-PTAS for unsplittable flow on line graphs

  • Nikhil Bansal 0001
  • Amit Chakrabarti
  • Amir Epstein
  • Baruch Schieber

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2 polylog(n) ). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs.Earlier results on this problem included a polynomial time (2+ε)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

Details

STOC Conference 2001 Conference Paper

Buffer overflow management in QoS switches

  • Alexander Kesselman
  • Zvi Lotker
  • Yishay Mansour
  • Boaz Patt-Shamir
  • Baruch Schieber
  • Maxim Sviridenko

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difficulty in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be released, or otherwise it is lost. We study the cases where the incoming streams overload the buffers, resulting in packet loss. In our model, each packet has an intrinsic value; the goal is to maximize the total value of packets transmitted

Details

STOC Conference 2001 Conference Paper

Online server allocation in a server farm via benefit task systems

  • T. S. Jayram
  • Tracy Kimbrel
  • Robert Krauthgamer
  • Baruch Schieber
  • Maxim Sviridenko

A web content hosting service provider needs to dynamically allocate servers in a server farm to its customers' web sites. Ideally, the allocation to a site should always suffice to handle its load. However, due to a limited number of servers and the overhead incurred in changing the allocation of a server from one site to another, the system may become overloaded. The problem faced by the web hosting service provider is how to allocate the available servers in the most profitable way. Adding to the complexity of this problem is the fact that future loads of the sites are either unknown or known only for the very near future. In this paper we model this server allocation problem , and consider both its offline and online versions. We give a polynomial time algorithm for computing the optimal offline allocation. In the online setting, we show almost optimal algorithms (both deterministic and randomized) for any positive lookahead. The quality of the solution improves as the lookahead increases. We also consider several special cases of practical interest. Finally, we present some experimental results using actual trace data that show that one of our online algorithm performs very close to optimal. Interestingly, the online server allocation problem can be cast as a more general benefit task system that we define. Our results extend to this task system, which captures also the benefit maximization variants of the k -server problem and the metrical task system problem. It follows that the benefit maximization variants of these problems are more tractable than their cost minimization variants.

Details

FOCS Conference 1997 Conference Paper

Improved Approximations for Shallow-Light Spanning Trees

  • Joseph Naor
  • Baruch Schieber

We consider the bicriteria optimization problem of computing a shallow-light tree. Given a directed graph with two unrelated cost functions defined on its edges: weight and length, and a designated root vertex, the goal is to find a minimum weight spanning tree such that the path lengths from its root to the rest of the vertices are bounded. This problem has several applications in network and VLSI design, and information retrieval. We give a polynomial time algorithm for finding a spanning tree whose weight is O(log |V|) times the weight of an optimal shallow-light tree, where the path lengths from the root to the rest of the vertices are at most twice the given bounds. We extend our technique to handle two variants of the problem: one in which the length bound is given on the average length of a path from the root to a vertex, and another tricriteria budgeted version. Our paper provides the first non-trivial approximation factors for directed graphs, and improves on previous results for undirected graphs.

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

FOCS Conference 1992 Conference Paper

Efficient Minimum Cost Matching Using Quadrangle Inequality

  • Alok Aggarwal
  • Amotz Bar-Noy
  • Samir Khuller
  • Dina Kravets
  • Baruch Schieber

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red * Blue), where mod Red mod = n, mod Blue mod = m, n >

Details

TCS Journal 1992 Journal Article

Fast geometric approximation techniques and geometric embedding problems

  • Marshall W. Bern
  • Howard J. Karloff
  • Prabhakar Raghavan
  • Baruch Schieber

Given an undirected n-vertex graph G and a set of n points in R d, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem as those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

Details DOI

FOCS Conference 1992 Conference Paper

Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary)

  • Don Coppersmith
  • Baruch Schieber

Consider an arithmetic expression of length n involving only the operations (+, *) and non-negative constants. The authors prove lower bounds on the depth of any binary computation tree over the same set of operations and constants that computes such an expression. In their main result they exhibit a family of arithmetic expressions that requires computation trees of depth at least 1. 5 log/sub 2/n-O(1). The authors also consider the family of arithmetic expressions defined by alternating 5-3 trees. For this family they show a tight bound of 5/(log/sub 2/15)log/sub 2/n+O(1) on the depth of any computation tree. This is the best known tight bound for any family of arithmetic expressions. >

Details

I&C Journal 1990 Journal Article

The power of multimedia: Combining point-to-point and multiaccess networks

  • Yehuda Afek
  • Gad M. Landau
  • Baruch Schieber
  • Moti Yung

This paper introduces a new network model called a multimedia network. It combines the point-to-point message passing network and the multiaccess channel. To benefit from the combination, the designed algorithms consist of two stages: a local stage which utilizes the parallelism of the point-to-point network and a global stage which utilizes the broadcast capability of the multiaccess channel. To balance the complexities of the two stages a partition of the network into O( n ) connected components each of radius O( n ) is required. We present efficient deterministic and randomized partitioning algorithms that run in ( n log∗ n ) time. The deterministic algorithm sends O(m + n log n log ∗ n) messages, while the randomized algorithm sends only O(m + n log ∗ n) messages. (n and m are the number of nodes and point-to-point links in the network.) The partitioning algorithms are then used to obtain: (1) O( n log n log ∗ n ) time deterministic and O( n log ∗ n ) time randomized algorithms for computing global sensitive functions, and (2) An O( n log n ) time deterministic algorithm for computing a minimum spanning tree. We give Ω(n) time lower bounds for computing global sensitive functions in both point-to-point and multiaccess networks, thus showing that the multimedia network is more powerful than both its separate components. Furthermore, we prove and Ω( n ) time lower bound for computing global sensitive functions in multimedia networks, thus leaving a small gap between our upper and lower bounds.

Details DOI

FOCS Conference 1989 Conference Paper

Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary)

  • Samir Khuller
  • Baruch Schieber

An efficient parallel algorithm for testing whether a graph G is K-vertex connected, for any fixed k, is presented. The algorithm runs in O(log n) time and uses nC(n, m) processors on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM), where n and m are the number of vertices and edges of G and C(n, m) is the number of processors required to compute the connected components of G in logarithmic time. An optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing k-vertex connectivity, for any k>4. To develop the algorithm, an efficient parallel algorithm is designed for the following disjoint s-t paths problem: Given a graph G and two specified vertices s and t, find k-vertex disjoint paths between s and t, if they exist. If no such paths exist, find a set of at most k-1 vertices whose removal disconnects s and t. The parallel algorithm for this problem runs in O(log n) time using C(n, m) processors. It is shown how to modify the algorithm to find k-edge disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph G is k-edge connected, for any fixed k. The algorithm runs in O(log n) time and uses nC (n, n) processors on a CRCW PRAM. Again, an optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing k-edge connectivity. >

Details

FOCS Conference 1989 Conference Paper

The Complexity of Approximating the Square Root (Extended Summary)

  • Yishay Mansour
  • Baruch Schieber
  • Prasoon Tiwari

The authors prove upper and lower bounds for approximately computing the square root using a given set of operations. The bounds are extended to hold for approximating the kth root, for any fixed k. Several tools from approximation theory are used to prove the lower bound. These include Markoff inequality, Chebyshev polynomials, and a theorem that relates the degree of a rational function to its deviation from the approximated function over a given interval. The lower bound can be generalized to other algebraic functions. The upper bound can be generalized to obtain an O(1)-step straight-line program for evaluating any rational function with integer coefficients at a given integer point. >

Details

TCS Journal 1986 Journal Article

Parallel ear decomposition search (EDS) and st-numbering in graphs

  • Yael Maon
  • Baruch Schieber
  • Uzi Vishkin

The linear time serial algorithm of Lempel et al. (1967) for testing planarity of graphs uses the linear time serial algorithm of Even and Tarjan (1976) for st-numbering. This st-numbering algorithm is based on depth-first search (DFS). A known conjecture states that DFS, which is a key technique in designing serial algorithms, is not amenable to poly-log time parallelism using ‘around linearly’ (or even polynomially) many processors. The first contribution of this paper is a general method for searching efficiently in parallel undirected graphs, called ear decomposition search (EDS). The second contribution demonstrates the applicability of this search method. We present an efficient parallel algorithm for st-numbering in a biconnected graph. The algorithm runs in logarithmic time using a linear number of processors on a concurrent-read concurrent-write (CRCW) PRAM. An efficient parallel algorithm for the problem did not exist before. The problem was not even known to be in NC.

Details DOI
v2026.09.13