Piotr Berman

On-line Load Balancing for Related Machines 1 (Revised Version) (2008)

Abstract. We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: • An upper bound of 3n − 1 in...

Piotr Berman, Moses Charikar, Marek Karpinskiy

We consider the problem of scheduling permanent jobs on related machinesin an on-line fashion. We design a new algorithm that achievesthe competitive ratio for the deterministic version,...

Packing to Angles and Sectors (2008)

Piotr Berman, Jieun Jeong, Shiva P. Kasiviswanathan, Bhuvan Urgaonkar

In our problem we are given a set of customers, their positions on the plane and their demands. Geometrically, a directional antenna with parameters #, #, R is a set of points with radial coordinates...

On cycles in the transcription network of Saccharomyces cerevisiae (2008)

Jeong, Jieun, Berman, Piotr

Abstract Background We investigate the cycles in the transcription network of Saccharomyces cerevisiae . Unlike a similar network of Escherichia coli , it contains many cycles. We characterize...

Simple Approximation Algorithm for Nonoverlapping Local Alignments (2008)

On Approximating Four Covering and Packing Problems (2008)

this paper will show how to implement this algorithm in O(N log N) time

Mary Ashley, Tanya Berger-wolf, Piotr Berman, Wanpracha Chaovalitwongse, Bhaskar Dasgupta, Ming-yang Kao

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 are generalized or...

On Approximating Four Covering and Packing Problems (2008)

Mary Ashley, Tanya Berger-wolf, Piotr Berman, Wanpracha Chaovalitwongse, Bhaskar Dasgupta, Ming-yang Kao

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 are generalized or...

On cycles in the transcription network of Saccharomyces cerevisiae (2008)

Jieun Jeong, Piotr Berman

which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Background: We investigate the cycles in the transcription network of...

On Approximation of the Power-p and Bottleneck Steiner Trees (2007)

Piotr Berman, Alexander Zelikovsky

Many VLSI routing applications, as well as the facility location problem involve computation of Steiner trees with non-linear cost measures. We consider two most frequent versions of this problem. In...

Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search (2007)

Piotr Berman, Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder

In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to find a set of tiles such that they...

Algorithmic issues in reverse engineering of protein and gene networks via the modular response analysis method, to appear in Annals of the New York Academy of Sciences (volume title: Reverse Engineering Biological Networks: Opportunities and Challenges i (2007)

On Constructing An Optimal Consensus Clustering from Multiple Clusterings (2007)

This paper studies a computational problem motivated by the modular response analysis method for reverse engineering of protein and gene networks. This set-cover problem is hard to solve exactly for...

Piotr Berman, Bhaskar Dasgupta, Ming-yang Kao, Jie Wang

Computing a suitable measure of consensus among several clusterings on the same data is an important problem that arises in several areas such as computational biology and data mining. In this paper,...

Abstract (2007)

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...

Abstract (2007)

HomologMiner: looking for homologous genomic groups in whole genomes (2007)

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family S of subsets of V with a positive real cost for every S ∈ S,...

Hou, Minmei, Berman, Piotr, Hsu, Chih-Hao, Harris, Robert S.

Motivation: Complex genomes contain numerous repeated sequences, and genomic duplication is believed to be a main evolutionary mechanism to obtain new functions. Several tools are available for de...

Fold classification based on secondary structure – how much is gained by including loop topology? (2006)

Jeong, Jieun, Berman, Piotr, Przytycka, Teresa

Abstract Background It has been proposed that secondary structure information can be used to classify (to some extend) protein folds. Since this method utilizes very limited information about the...

8/7-approximation algorithm for (1,2)-TSP (2006)

Approximating the Online Set Multicover Problems Via Randomized Winnowing, to appear (2005)

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor for...

Tight approximability results for test set problems in bioinformatics (2005)

Abstract. In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family S of subsets of V with a positive real cost for every S...

Piotr Berman, Bhaskar Dasgupta, Ming-yang Kao

Abstract. In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished ” by...

The Inverse Protein Folding Problem on 2D and 3D Lattices ∗ (2005)

Piotr Berman, Bhaskar Dasgupta, Dhruv Mubayi, Robert Sloan, György Turán, Yi Zhang

In this paper we investigate the inverse protein folding (IPF) problem under the Canonical model on 3D and 2D lattices [13, 26]. In this problem, we are given a contact graph G = (V,E) of a protein...

Tight approximability results for test set problems in bioinformatics (2005)

Piotr Berman, Bhaskar Dasgupta, Ming-yang Kao

In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished ” by a family...

BMC Structural Biology Methodology article (2005)

Jieun Jeong, Piotr Berman, Teresa Przytycka, Biomed Central

Fold classification based on secondary structure – how much is gained by including loop topology?

The protein sequence design problem in canonical model on 2D and 3D lattices (2004)

Piotr Berman, Bhaskar Dasgupta, Dhruv Mubayi, Robert Sloan, Yi Zhang

Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks (2004)

Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks (2004)

In this paper we investigate the computational complexities of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: . We...

Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks (2004)

Abstract. In this paper we investigate the computational complexities of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows:...

The protein sequence design problem in canonical model on 2D and 3D lattices (2004)

In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: • We...

Piotr Berman, Bhaskar Dasgupta, Dhruv Mubayi, Robert Sloan

Abstract. In this paper we investigate the protein sequence design (PSD) problem (also known as the inverse protein folding problem) under the Canonical model 4 on 2D and 3D lattices [12, 25]. The...

Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks (2004)

The protein sequence design problem in canonical model on 2D and 3D lattices (2004)

In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: • We...

Piotr Berman, Bhaskar Dasgupta, Dhruv Mubayi, Robert Sloan

Abstract. In this paper we investigate the protein sequence design (PSD) problem (also known as the inverse protein folding problem) under the Canonical model 4 on 2D and 3D lattices [12, 25]. The...

Optimizing Misdirection (2003)

Berman,Piotr, Krysta,Piotr

Optimizing Misdirection (2003)

Berman, Piotr, Krysta, Piotr

A Bidding Protocol for Deploying Mobile Sensors (2003)

Guiling Wang, Guohong Cao, Piotr Berman, Thomas F. Laporta

Adequate coverage is very important for sensor networks to fulfill sensing tasks. In many working environments, it is necessary to make use of mobile sensors to provide the required coverage. We...

Slice and Dice: A Simple, Improved Approximate Tiling Recipe (2002)

Approximating Huffman Codes in Parallel (2002)

We are given a two dimensional array A[1 \Delta \Delta \Delta n; 1 \Delta \Delta \Delta n] where each A[i; j] stores a non-negative number. A (rectangular) tiling of A is a collection of rectangular...

Piotr Berman, Marek Karpinski, Yakov Nekrich

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is...

Simple approximation algorithm for nonoverlapping local alignments (2002)

Simple approximation algorithm for nonoverlapping local alignments (2002)

Problem. We study the following maximization problem called the Independent subset of Rectangles (IR) problem. We are a given a set S of N positively weighted axis parallel rectangles such that, for...

Slice and dice: A simple, improved approximate tiling recipe (2002)

Abstract We consider the following problem motivated by applications to nonoverlapping local alignment problems in computational molecular biology: we are a given a set of n positively weighted axis...

Fast optimal genome tiling with applications to microarray design and homology search (2002)

We are given a two dimensional array A[1 n � 1 n] where each A[i � j] stores a non-negative number. A (rectangular) tiling of A is a collection of rectangular portions A[l r�t b], called tiles,...

Piotr Berman, Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder

In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to find a set of tiles of maximum total...

Fast optimal genome tiling with applications to microarray design and homology search (2002)

Piotr Berman, Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder, ...

Abstract. In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to nd a set of tiles such that...

Improved Approximation Algorithms for Rectangle Tiling and Packing (Extended Abstract) (2001)

Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan, Suneeta Ramaswami

) 1 Introduction We study several rectangle tiling and packing problems. These are natural combinatorial problems that arise in many applications in databases, parallel computing and image...

Improved Approximations for General Minimum Cost Scheduling (2001)

Improved Approximation Algorithms for Rectangle Tiling and Packing (2001)

We give improved trade-off results on approximating general minimum cost scheduling problems.

Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan, Suneeta Ramaswami

1.375-Approximation Algorithm for Sorting by Reversals (2001)

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. This...

Discrete Applied Mathematics 127 (2003) 119–143 Aligning two fragmented sequences (2001)

Vamsi Veeramachaneni, Piotr Berman, Webb Miller

On the Exact Size of the Binary Space Partitioning of Sets of Isothetic Rectangles with Applications (Extended Abstract) (2000)

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling (2000)

) Abstract We show an upper bound of 3n on size of the Binary Space Partitioning (BSP) tree for a set of n isothetic rectangles, and an upper bound of 2n if the rectangles tile the underlying space....

Improvements in Throughput Maximization for Real-Time Scheduling (Extended Abstract) (2000)

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem...

Improvements in throughput maximization for real-time scheduling (2000)

) Abstract We consider the problem of o#-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of...

Piotr Berman

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem...

Multi-phase algorithms for throughput maximization for real-time scheduling (2000)

Optimal Phase Con ict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem...

Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alexander Zelikovsky X

We describe new, e cient algorithms for layout modi cation and phase assignment for dark eld alternating-type phase-shifting masks in the single-exposure regime. We make the following contributions....

Aligning two fragmented sequences (1999)

Vamsi Veeramachaneni, Piotr Berman

Upon completion of the human and mouse genome sequences, world-wide sequencing capacity will turn to other complex organisms. Current strategies call for many of these genomes to be incompletely...

Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)

Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alexander Zelikovsky

We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...

Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)

Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alex Zelikovsky

We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...

The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout (1999)

Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Alexander Zelikovsky

. Given a graph G with weighted edges, and a subset of nodes T , the T -join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u 2 T . We...

On Some Tighter Inapproximability Results (1999)

Improvements in Throughput Maximization for Real-Time Scheduling (1999)

We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX2SAT and E2-LIN-2, and...

Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)

We consider the problem of o#-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem...

Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alex Zelikovsky

We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...

Post-processing long pairwise alignments (1999)

Zhang, Zheng, Berman, Piotr, Wiehe, Thomas, Miller, Webb

Motivation: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming,...

Practical Issues in the Complexity of Neural Networks. (1998)

Parberry, Ian, Berman, Piotr, Schnitger, Georg

The equipment purchased under this Grant was used to supplement the theoretical work done under AFOSR-87-0400 with experimental results. The primary use of the equipment was to perform experiments to...

A Complexity Theory of Neural Networks. (1998)

Parberry, Ian, Berman, Piotr, Schnitger, Georg

Significant results have been obtained on the computation complexity of analog neural networks, and distribute voting. The computing power and learning algorithms for limited precision analog neural...

A Complexity Theory of Neural Networks. (1998)

Berman, Piotr, Schnitger, Georg, Parberry, Ian

Significant progress has been made in laying the foundations of a complexity theory of neural networks. The fundamental complexity classes have been identified and studied. The class of problems...

On Some Tighter Inapproximability Results, Further Improvements (1998)

On Approximating the Corner Cover Problem (1998)

Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in...

Alignments without low-scoring regions (1998)

The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon of n vertices has to be covered with the minimum number of rectangles included in the...

Zheng Zhang, Piotr Berman, Webb Miller

On the complexity of pattern matching for highly compressed texts (1997)

Berman, Piotr, Karpinski, Marek, Larmore, Lawrence L., Plandowski, Wojciech, Rytter, Wojciech

On Approximating the Corner Cover Problem (1997)

On-line Load Balancing for Related Machines (1997)

The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon of n vertices has to be covered with the minimum number of rectangles included in the...

Piotr Berman, Moses Charikar, Marek Karpinski

this paper appeared in Proceedings of WADS 97, LNCS 1272, SpringerVerlag, 1997, 116-125.

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts (1997)

Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

this paper to lack polynomial time algorithms

Randomized Robot Navigation Algorithms (1996)

Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks

We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...

The Complexity of Two-Dimensional Compressed Pattern-Matching (1996)

Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

We consider the complexity of problems for highly compressed 2-dimensional texts: compressed pattern-matching (when the pattern is not compressed and the text is compressed) and fully compressed...

Fast Sorting by Reversal (1996)

Piotr Berman, Sridhar Hannenhalli

Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed...

Constant Ratio Approximations of Feedback Vertex Sets in Weighted Undirected Graphs (1996)

Vineet Bafna, P. Bergman, T. Fujito, Piotr Berman, Toshihiro Fujito

A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. We show that a feedback vertex set approximating a minimum one within a...

Approaching the 5/4-Approximation for Rectilinear Steiner Trees (1995)

Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky

The rectilinear Steiner tree problem requires a shortest tree spanning a given vertex subset in the plane with rectilinear distance. It was proved that the output length of Zelikovsky's [25] and...

On Approximation Properties of the Independent Set Problem for Degree 3 Graphs (1995)

Piotr Berman, Toshihiro Fujito

. The main problem we consider in this paper is the Independent Set problem for bounded degree graphs. It is shown that the problem remains MAX SNP--complete when the maximum degree is bounded by 3....

Randomized Navigation to a Wall through Convex Obstacles (1994)