Baruch M Schieber  Baruch M Schieber photo       

contact information

Senior Manager, Mathematical Sciences
Thomas J. Watson Research Center, Yorktown Heights, NY USA
  +1dash914dash945dash1169

links

Professional Associations

Professional Associations:  ACM  |  ACM SIGACT  |  IBM Academy of Technology


2013

The Approximability of the Binary Paintshop Problem
Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber
APPROX-RANDOM, pp. 205--217, Springer, 2013

The Euclidean k-Supplier Problem
Viswanath Nagarajan, Baruch Schieber, Hadas Shachnai
IPCO, pp. 290--301, Springer, 2013

All-or-Nothing generalized assignment with application to scheduling advertising campaigns
Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, Tami Tamir
Integer Programming and Combinatorial Optimization, pp. 13--24, Springer, 2013


2011

Shape rectangularization problems in intensity-modulated radiation therapy
Nikhil Bansal, Danny Z Chen, Don Coppersmith, Xiaobo S Hu, Shuang Luan, Ewa Misiolek, Baruch Schieber, Chao Wang
Algorithmica 60(2), 421--450, Springer, 2011


2010

Dynamic pricing for impatient bidders
Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rurda, Baruch Schieber, Maxim Sviridenko
ACM Transactions on Algorithms (TALG) 6(2), 35, ACM, 2010


2009

Throughput maximization of real-time scheduling with batching
Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Seffi Naor, Baruch Schieber, Hadas Shachnai
ACM Transactions on Algorithms (TALG) 5(2), 18, ACM, 2009


2008

Traffic engineering of management flows by link augmentations on confluent trees
Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S Mirrokni, Joseph Seffi Naor, Baruch Schieber
Theory of Computing Systems 42(1), 2--26, Springer, 2008

Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon Moni Shahar, Maxim Sviridenko
ACM Transactions on Algorithms (TALG) 4(3), 34, ACM, 2008


2007

Non-preemptive min-sum scheduling with resource augmentation
Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, B Schicber, Cliff Stein
Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on, pp. 614--624

Inventory allocation and transportation scheduling for logistics of network-centric military operations

IBM Journal of Research and Development 51(3.4), 391-407, 2007


2006

Vehicle Routing and Staffing for Sedan Service
Oktay Gunluk, Tracy Kimbrel, Laszlo Ladanyi, Baruch Schieber, Gregory B. Sorkin
Transportation Science 40(3), 313-326, 2006

Minimizing migrations in fair multiprocessor scheduling of persistent tasks
Tracy Kimbrel, Baruch Schieber, Maxim Sviridenko
Journal of Scheduling 9(4), 365--379, Springer, 2006

A quasi-PTAS for unsplittable flow on line graphs
Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 721--729, 2006


2005

Computing the minimum DNF representation of Boolean functions defined by intervals
Baruch Schieber, Daniel Geist, Ayal Zaks
Discrete Applied Mathematics 149(1), 154--173, Elsevier, 2005


2004

Buffer overflow management in QoS switches
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko
SIAM Journal on Computing 33(3), 563--583, SIAM, 2004

Further improvements in competitive guarantees for QoS buffering
Nikhil Bansal, Lisa K Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko
Automata, Languages and Programming, pp. 196--207, Springer, 2004

Resource optimization in QoS multicast routing of real-time multimedia
Moses Charikar, Joseph Naor, Baruch Schieber
Networking, IEEE/ACM Transactions on 12(2), 340--348, IEEE, 2004


2003

Sparse LCS Common Substring Alignment
G.M. Landau, B. Schieber, M. Ziv-Ukelson
Information Processing Letters 88(6), 259--270, Elsevier, 2003

Pushing dependent data in clients--providers--servers systems
Amotz Bar-Noy, Joseph Seffi Naor, Baruch Schieber
Wireless Networks 9(5), 421--430, Springer, 2003



2002

Improved approximations of crossings in graph drawings and VLSI layout areas
Guy Even, Sudipto Guha, Baruch Schieber
SIAM Journal on Computing 32(1), 231--252, SIAM, 2002

Minimizing service and operation costs of periodic scheduling
Amotz Bar-Noy, Randeep Bhatia, Joseph Seffi Naor, Baruch Schieber
Mathematics of Operations Research 27(3), 518--544, INFORMS, 2002


2001

The edge versus path incidence matrix of series-parallel graphs and greedy packing
Alan J Hoffman, Baruch Schieber
Discrete applied mathematics 113(2), 275--284, Elsevier, 2001

Approximating the throughput of multiple machines in real-time scheduling
Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber
SIAM Journal on Computing 31(2), 331--352, SIAM, 2001

A unified approach to approximating resource allocation and scheduling
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber
Journal of the ACM (JACM) 48(5), 1069--1090, ACM, 2001


2000

Message multicasting in heterogeneous networks
Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber
SIAM Journal on Computing 30(2), 347--358, SIAM, 2000

Optimal multiple message broadcasting in telephone-like communication systems
Amotz Bar-Noy, Shlomo Kipnis, Baruch Schieber
Discrete Applied Mathematics 100(1), 1--15, Elsevier, 2000

Approximating minimum subset feedback sets in undirected graphs with applications
Guy Even, Joseph Naor, Baruch Schieber, Leonid Zosin
SIAM Journal on Discrete Mathematics 13(2), 255--267, SIAM, 2000

Divide-and-conquer approximation algorithms via spreading metrics
Guy Even, Joseph Seffi Naor, Satish Rao, Baruch Schieber
Journal of the ACM (JACM) 47(4), 585--616, ACM, 2000


1999

Bandwidth allocation with preemption
Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber
SIAM Journal on Computing 28(5), 1806--1828, SIAM, 1999

Lower bounds on the depth of monotone arithmetic computations
Don Coppersmith, Baruch Schieber
Journal of Complexity 15(1), 17--29, Elsevier, 1999

Fast approximate graph partitioning algorithms
Guy Even, Joseph Naor, Satish Rao, Baruch Schieber
SIAM Journal on Computing 28(6), 2187--2214, SIAM, 1999

Efficient recovery from power outage
Sudipto Guha, Anna Moss, Joseph Seffi Naor, Baruch Schieber
Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 574--582, 1999


1998


Guaranteeing fair service to persistent dependent tasks
Amotz Bar-Noy, Alain Mayer, Baruch Schieber, Madhu Sudan
SIAM journal on Computing 27(4), 1168--1189, SIAM, 1998

A sublinear space, polynomial time algorithm for directed st connectivity
Greg Barnes, Jonathan F Buss, Walter L Ruzzo, Baruch Schieber
SIAM Journal on Computing 27(5), 1273--1282, SIAM, 1998

Approximating minimum feedback sets and multicuts in directed graphs
Guy Even, J Seffi Naor, Baruch Schieber, Madhu Sudan
Algorithmica 20(2), 151--174, Springer, 1998

The complexity of finding most vital arcs and nodes
Amotz Bar-Noy, Samir Khuller, Baruch Schieber
Noy, S Khuller, B Schieber - 1998 - drum.lib.umd.edu


1997

How much can hardware help routing?
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
Journal of the ACM (JACM) 44(5), 726--741, ACM, 1997

Deterministic many-to-many hot potato routing
Allan Borodin, Yuval Rabani, Baruch Schieber
Parallel and Distributed Systems, IEEE Transactions on 8(6), 587--596, IEEE, 1997

A linear-time algorithm for computing the intersection of all odd cycles in a graph
Leizhen Cai, Baruch Schieber
Discrete applied mathematics 73(1), 27--34, Elsevier, 1997

A tight bound for approximating the square root
Nader H Bshouty, Yishay Mansour, Baruch Schieber, Prasoon Tiwari
Information processing letters 63(4), 211--213, Elsevier, 1997

Navigating in unfamiliar geometric terrain
Avrim Blum, Prabhakar Raghavan, Baruch Schieber
SIAM Journal on Computing 26(1), 110--137, SIAM, 1997


1996

A fast parallel algorithm for finding the convex hull of a sorted point set
Omer Berkman, Baruch Schieber, Uzi Vishkin
International Journal of Computational Geometry \& Applications 6(02), 231--241, World Scientific, 1996

Efficient routing in optical networks
Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
Journal of the ACM (JACM) 43(6), 973--1001, ACM, 1996


1995

Efficient minimum cost matching and transportation using the quadrangle inequality
Alok Aggarwal, Amotz Barnoy, Samir Khuller, Dina Kravets, Baruch Schieber
Journal of Algorithms 19(1), 116--143, Elsevier, 1995

Computing global combine operations in the multiport postal model
Amotz Bar-Noy, Jehoshua Bruck, Ching-Tien Ho, Shlomo Kipnis, Baruch Schieber
Parallel and Distributed Systems, IEEE Transactions on 6(8), 896--900, IEEE, 1995

Optimal computation of census functions in the postal model
Amotz Bar-Noy, Shlomo Kipnis, Baruch Schieber
Discrete Applied Mathematics 58(3), 213--222, Elsevier, 1995

Competitive paging with locality of reference
Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber
Journal of Computer and System Sciences 50(2), 244--258, Elsevier, 1995


1994

Calling names in nameless networks
Baruch Schieber, Marc Snir
Information and Computation 113(1), 80--101, Academic Press, 1994

A deterministic O(k3)-competitive k-server algorithm for the circle
Amos Fiat, Yuval Rabani, Yiftach Ravid, Baruch Schieber
Algorithmica 11(6), 572--578, Springer, 1994

Finding a minimum-weight k-link path in graphs with the concave Monge property and applications
Alok Aggarwal, Baruch Schieber, Takeshi Tokuyama
Discrete & Computational Geometry 12(1), 263--280, Springer, 1994


1993

An optimal algorithm for computing census functions in message-passing systems
Amotz Bar-Noy, Shlomo Kipnis, Baruch Schieber
Parallel Processing Letters 3(01), 19--23, World Scientific, 1993

Improved selection in totally monotone arrays
Yishay Mansour, James K Park, Baruch Schieber, Sandeep Sen
International Journal of Computational Geometry \& Applications 3(02), 115--132, World Scientific, 1993

Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values
Omer Berkman, Baruch Schieber, Uzi Vishkin
Journal of Algorithms 14(3), 344--370, Elsevier, 1993

Fast deflection routing for packets and worms
Amotz Bar-Noy, Prabhakar Raghavan, Baruch Schieber, Hisao Tamaki
Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, pp. 75--86, 1993

Parallel lowest common ancestor computation
Baruch Schieber
Synthesis of Parallel Algorithms, 259--273, Morgan Kaufmann Pub, 1993


1992


Fast exponentiation using the truncation operation
Nader H Bshouty, Yishay Mansour, Baruch Schieber, Prasson Tiwari
computational complexity 2(3), 244--255, Springer, 1992

On independent spanning trees
Samir Khuller, Baruch Schieber
Information Processing Letters 42(6), 321--323, Elsevier, 1992

Fast geometric approximation techniques and geometric embedding problems
Marshall W Bern, Howard J Karloff, Prabhakar Raghavan, Baruch Schieber
Theoretical Computer Science 106(2), 265--281, Elsevier, 1992

An efficient algorithm for the all pairs suffix-prefix problem
Dan Gusfield, Gad M Landau, Baruch Schieber
Information Processing Letters 41(4), 181--185, Elsevier, 1992


1991

Computing external farthest neighbors for a simple polygon
Pankaj K Agarwal, Alok Aggarwal, Boris Aronov, S Rao Kosaraju, Baruch Schieber, Subhash Suri
Discrete Applied Mathematics 31(2), 97--111, Elsevier, 1991

Lower bounds for computations with the floor operation
Yishay Mansour, Baruch Schieber, Prasoon Tiwari
SIAM Journal on Computing 20(2), 315--327, SIAM, 1991

A lower bound for integer greatest common divisor computations
Yishay Mansour, Baruch Schieber, Prasoon Tiwari
Journal of the ACM (JACM) 38(2), 453--471, ACM, 1991

On-line dynamic programming with applications to the prediction of RNA secondary structure
Lawrence L Larmore, Baruch Schieber
Journal of Algorithms 12(3), 490--515, Elsevier, 1991

Efficient Parallel Algorithms for Testing k and Finding Disjoint s-t Paths in Graphs
Samir Khuller, Baruch Schieber
SIAM Journal on Computing 20(2), 352--375, SIAM, 1991


1990


The power of multimedia: combining point-to-point and multiaccess networks
Yehuda Afek, Gad M Landau, Baruch Schieber, Moti Yung
Information and Computation 84(1), 97--118, Elsevier, 1990


1989

Finding the edge connectivity of directed graphs
Yishay Mansour, Baruch Schieber
Journal of Algorithms 10(1), 76--85, Elsevier, 1989

Parallel algorithms for maximum bipartite matchings and maximum 0--1 flows
Baruch Schieber, Shlomo Moran
Journal of Parallel and Distributed Computing 6(1), 20--38, Elsevier, 1989


1988

Parallel construction of a suffix tree with applications
Alberto Apostolico, Costas Iliopoulos, Gad M. Landau, Baruch Schieber, Uzi Vishkin
Algorithmica 3(1-4), 347--365, Springer, 1988

On finding lowest common ancestors: simplification and parallelization
Baruch Schieber, Uzi Vishkin
SIAM Journal on Computing 17(6), 1253--1262, SIAM, 1988

On finding most uniform spanning trees
Zvi Galil, Baruch Schieber
Discrete Applied Mathematics 20(2), 173--175, Elsevier, 1988


1987



1986

Parallel ear decomposition search (EDS) and st-numbering in graphs
Yael Maon, Baruch Schieber, Uzi Vishkin
Theoretical Computer Science 47, 277--298, Elsevier, 1986