Piotr Berman

ACM Trans. Algorithms, 2022

2019

Testing convexity of figures under the uniform distribution.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

The Power and Limitations of Uniform Samples in Testing Properties of Figures.

[BibT_eX]

[DOI]

Algorithmica, 2019

2015

Constant-Time Testing and Learning of Image Properties.

[BibT_eX]

[DOI]

CoRR, 2015

The Distributed Selection Problem and the AKS Sorting Network.

[BibT_eX]

[DOI]

Junichiro Fukuyama

CoRR, 2015

2014

HybridPlan: a capacity planning technique for projecting storage requirements in hybrid storage systems.

[BibT_eX]

[DOI]

Anand Sivasubramaniam

J. Supercomput., 2014

Approximation Algorithms for Min-Max Generalization Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Steiner transitive-closure spanners of low-dimensional posets.

[BibT_eX]

[DOI]

Comb., 2014

On the Computational Complexity of Measuring Global Stability of Banking Networks.

[BibT_eX]

[DOI]

Algorithmica, 2014

Lp-testing.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

Approximation algorithms for spanner problems and Directed Steiner Forest.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Konstantin Makarychev

Inf. Comput., 2013

2012

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems.

[BibT_eX]

[DOI]

Andrzej Lingas

Algorithmica, 2012

Improving the performance of k-means clustering through computation skipping and data locality optimizations.

[BibT_eX]

[DOI]

Orhan Kislal

Mahmut T. Kandemir

Proceedings of the Computing Frontiers Conference, CF'12, 2012

Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Optimizing sensor movement planning for energy efficiency.

[BibT_eX]

[DOI]

ACM Trans. Sens. Networks, 2011

On Systemic Stability of Banking Networks

[BibT_eX]

[DOI]

CoRR, 2011

HybridStore: A Cost-Efficient, High-Performance Storage System Combining SSDs and HDDs.

[BibT_eX]

[DOI]

Anand Sivasubramaniam

Proceedings of the MASCOTS 2011, 2011

Improved Approximation for the Directed Spanner Problem.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Konstantin Makarychev

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

O(1)-Approximations for Maximum Movement Problems.

[BibT_eX]

[DOI]

Erik D. Demaine

Morteza Zadimoghaddam

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets

[BibT_eX]

[DOI]

CoRR, 2010

Successes and Failures of Elegant Algorithms in Computational Biology.

[BibT_eX]

[DOI]

Proceedings of the Bioinformatics Research and Applications, 6th International Symposium, 2010

A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Efficient Alignments of Metabolic Networks with Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the ICDMW 2010, 2010

Finding Sparser Directed Spanners.

[BibT_eX]

[DOI]

Ge Ruan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

On approximating four covering and packing problems.

[BibT_eX]

[DOI]

Mary V. Ashley

Tanya Y. Berger-Wolf

Wanpracha Art Chaovalitwongse

Ming-Yang Kao

J. Comput. Syst. Sci., 2009

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications

[BibT_eX]

[DOI]

Andrzej Lingas

CoRR, 2009

Consistent Sets of Secondary Structures in Proteins.

[BibT_eX]

[DOI]

Algorithmica, 2009

1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Aligning Two Genomic Sequences That Contain Duplications.

[BibT_eX]

[DOI]

Proceedings of the Comparative Genomics, International Workshop, 2009

2008

Approximating the online set multicover problems via randomized winnowing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Improving Strand Pairing Prediction through Exploring Folding Cooperativity.

[BibT_eX]

[DOI]

Teresa M. Przytycka

IEEE ACM Trans. Comput. Biol. Bioinform., 2008

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two

[BibT_eX]

[DOI]

CoRR, 2008

Approximating Transitivity in Directed Networks

[BibT_eX]

[DOI]

CoRR, 2008

On cycles in the transcription network of Saccharomyces cerevisiae.

[BibT_eX]

[DOI]

BMC Syst. Biol., 2008

HCV Quasispecies Assembly Using Network Flows.

[BibT_eX]

[DOI]

Proceedings of the Bioinformatics Research and Applications, 2008

Fast Alignments of Metabolic Networks.

[BibT_eX]

[DOI]

Proceedings of the 2008 IEEE International Conference on Bioinformatics and Biomedicine, 2008

2007

Bidding Protocols for Deploying Mobile Sensors.

[BibT_eX]

[DOI]

IEEE Trans. Mob. Comput., 2007

Optimal trade-off for Merkle tree traversal.

[BibT_eX]

[DOI]

Yakov Nekrich

Theor. Comput. Sci., 2007

On constructing an optimal consensus clustering from multiple clusterings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Approximating Transitive Reductions for Directed Networks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Computational complexity of some restricted instances of 3-SAT.

[BibT_eX]

[DOI]

Alexander D. Scott

Discret. Appl. Math., 2007

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

[BibT_eX]

[DOI]

Eduardo D. Sontag

Discret. Appl. Math., 2007

The inverse protein folding problem on 2D and 3D lattices.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

HomologMiner: looking for homologous genomic groups in whole genomes.

[BibT_eX]

[DOI]

Bioinform., 2007

Foreword.

[BibT_eX]

[DOI]

Jie Liang

Algorithmica, 2007

Faster Approximation of Distances in Graphs.

[BibT_eX]

[DOI]

Shiva Prasad Kasiviswanathan

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Bringing Folding Pathways into Strand Pairing Prediction.

[BibT_eX]

[DOI]

Teresa M. Przytycka

Proceedings of the Algorithms in Bioinformatics, 7th International Workshop, 2007

2006

Packing to angles and sectors.

[BibT_eX]

[DOI]

Shiva Prasad Kasiviswanathan

Bhuvan Urgaonkar

Electron. Colloquium Comput. Complex., 2006

A Linear-Time Algorithm for Studying Genetic Variation.

[BibT_eX]

[DOI]

Nikola Stojanovic

Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

Controlling Size When Aligning Multiple Genomic Sequences with Duplications.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

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

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees.

[BibT_eX]

[DOI]

Martin Fürer

Proceedings of the Computer Science, 2006

2005

Tight approximability results for test set problems in bioinformatics.

[BibT_eX]

[DOI]

Ming-Yang Kao

J. Comput. Syst. Sci., 2005

8/7-Approximation Algorithm for (1,2)-TSP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

On the Vehicle Routing Problem.

[BibT_eX]

[DOI]

Surajit K. Das

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Optimizing sensor movement planning for energy efficiency.

[BibT_eX]

[DOI]

Proceedings of the 2005 International Symposium on Low Power Electronics and Design, 2005

2004

Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search.

[BibT_eX]

[DOI]

J. Comput. Biol., 2004

Computational Complexity of Some Restricted Instances of 3SAT

[BibT_eX]

[DOI]

Alexander D. Scott

Electron. Colloquium Comput. Complex., 2004

Power efficient monitoring management in sensor networks.

[BibT_eX]

[DOI]

Proceedings of the 2004 IEEE Wireless Communications and Networking Conference , 2004

The Protein Sequence Design Problem in Canonical Model on 2D and 3D Lattices.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003

Approximation algorithms for MAX-MIN tiling.

[BibT_eX]

[DOI]

J. Algorithms, 2003

Approximability of Hypergraph Minimum Bisection.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Approximation Hardness of Short Symmetric Instances of MAX-3SAT.

[BibT_eX]

[DOI]

Alex D. Scott

Electron. Colloquium Comput. Complex., 2003

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

[BibT_eX]

[DOI]

Alex D. Scott

Electron. Colloquium Comput. Complex., 2003

Improved Approximation Lower Bounds on Small Occurrence Optimization

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Aligning two fragmented sequences.

[BibT_eX]

[DOI]

Vamsi Veeramachaneni

Webb Miller

Discret. Appl. Math., 2003

Optimizing misdirection.

[BibT_eX]

[DOI]

Piotr Krysta

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002

Exact Size of Binary Space Partitionings and Improved Rectangle Tiling Algorithms.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2002

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Approximating Huffman Codes in Parallel

[BibT_eX]

[DOI]

Yakov Nekrich

Electron. Colloquium Comput. Complex., 2002

Simple approximation algorithm for nonoverlapping local alignments.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Slice and dice: a simple, improved approximate tiling recipe.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles.

[BibT_eX]

[DOI]

J. Algorithms, 2001

Improved Approximations for General Minimum Cost Scheduling

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

On the Complexity of Positional Sequencing by Hybridization

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Efficient Amplifiers and Bounded Degree Optimization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

1.375-Approximation Algorithm for Sorting by Reversals

[BibT_eX]

[DOI]

Sridhar Hannenhalli

Electron. Colloquium Comput. Complex., 2001

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Approximating Minimum Unsatisfiability of Linear Equations

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Improved approximation algorithms for rectangle tiling and packing.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

An Online Algorithm for the Postman Problem with a Small Penalty.

[BibT_eX]

[DOI]

Junichiro Fukuyama

Proceedings of the Approximation, 2001

2000

Optimal phase conflict removal for layout of dark field alternatingphase shifting masks.

[BibT_eX]

[DOI]

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2000

A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs.

[BibT_eX]

Nord. J. Comput., 2000

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling.

[BibT_eX]

[DOI]

J. Comb. Optim., 2000

Winnowing Sequences from a Database Search.

[BibT_eX]

[DOI]

J. Comput. Biol., 2000

On-Line Load Balancing for Related Machines

[BibT_eX]

[DOI]

Moses Charikar

Electron. Colloquium Comput. Complex., 2000

A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2000

Improvements in throughout maximization for real-time scheduling.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Variable length sequencing with two lengths.

[BibT_eX]

[DOI]

Junichiro Fukuyama

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem.

[BibT_eX]

[DOI]

Vineet Bafna

SIAM J. Discret. Math., 1999

Speed is More Powerful than Clairvoyance.

[BibT_eX]

Chris Coulston

Nord. J. Comput., 1999

On Approximation Properties of the Independent Set Problem for Low Degree Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1999

Post-processing long pairwise alignments.

[BibT_eX]

[DOI]

Bioinform., 1999

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Optimal phase conflict removal for layout of dark field alternating phase shifting masks.

[BibT_eX]

[DOI]

Proceedings of the 1999 International Symposium on Physical Design, 1999

On Some Tighter Inapproximability Results (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

1998

Alignments without Low-Scoring Regions.

[BibT_eX]

[DOI]

Zheng Zhang

Webb Miller

J. Comput. Biol., 1998

On Some Tighter Inapproximability Results, Further Improvements

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

On Some Tighter Inapproximability Results

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Speed is More Powerful than Claivoyance.

[BibT_eX]

[DOI]

Chris Coulston

Proceedings of the Algorithm Theory, 1998

Adaptability and the Usefulness of Hints (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1998

1997

A Nearly Optimal Parallel Algorithm for the Voronoi Diagram of a Convex Polygon.

[BibT_eX]

[DOI]

Andrzej Lingas

Theor. Comput. Sci., 1997

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures.

[BibT_eX]

[DOI]

Krzysztof Diks

Andrzej Pelc

J. Algorithms, 1997

Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems.

[BibT_eX]

[DOI]

Algorithmica, 1997

A Linear-Time Algorithm for the 1-Mismatch Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

On-Line Algorithms for Steiner Tree Problems (Extended Abstract).

[BibT_eX]

[DOI]

Chris Coulston

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Competing against Specialists.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 1997

1996

Randomized Robot Navigation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On-line Searching and Navigation.

[BibT_eX]

[DOI]

Proceedings of the Online Algorithms, 1996

Fast Sorting by Reversal.

[BibT_eX]

[DOI]

Sridhar Hannenhalli

Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995

On the Approximation Properties of Independent Set Problem in Degree 3 Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs.

[BibT_eX]

[DOI]

Vineet Bafna

Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

1994

Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data.

[BibT_eX]

[DOI]

Mirjana Spasojevic

IEEE Trans. Parallel Distributed Syst., 1994

Reliable distributed diagnosis for multiprocessor systems with random faults.

[BibT_eX]

[DOI]

Andrzej Pelc

Networks, 1994

Improved Approximations for the Steiner Tree Problem.

[BibT_eX]

[DOI]

Viswanathan Ramaiyer

J. Algorithms, 1994

Online Navigation in a Room.

[BibT_eX]

[DOI]

J. Algorithms, 1994

Approximating Maximum Independent Set in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Martin Fürer

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Approaching the 5/4-Approximation for Rectilinear Steiner Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1994

1993

Cloture Votes: n/4-Resilient Distributed Consensus in t+1 Rounds.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1993

Fast Consensus in Networks of Bounded Degree.

[BibT_eX]

[DOI]

Distributed Comput., 1993

Quick Atomic Broadcast (Extended Abstract).

[BibT_eX]

[DOI]

Anupam A. Bharali

Proceedings of the Distributed Algorithms, 7th International Workshop, 1993

Randomized Distributed Agreement Revisited.

[BibT_eX]

[DOI]

Proceedings of the Digest of Papers: FTCS-23, 1993

1992

On the Complexity of Approximating the Independent Set Problem

[BibT_eX]

[DOI]

Georg Schnitger

Inf. Comput., January, 1992

A note on the complexity of reliability in neural networks.

[BibT_eX]

[DOI]

Ian Parberry

Georg Schnitger

IEEE Trans. Neural Networks, 1992

Optimal Early Stopping in Distributed Consensus (Extended Abstract).

[BibT_eX]

[DOI]

Kenneth J. Perry

Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

On-Line Navigation in a Room.

[BibT_eX]

[DOI]

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Distributed Consensus in Semi-Synchronous Systems.

[BibT_eX]

[DOI]

Anupam A. Bharali

Proceedings of the 6th International Parallel Processing Symposium, 1992

1991

Efficient Distributed Consensus with n = (3 + epsilon) t Processors (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

1990

Weighted Voting for Operation Dependent Management of Replicated Data.

[BibT_eX]

[DOI]

Mirjana Obradovic

Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Fast Consensus in Networks of Bounded Degree (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data.

[BibT_eX]

[DOI]

Mirjana Obradovic

Proceedings of the Ninth Symposium on Reliable Distributed Systems, 1990

A Competitive 3-Server Algorithm.

[BibT_eX]

[DOI]

Howard J. Karloff

Gábor Tardos

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Distributed probabilistic fault diagnosis for multiprocessor systems.

[BibT_eX]

[DOI]

Andrzej Pelc

Proceedings of the 20th International Symposium on Fault-Tolerant Computing, 1990

1989

Efficient Agreement on Bounded-Degree Networks.

[BibT_eX]

Proceedings of the International Conference on Parallel Processing, 1989

Asymptotically Optimal Distributed Consensus (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Towards Optimal Distributed Consensus (Extended Abstract)

[BibT_eX]

[DOI]

Kenneth J. Perry

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Investigations of Fault-Tolerant Networks of Computers (Preliminary Version)

[BibT_eX]

[DOI]

Janos Simon

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987

A Learning Algorithm for a Class of Context-Free Languages (Extended Abstract).

[BibT_eX]

Robert Roos

Proceedings of the Methodologies for Intelligent Systems, 1987

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

[BibT_eX]

[DOI]

Robert Roos

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1983

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

[BibT_eX]

[DOI]

Janos Simon

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Deterministic Dynamic Logic of Recursive Programs is Weaker than Dynamic Logic.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1983

1982

On the Power of Nondeterminism in Dynamic Logic.

[BibT_eX]

[DOI]

Joseph Y. Halpern

Jerzy Tiuryn

Proceedings of the Automata, 1982

1980

A Note on Sweeping Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

1978

Relationship Between Density and Deterministic Complexity of NP-Complete Languages.

[BibT_eX]

[DOI]