Arrow Research search

Author name cluster

Piotr Berman

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.

23 papers
2 author rows

Possible papers

23

I&C Journal 2013 Journal Article

Approximation algorithms for spanner problems and Directed Steiner Forest

  • Piotr Berman
  • Arnab Bhattacharyya
  • Konstantin Makarychev
  • Sofya Raskhodnikova
  • Grigory Yaroslavtsev

We present an O ( n log n ) -approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G = ( V, E ) with nonnegative edge lengths d: E → R ⩾ 0 and a stretch k ⩾ 1, a subgraph H = ( V, E H ) is a k-spanner of G if for every edge ( s, t ) ∈ E, the graph H contains a path from s to t of length at most k ⋅ d ( s, t ). The previous best approximation ratio was O ˜ ( n 2 / 3 ), due to Dinitz and Krauthgamer (STOC ʼ11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from O ˜ ( n ) to O ( n 1 / 3 log n ). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS ʼ10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and Krauthgamerʼs lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O ( n 1 / 3 log n ) -approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O ( n ) -approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O ( n 2 / 3 + ϵ ) for any constant ϵ > 0, which improves the O ( n ϵ ⋅ min ( n 4 / 5, m 2 / 3 ) ) ratio due to Feldman, Kortsarz and Nutov (JCSSʼ12).

Details DOI

TCS Journal 2008 Journal Article

Approximating the online set multicover problems via randomized winnowing

  • Piotr Berman
  • Bhaskar DasGupta

In this paper, we consider the weighted online set k -multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every S ∈ S, and a “coverage factor” (positive integer) k. A subset { i 0, i 1, … } ⊆ V of elements are presented online in an arbitrary order. When each element i p is presented, we are also told the collection of all (at least k ) sets S i p ⊆ S and their costs to which i p belongs and we need to select additional sets from S i p if necessary such that our collection of selected sets contains at least k sets that contain the element i p. The goal is to minimize the total cost of the selected sets. 1 1 Our algorithm and competitive ratio bounds can be extended to the case when a set can be selected at most a prespecified number of times instead of just once; we do not report these extensions for simplicity and also because they have no relevance to the biological applications that motivated our work. In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of [N. Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (1988) 285–318]. This algorithm generalizes and improves some earlier results in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, A general approach to online network optimization problems, in: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 570–579; N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100–105]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100–105].

Details DOI

TCS Journal 2007 Journal Article

Optimal trade-off for Merkle tree traversal

  • Piotr Berman
  • Marek Karpinski
  • Yakov Nekrich

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo [Fractal Merkle tree representation and traversal, in: RSA Cryptographers Track, RSA Security Conference, 2003] and M. Szydlo [Merkle tree traversal in log space and time, in: Proc. Eurocrypt, in: LNCS, vol. 3027, 2004, pp. 541–554; Merkle tree traversal in log space and time, Preprint version 2003, available at http: //www. szydlo. com]. In particular, we show that our algorithm requires 2 log n / log ( 3 ) n hash function computations and storage for less than ( log n / log ( 3 ) n + 1 ) log log n + 2 log n hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i. e. there is no algorithm that requires less than O ( log n / log t ) time and less than O ( t log n / log t ) space for any choice of parameter t ≥ 2. Our algorithm could be of special interest in the case when both time and space are limited.

Details DOI

TCS Journal 1997 Journal Article

A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon

  • Piotr Berman
  • Andrzej Lingas

We present a parallel algorithm for the Voronoi diagram of the set of vertices of a convex polygon. The algorithm runs in time O(log n) and uses O( n log log n log n ) processors in the CRCW PRAM model. The concurrent write is used only by an integer sorting subroutine. We also obtain an O(log n)-time and O( n log log n log n )-processor CRCW PRAM algorithm for the construction of the medial axis of a convex polygon. Our algorithms use the solution to the duration-unknown task scheduling problem due to Cole and Vishkin and the optimal parallel algorithm for the convex hull of a polygon due to Wagener. They are randomized in the sense that for any given l > 0 they terminate in time O(log n) with probability greater than 1 − n −1.

Details DOI

I&C Journal 1992 Journal Article

On the complexity of approximating the independent set problem

  • Piotr Berman
  • Georg Schnitger

We show that for some positive constant c it is not feasible to approximate Independent Set (for graphs of n vertices) within a factor of n c, provided Maximum 2-Satisfiability does not have a randomized polynomial time approximation scheme. We also study reductions preserving the quality of approximations and exhibit complete problems.

Details DOI

FOCS Conference 1989 Conference Paper

Towards Optimal Distributed Consensus (Extended Abstract)

  • Piotr Berman
  • Juan A. Garay 0001
  • Kenneth J. Perry

In a distributed consensus protocol all processors (of which t may be faulty) are given (binary) initial values; after exchanging messages all correct processors must agree on one of them. The quality of a protocol is measured here using as parameters the total number of processors n, number of rounds of message exchange r, and maximal message length m, with optima, respectively, of 3t+1, t+1, and 1. Although no known protocol is optimal in all these three aspects simultaneously, the protocols that take further steps in this direction are presented. The first protocol has n>4t, r=t+1, and polynomial message size. The second protocol has n>3t, r=3t+3, and m=2, and it is asymptotically optimal in all three quality parameters while using the optimal number of processors. Using these protocols as building blocks, families of protocols with intermediate quality parameters, offering better tradeoffs than previous results, are obtained. All the protocols work in polynomial time and have succinct descriptions. >

Details

FOCS Conference 1987 Conference Paper

Learning One-Counter Languages in Polynomial Time (Extended Abstract)

  • Piotr Berman
  • Robert Roos

We demonstrate that the class of languages accepted by deterministic one-counter machines, or DOCAs (a natural subset of the context-free languages), is learnable in polynomial time. Our learning protocol is based upon Angluin's concept of a "minimally adequate teacher" who can answer membership queries about a concept and provide counterexamples to incorrect hypothesized concepts. We also demonstrate that the problem of testing DOCAs for equivalence may be solved in polynomial time, answering a question posed by Valiant and Paterson.

Details

FOCS Conference 1983 Conference Paper

Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version)

  • Piotr Berman
  • Janos Simon

It is likely that reliable and fast space-bounded probabilistic acceptors are less powerful than nondeterministic ones. We consider a restricted model of space-bounded probabilistic computation, the random analog of a model studied in [CR]. We show that maze traversal (a complete problem for nondeterministic space log n) requires space Ω(log2n/loglogn) by random machines, even if 'fast' is relaxed to mean only 'subexponential'. In particular, the lower bound on space holds for the time complexity of Savitch's algorithm (which can be simulated in the model).

Details
v2026.09.13