Baruch Schieber

D. Katz, Baruch M. Schieber, H. Shachnai. 2019. “Flexible Resource Allocation to Interval Jobs.” Algorithmica, vol. 81, pp. 3217--3244.

Baruch M. Schieber, H. Shachnai, G. Tamir, T. Tamir. 2018. “A Theory and Algorithms for Combinatorial Reoptimization.” Algorithmica, vol. 80, pp. 576--607.

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

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

R. Khandekar, Baruch M. Schieber, H. Shachnai, T. Tamir. 2015. “Real-time Scheduling to Minimize Machine Busy Times.” Journal of Scheduling, vol. 18, pp. 561--573.

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

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

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

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

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

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

T. Kimbrel, Baruch M. Schieber, M. Sviridenko. 2006. “Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks.” Journal of Scheduling, vol. 9, pp. 365--379.

O. Gunluk, T. Kimbrel, L. Ladanyi, Baruch M. Schieber, G. Sorkin. 2006. “Vehicle routing and staffing for sedan service.” Transportation Science, vol. 40, pp. 313--326.

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

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

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

G. Even, S. Guha, Baruch M. Schieber. 2003. “Improved approximations of crossings in graph drawings.” SIAM Journal on Computing, vol. 32, pp. 231--252.

A. Bar-Noy, J. Naor, Baruch M. Schieber. 2003. “Publishing dependent data in clients-providers-servers systems.” Wireless Networks, vol. 9, pp. 421--430.

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

G.M. Landau, Baruch M. Schieber, M. Ziv-Ukelson. 2003. “Sparse LCS Common Substring Alignment.” Information Processing Letters, vol. 88, pp. 259--270.

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

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

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

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

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

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

A. Bar-Noy, S. Guha, J. Naor, Baruch M. Schieber. 2000. “Message multicasting in heterogeneous networks.” SIAM Journal on Computing, vol. 30, pp. 347--358.

A. Bar-Noy, S. Kipnis, Baruch M. Schieber. 2000. “Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems.” Discrete Applied Mathematics, vol. 100, pp. 1--15.

G. Even, J. Naor, S. Rao, Baruch M. Schieber. 1999. “Approximate Graph Partitioning Algorithms.” SIAM Journal on Computing, vol. 28, pp. 2187--2214.

A. Bar-Noy, R. Canetti, S. Kutten, Y. Mansour, Baruch M. Schieber. 1999. “Bandwidth allocation with preemption.” SIAM Journal on Computing, vol. 28, pp. 1806--1828.

D. Coppersmith, Baruch M. Schieber. 1999. “Lower bounds on the depth of monotone arithmetic computations.” Journal of Complexity, vol. 15, pp. 17--29.

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

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

G. Even, J. Naor, Baruch M. Schieber, M. Sudan. 1998. “Approximating minimum feedback sets and multi-cuts in directed graphs.” Algorithmica, vol. 20, pp. 151--174.

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

A. Bar-Noy, A. Mayer, Baruch M. Schieber, M. Sudan. 1998. “Guaranteeing fair service to persistent dependent tasks.” SIAM Journal on Computing, vol. 24, pp. 1168--1189.

L. Cai, Baruch M. Schieber. 1997. “A linear-time algorithm for computing the intersection of all odd cycles in a graph.” Discrete Applied Mathematics, vol. 73, no. 1, pp. 27--34.

N. Bshouty, Y. Mansour, Baruch M. Schieber, P. Tiwari. 1997. “A tight bound for approximating the square root.” Information Processing Letters, vol. 63, pp. 211--213.

A. Borodin, Y. Rabani, Baruch M. Schieber. 1997. “Deterministic many-to-many hot potato routing.” IEEE Trans. on Parallel and Distributed Systems, vol. 8, no. 6, pp. 587--596.

A. Borodin, P. Raghavan, Baruch M. Schieber, E. Upfal. 1997. “How much can hardware help routing?.” Journal of the ACM, vol. 44, no. 5, pp. 726--741.

A. Blum, P. Raghavan, Baruch M. Schieber. 1997. “Navigating in unfamiliar geometric terrain.” SIAM Journal on Computing, vol. 26, no. 1, pp. 110--137.

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

A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, Baruch M. Schieber, M. Sudan. 1996. “Efficient routing in optical networks.” Journal of the ACM, vol. 43, no. 6, pp. 973--1001.

A. Borodin, S. Irani, P. Raghavan, Baruch M. Schieber. 1995. “Competitive paging with locality of reference.” Journal of Computer and System Sciences, vol. 50, pp. 244--258.

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

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

A. Bar-Noy, S. Kipnis, Baruch M. Schieber. 1995. “Optimal computation of census functions in the Postal Model.” Discrete Applied Mathematics, vol. 58, pp. 213--222.

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

Baruch M. Schieber, M. Snir. 1994. “Calling names on nameless networks.” Information and Computation, vol. 113, pp. 80--101.

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

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

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

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

D. Gusfield, G.M. Landau, Baruch M. Schieber. 1992. “An efficient algorithm for the all pairs Suffix-Prefix problem.” Information Processing Letters, vol. 41, pp. 181--185.

M.W. Bern, H.J. Karloff, P. Raghavan, Baruch M. Schieber. 1992. “Fast approximation techniques and geometric embedding problems.” Theoretical Computer Science, vol. 106, pp. 265--281.

N.H. Bshouty, Y. Mansour, Baruch M. Schieber, P. Tiwari. 1992. “Fast exponentiation using the truncation operation.” Computational Complexity, vol. 2, pp. 244--255.

S. Khuller, Baruch M. Schieber. 1992. “On independent spanning trees.” Information Processing Letters, vol. 42, pp. 321--323.

Y. Mansour, Baruch M. Schieber. 1992. “The intractability of bounded protocols for non-FIFO channels.” Journal of the ACM, vol. 39, pp. 783--799.

Y. Mansour, Baruch M. Schieber, P. Tiwari. 1991. “A lower bound for integer greatest common divisor computations.” Journal of the ACM, vol. 38, pp. 453--471.

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

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

Y. Mansour, Baruch M. Schieber, P. Tiwari. 1991. “Lower bounds for computations with the floor operation.” SIAM Journal on Computing, vol. 20, pp. 315--327.

L.L. Larmore, Baruch M. Schieber. 1991. “On-line dynamic programming with applications to the prediction of RNA secondary structure.” Journal of Algorithms, vol. 12, pp. 490--515.

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

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

Y. Mansour, Baruch M. Schieber. 1989. “Finding the edge connectivity of directed graphs.” Journal of Algorithms, vol. 10, pp. 76--85.

Baruch M. Schieber, S. Moran. 1989. “Parallel algorithms for maximum bipartite matchings and maximum $0-1$ flows.” Journal of Parallel and Distributed Computing, vol. 6, pp. 20--38.

Baruch M. Schieber, U. Vishkin. 1988. “On finding lowest common ancestors: simplification and parallelization.” SIAM Journal on Computing, vol. 17, pp. 1253--1262.

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

A. Apostolico, C. Iliopoulos, G.M. Landau, Baruch M. Schieber, U. Vishkin. 1988. “Parallel construction of a suffix tree with applications.” Algorithmica, vol. 3, pp. 347--365.

Y. Maon, Baruch M. Schieber, U. Vishkin. 1986. “Parallel Ear Decomposition Search (EDS) and st-numbering in graphs.” Theoretical Computer Science, vol. 47, pp. 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.