Baruch Schieber

Katz, D., & Schieber, Baruch M., & Shachnai, H. (2019). Flexible Resource Allocation to Interval Jobs. Algorithmica, 81, 3217--3244.

Schieber, Baruch M., & Shachnai, H., & Tamir, G., & Tamir, T. (2018). A Theory and Algorithms for Combinatorial Reoptimization. Algorithmica, 80, 576--607.

Toubaline, S., & D'Ambrosio, C., & Liberti, L., & Poirion, P-L., & Schieber, Baruch M., & Shachnai, H. (2018). Complexity and inapproximability results for the Power Edge Set problem. Journal of Combinatorial Optimization, 35, 895--905.

Adany, R., & Feldman, M., & Haramaty, E., & Khandekar, R., & Schieber, Baruch M., & Schwartz, R., & Shachnai, H., & Tamir, T. (2016). All-or-Nothing Generalized Assignment with Applications to Scheduling Advertising Campaigns. ACM Transactions on Algorithms, 12, 38:1--38:25.

Khandekar, R., & Schieber, Baruch M., & Shachnai, H., & Tamir, T. (2015). Real-time Scheduling to Minimize Machine Busy Times. Journal of Scheduling, 18, 561--573.

Bansal, N., & Z., D. Chen, & Coppersmith, D., & S., X. Hu, & Luan, S., & Misiolek, E., & Schieber, Baruch M., & Wang, C. (2011). Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy. Algorithmica, 60, 421--450.

Bansal, N., & Chen, N., & Cherniavsky, N., & Rudra, A., & Schieber, Baruch M., & Sviridenko, M. (2010). Dynamic Pricing for Impatient Bidders. ACM Transactions on Algorithms, 6, 35:1--35:21.

Bar-Noy, A., & Guha, S., & Katz, Y., & Naor, J., & Schieber, Baruch M., & Shachnai, H. (2009). Throughput Maximization of Real-Time Scheduling with Batching. ACM Transactions on Algorithms, 5, 18:1--18:17.

Even, G., & Levi, R., & Rawitz, D., & Schieber, Baruch M., & Shahar, S., & Sviridenko, M. (2008). Algorithms for Capacitated Rectangle Stabbing and Lot Sizing with Joint Set-Up Costs. ACM Transactions on Algorithms, 4, 34:1--34:17.

Bahtia, R., & Immorlica, N., & Kimbrel, T., & Mirrokni, V., & Naor, J., & Schieber, Baruch M. (2008). Traffic Engineering of Management Flow by Link Augmentations on Confluent Trees. Theory of Computing Systems, 42(1), 2--26.

Barahona, F., & Chowdhary, P., & Ettl, M., & Huang, P., & Kimbrel, T., & Ladanyi, L., & M., Y. Lee, & Schieber, Baruch M., & Sourirajan, K., & I., M. Sviridenko, & M., G. Swirszcz (2007). Inventory allocation and transportation scheduling for logistics of network-centric military operations. IBM Journal of Research and Development, 51, 391--408.

Kimbrel, T., & Schieber, Baruch M., & Sviridenko, M. (2006). Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks. Journal of Scheduling, 9, 365--379.

Gunluk, O., & Kimbrel, T., & Ladanyi, L., & Schieber, Baruch M., & Sorkin, G. (2006). Vehicle routing and staffing for sedan service. Transportation Science, 40, 313--326.

Schieber, Baruch M., & Geist, D., & Zaks, A. (2005). Computing the minimum DNF representation of Boolean functions defined by intervals. Discrete Applied Mathematics, 149, 154--173.

Kesselman, A., & Lotker, Z., & Mansour, Y., & Patt-Shamir, B., & Schieber, Baruch M., & Sviridenko, M. (2004). Buffer Overflow management in QoS Switches. SIAM Journal on Computing, 33, 563--583.

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

Even, G., & Guha, S., & Schieber, Baruch M. (2003). Improved approximations of crossings in graph drawings. SIAM Journal on Computing, 32, 231--252.

Bar-Noy, A., & Naor, J., & Schieber, Baruch M. (2003). Publishing dependent data in clients-providers-servers systems. Wireless Networks, 9, 421--430.

Batiste, P., & Schieber, Baruch M. (2003). Scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. Journal of Scheduling, 6, 295--404.

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

Bar-Noy, A., & Bhatia, R., & Naor, J., & Schieber, Baruch M. (2002). Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research, 27, 518--544.

Bar-Noy, A., & Bar-Yehuda, R., & Freund, A., & Naor, J., & Schieber, Baruch M. (2001). A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48, 1069--1090.

Bar-Noy, A., & Guha, S., & Naor, J., & Schieber, Baruch M. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing, 31, 331--352.

Hoffman, A.J., & Schieber, Baruch M. (2001). The edge versus path incidence matrix of series parallel graphs and greedy packing. Discrete Mathematics, 113, 275--284.

Even, G., & Naor, J., & Schieber, Baruch M., & Zosin, L. (2000). Approximating minimum subset feedback sets in undirected graphs with applications. SIAM Journal on Discrete Mathematics, 13, 255--267.

Even, G., & Naor, J., & Rao, S., & Schieber, Baruch M. (2000). Divide-and-conquer approximation algorithms via spreading metrics. Journal of the ACM, 47, 585--616.

Bar-Noy, A., & Guha, S., & Naor, J., & Schieber, Baruch M. (2000). Message multicasting in heterogeneous networks. SIAM Journal on Computing, 30, 347--358.

Bar-Noy, A., & Kipnis, S., & Schieber, Baruch M. (2000). Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems. Discrete Applied Mathematics, 100, 1--15.

Even, G., & Naor, J., & Rao, S., & Schieber, Baruch M. (1999). Approximate Graph Partitioning Algorithms. SIAM Journal on Computing, 28, 2187--2214.

Bar-Noy, A., & Canetti, R., & Kutten, S., & Mansour, Y., & Schieber, Baruch M. (1999). Bandwidth allocation with preemption. SIAM Journal on Computing, 28, 1806--1828.

Coppersmith, D., & Schieber, Baruch M. (1999). Lower bounds on the depth of monotone arithmetic computations. Journal of Complexity, 15, 17--29.

Aggarwal, A., & Coppersmith, D., & Khanna, S., & Motwani, R., & Schieber, Baruch M. (1999). The angular-metric traveling salesman problem. SIAM Journal on Computing, 29, 697--711.

Barnes, G., & Buss, J., & Ruzzo, W.L., & Schieber, Baruch M. (1998). A sub-linear space, polynomial time algorithm for directed $s-t$ connectivity. SIAM Journal on Computing, 27, 1273--1282.

Even, G., & Naor, J., & Schieber, Baruch M., & Sudan, M. (1998). Approximating minimum feedback sets and multi-cuts in directed graphs. Algorithmica, 20, 151--174.

Schieber, Baruch M. (1998). Computing a minimum weight $K$-link path in graphs with the concave Monge property. Journal of Algorithms, 29, 204--222.

Bar-Noy, A., & Mayer, A., & Schieber, Baruch M., & Sudan, M. (1998). Guaranteeing fair service to persistent dependent tasks. SIAM Journal on Computing, 24, 1168--1189.

Cai, L., & Schieber, Baruch M. (1997). A linear-time algorithm for computing the intersection of all odd cycles in a graph. Discrete Applied Mathematics, 73(1), 27--34.

Bshouty, N., & Mansour, Y., & Schieber, Baruch M., & Tiwari, P. (1997). A tight bound for approximating the square root. Information Processing Letters, 63, 211--213.

Borodin, A., & Rabani, Y., & Schieber, Baruch M. (1997). Deterministic many-to-many hot potato routing. IEEE Trans. on Parallel and Distributed Systems, 8(6), 587--596.

Borodin, A., & Raghavan, P., & Schieber, Baruch M., & Upfal, E. (1997). How much can hardware help routing?. Journal of the ACM, 44(5), 726--741.

Blum, A., & Raghavan, P., & Schieber, Baruch M. (1997). Navigating in unfamiliar geometric terrain. SIAM Journal on Computing, 26(1), 110--137.

Berkman, O., & Schieber, Baruch M., & Vishkin, U. (1996). A fast parallel algorithm for finding the convex hull of a sorted point set. International Journal of Computational Geometry and Applications, 6, 231--241.

Aggarwal, A., & Bar-Noy, A., & Coppersmith, D., & Ramaswami, R., & Schieber, Baruch M., & Sudan, M. (1996). Efficient routing in optical networks. Journal of the ACM, 43(6), 973--1001.

Borodin, A., & Irani, S., & Raghavan, P., & Schieber, Baruch M. (1995). Competitive paging with locality of reference. Journal of Computer and System Sciences, 50, 244--258.

Bar-Noy, A., & Bruck, J., & Ho, C-T., & Kipnis, S., & Schieber, Baruch M. (1995). Computing global combine operations in the Multi-Port Postal Model. IEEE Trans. on Parallel and Distributed Systems, 6, 896--900.

Aggarwal, A., & Bar-Noy, A., & Kravets, D., & Khuller, S., & Schieber, Baruch M. (1995). Efficient minimum cost matching using the quadrangle inequality. Journal of Algorithms, 19, 116--143.

Bar-Noy, A., & Kipnis, S., & Schieber, Baruch M. (1995). Optimal computation of census functions in the Postal Model. Discrete Applied Mathematics, 58, 213--222.

Fiat, A., & Rabani, Y., & Ravid, Y., & Schieber, Baruch M. (1994). A deterministic $O(k{^3})$ competitive $k$-server algorithm for the circle. Algorithmica, 11, 572--578.

Schieber, Baruch M., & Snir, M. (1994). Calling names on nameless networks. Information and Computation, 113, 80--101.

Aggarwal, A., & Schieber, Baruch M., & Tokuyama, T. (1994). Finding a minimum weight $K$-link path in graphs with Monge property and applications. Journal of Discrete and Computational Geometry, 12, 263--280.

Bar-Noy, A., & Kipnis, S., & Schieber, Baruch M. (1993). An optimal algorithm for computing census functions in message-passing systems. Parallel Processing Letters, 3, 19--23.

Mansour, Y., & Park, J.K., & Schieber, Baruch M., & Sen, S. (1993). Improved selection in totally monotone arrays. International Journal of Computational Geometry and Applications, 3, 115--132.

Berkman, O., & Schieber, Baruch M., & Vishkin, U. (1993). Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. Journal of Algorithms, 14, 344--370.

Gusfield, D., & Landau, G.M., & Schieber, Baruch M. (1992). An efficient algorithm for the all pairs Suffix-Prefix problem. Information Processing Letters, 41, 181--185.

Bern, M.W., & Karloff, H.J., & Raghavan, P., & Schieber, Baruch M. (1992). Fast approximation techniques and geometric embedding problems. Theoretical Computer Science, 106, 265--281.

Bshouty, N.H., & Mansour, Y., & Schieber, Baruch M., & Tiwari, P. (1992). Fast exponentiation using the truncation operation. Computational Complexity, 2, 244--255.

Khuller, S., & Schieber, Baruch M. (1992). On independent spanning trees. Information Processing Letters, 42, 321--323.

Mansour, Y., & Schieber, Baruch M. (1992). The intractability of bounded protocols for non-FIFO channels. Journal of the ACM, 39, 783--799.

Mansour, Y., & Schieber, Baruch M., & Tiwari, P. (1991). A lower bound for integer greatest common divisor computations. Journal of the ACM, 38, 453--471.

Agarwal, P.K., & Aggarwal, A., & Aronov, B., & Kosaraju, S.R., & Schieber, Baruch M., & Suri, S. (1991). Computing external farthest neighbors for a simple polygon. Discrete Applied Mathematics, 31, 97--111.

Khuller, S., & Schieber, Baruch M. (1991). Efficient parallel algorithms for testing connectivity and finding disjoint $s-t$ paths in graphs. SIAM Journal on Computing, 20, 352--375.

Mansour, Y., & Schieber, Baruch M., & Tiwari, P. (1991). Lower bounds for computations with the floor operation. SIAM Journal on Computing, 20, 315--327.

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

Schieber, Baruch M., & Vishkin, U. (1990). Finding all nearest neighbors for convex polygons in parallel: a new lower bound technique and a matching algorithm. Discrete Applied Mathematics, 29, 97--111.

Afek, Y., & Landau, G.M., & Schieber, Baruch M., & Yung, M. (1990). The power of multimedia: combining point-to-point and multiaccess networks. Information and Computation, 84, 97--118.

Mansour, Y., & Schieber, Baruch M. (1989). Finding the edge connectivity of directed graphs. Journal of Algorithms, 10, 76--85.

Schieber, Baruch M., & Moran, S. (1989). Parallel algorithms for maximum bipartite matchings and maximum $0-1$ flows. Journal of Parallel and Distributed Computing, 6, 20--38.

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

Galil, Z., & Schieber, Baruch M. (1988). On finding most uniform trees (a note). Discrete Applied Mathematics, 20, 173--175.

Apostolico, A., & Iliopoulos, C., & Landau, G.M., & Schieber, Baruch M., & Vishkin, U. (1988). Parallel construction of a suffix tree with applications. Algorithmica, 3, 347--365.

Maon, Y., & Schieber, Baruch M., & Vishkin, U. (1986). Parallel Ear Decomposition Search (EDS) and st-numbering in graphs. Theoretical Computer Science, 47, 277--298.

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
2019

Generalized Assignment via Submodular Optimization with Reserved Capacity
2019

Scalable Fair Clustering
2019

The Preemptive Resource Allocation Problem
2019

Brief Announcement: Approximation Algorithms for Preemptive Resource Allocation
2018

Fully Dynamic Maximal Independent Set with Sublinear Update Time
2018

Fully Dynamic MIS in Uniformly Sparse Graphs
2018

Generalized Assignment of Time-Sensitive Item Groups
2018

Globally Optimal Symbolic Regression
2017

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks
2016

Complexit\'e du Probl\`eme Power Edge Set
2016

Real-Time k-Bounded Preemptive Scheduling
2016

Subgraph Counting: Color Coding Beyond Trees
2016

The Container Selection Problem
2015

All-or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns
2013

The Approximability of the Binary Paintshop Problem
2013

The Euclidean k-Supplier Problem
2013

Minimizing Busy Time in Multiple Machine Real-time Scheduling
2010

Dynamic Pricing for Impatient Bidders
2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation
2007

A Quasi-PTAS for Unsplittable Flow on Line Graphs
2006

Minimizing Setup and Beam-On Times in Radiation Therapy
2006

Traffic Engineering of Data Networks for Management Data
2005

Further Improvements in Competitive Guarantees for QoS Buffering
2004

Minimizing migrations in fair multiprocessor scheduling of persistent tasks
2004

Sparse LCS Common Substring Alignment
2003

Scheduling tall/small microprocessor tasks with unit processing time to minimize maximum tardiness
2002

Throughput maximization of real-time scheduling with batching
2002

Buffer overflow management in QoS switches
2001

Online server allocation in a server farm via benefit task systems
2001

A unified approach to approximating resource allocation and scheduling
2000

Improved approximations of crossings in graph drawings
2000

Pushing dependent data in clients-providers-servers systems
2000

Resource optimization in QoS multicast routing of real-time multimedia
2000

Approximating the throughput of multiple machines under real-time scheduling
1999

Efficient recovery from power outage
1999

Competitive dynamic bandwidth allocation
1998

Minimizing service and operation costs of periodic scheduling
1998

Multicasting in heterogeneous networks
1998

Fast spreading metric based approximate graph partitioning algorithms
1997

The angular-metric traveling salesman problem
1997

Approximating minimum subset feedback sets in undirected graphs with applications to multicuts
1996

Approximating minimum feedback sets and multi-cuts in directed graphs
1995

Bandwidth allocation with preemption
1995

Divide-and-conquer approximation algorithms via spreading metrics
1995

Finding a minimum weight K-link path in graphs with the concave Monge property
1995

Guaranteeing fair service to persistent dependent tasks
1995

Efficient routing and scheduling algorithms for optical networks
1994

Optimal multiple message broadcasting in telephone-like communication systems
1994

Computing global combine operations in the Multi-Port Postal Model
1993

Fast deflection routing for packets and worms
1993

Finding a minimum weight K-link path in graphs with Monge property and applications
1993

How much can hardware help routing?
1993

A sub-linear space, polynomial time algorithm for directed $s-t$ connectivity
1992

Efficient minimum cost matching using quadrangle inequality
1992

Lower bounds on the depth of monotone arithmetic computations
1992

An efficient algorithm for Suffix-Prefix matching
Springer-Verlag, 1991

Competitive paging with locality of reference
1991

Improved selection in totally monotone arrays
Springer-Verlag, 1991

Navigating in unfamiliar geometric terrain
1991

The Canadian traveler problem
1991

On-line dynamic programming with applications to the prediction of RNA secondary structure
1990

Calling names on nameless networks
1989

Computing external-furthest neighbors for a simple polygon
1989

Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs
1989

Fast approximation techniques and geometric embedding problems
1989

Highly parallelizable problems
1989

Lower bounds for computations with the floor operation
1989

The complexity of approximating the square root
1989

The intractability of bounded protocols for non-FIFO channels
1989

Lower bounds for integer greatest common divisor computations
1988

On finding lowest common ancestors: simplification and parallelization
1988

The power of multimedia: combining point-to-point and multiaccess networks
1988

Parallel construction of a suffix tree
1987

Parallel Ear Decomposition Search (EDS) and $st$-numbering in graphs
Springer-Verlag, 1986

Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings
1986