Baruch Schieber

Baruch Schieber

Auto-generated profile, based on publicly available information

Baruch Schieber

IBM T.J. Watson Research Center

Research Focus & Metrics

Academic Career Length

21Years (2006-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 December 2014 in Journal of Scheduling
Verified
Journal Article
Closed access
PDF file
RKRohit Khandekar
Rohit Khandekar
BSBaruch Schieber
Baruch Schieber
HSHadas Shachnai
Hadas Shachnai
TTTami Tamir
Tami Tamir

1 August 2006 in Journal of Scheduling
Verified
Journal Article
Closed access
PDF file
TKTracy Kimbrel
Tracy Kimbrel
BSBaruch Schieber
Baruch Schieber
MSMaxim Sviridenko
Maxim Sviridenko

27 December 2017 in Journal of Combinatorial Optimization
Verified
Journal Article
Open access
PDF file
STSonia Toubaline
Sonia Toubaline
CDClaudia D’ambrosio
Claudia D’ambrosio
LLLeo Liberti
Leo Liberti
PPPierre-Louis Poirion
Pierre-Louis Poirion
BSBaruch Schieber
Baruch Schieber
HSHadas Shachnai
Hadas Shachnai
We consider the single channel PMU placement problem called the Power Edge Set problem. In this variant of the PMU placement problem, (single channel) PMUs are placed on the edges of an electrical network. Such a PMU measures the current along the edge on which it is placed and the voltage at its two endpoints. The objective is to find the minimum placement of PMUs in the network that ensures its full observability, namely measurement of all the voltages and currents. We prove that PES is NP-hard to approximate within a factor (1.12)-\(\epsilon \), for any \(\epsilon > 0\). On the positive side we prove that PES problem is solvable in polynomial time for trees and grids.

29 August 2009 in Algorithmica
Verified
Journal Article
Closed access
PDF file
NBNikhil Bansal
Nikhil Bansal
DCDanny Z. Chen
Danny Z. Chen
DCDon Coppersmith
Don Coppersmith
XHXiaobo S. Hu
Xiaobo S. Hu
SLShuang Luan
Shuang Luan
CWChao Wang
Chao Wang

4 July 2007 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
RBRandeep Bhatia
Randeep Bhatia
NINicole Immorlica
Nicole Immorlica
TKTracy Kimbrel
Tracy Kimbrel
VMVahab S. Mirrokni
Vahab S. Mirrokni
JNJoseph (Seffi) Naor
Joseph (Seffi) Naor
BSBaruch Schieber
Baruch Schieber

27 February 2018 in arXiv
Verified
Preprint
Open access
PDF file
SASepehr Assadi
Sepehr Assadi
KOKrzysztof Onak
Krzysztof Onak
BSBaruch Schieber
Baruch Schieber
SSShay Solomon
Shay Solomon
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.