9 citations · 21 across the 10 of their papers we have counts for
11 papers
Distributed Selection in Time with Messages
Piotr Berman, Junichiro Fukuyama
We consider the selection problem on a completely connected network of processors with no shared memory. Each processor initially holds a given numeric item of bits allowed…
Tolerant Testers of Image Properties
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova
We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property (that i…
On the Computational Complexity of Measuring Global Stability of Banking Networks
Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder +1
Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable emphasis is placed on the analyzing the cause and ef…
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…
On Approximating Four Covering and Packing Problems
Mary Ashley, Tanya Berger-Wolf, Piotr Berman +3
In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them…
Steiner Transitive-Closure Spanners of d-Dimensional Posets
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu +3
Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diamet…