BSBaruch Schieber
Baruch Schieber
*This is an algorithmically generated author record based on publicly available information.
Research Subjects
Baruch Schieber has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Hadas Shachnai
Computer Science Department, Technion, Haifa, Israel
2 shared publications - Tracy Kimbrel
IBM T.J. Watson Research Center, Yorktown Heights, USA
2 shared publications - Chao Wang
University of Notre Dame
1 shared publication Claudia D’ambrosio
CNRS LIX, École Polytechnique
1 shared publication- Danny Z. Chen
University of Notre Dame
1 shared publication - Don Coppersmith
IDA Center for Communications Research
1 shared publication
Latest Publications
- Open Access
Fully Dynamic Maximal Independent Set with Sublinear Update Time
A maximal independent set (MIS) can be maintained in an evolving $m$-edge graph by simply recomputing it from scratch in $O(m)$ time after each update. But can it be maintained in time sublinear in $m$ in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time $O(\min\{\Delta,m^{3/4}\})$, where $\Delta$ is a fixed bound on the maximum degree in the graph and $m$ is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with $O(\min\{\Delta,m^{3/4}\})$ amortized message complexity, and $O(1)$ amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary.Open AccessFully Dynamic Maximal Independent Set with Sublinear Update Time
A maximal independent set (MIS) can be maintained in an evolving $m$-edge graph by simply recomputing it from scratch in $O(m)$ time after each update. But can it be maintained in time sublinear in $m$ in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time $O(\min\{\Delta,m^{3/4}\})$, where $\Delta$ is a fixed bound on the maximum degree in the graph and $m$ is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with $O(\min\{\Delta,m^{3/4}\})$ amortized message complexity, and $O(1)$ amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary. - Open Access
- 27 December 2017
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 35 (3) , 895-905
Complexity and inapproximability results for the Power Edge Set problem
- 27 December 2017
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 35 (3) , 895-905
Open AccessComplexity and inapproximability results for the Power Edge Set problem
- 19 December 2014
- Published by Springer Nature in Journal of Scheduling
- Vol. 18 (6) , 561-573
Real-time scheduling to minimize machine busy times
- 19 December 2014
- Published by Springer Nature in Journal of Scheduling
- Vol. 18 (6) , 561-573
Real-time scheduling to minimize machine busy times
- 29 August 2009
- Published by Springer Nature in Algorithmica
- Vol. 60 (2) , 421-450
Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy
- 29 August 2009
- Published by Springer Nature in Algorithmica
- Vol. 60 (2) , 421-450
Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy
- 4 July 2007
- Published by Springer Nature in Theory of Computing Systems
- Vol. 42 (1) , 2-26
Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees
- 4 July 2007
- Published by Springer Nature in Theory of Computing Systems
- Vol. 42 (1) , 2-26
Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees
- 1 August 2006
- Published by Springer Nature in Journal of Scheduling
- Vol. 9 (4) , 365-379
Minimizing migrations in fair multiprocessor scheduling of persistent tasks
- 1 August 2006
- Published by Springer Nature in Journal of Scheduling
- Vol. 9 (4) , 365-379
Minimizing migrations in fair multiprocessor scheduling of persistent tasks