The Cost of Cache-Oblivious Searching Michael A. Bender (2008)
Gerth Sto/lting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono
zx
Improved Bounds on Sorting by Length-Weighted Reversals ∗ (2008)
Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, ...
We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ) = ℓ α for all α ≥ 0, where ℓ is the...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2008)
Michael A. Bender, Martin Farach-colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson
Abstract — Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the...
ABSTRACT Improved Approximation Algorithms for the Freeze-Tag Problem (2008)
Esther M. Arkin, Simai He, Michael A. Bender, Dongdong Ge
In the Freeze-Tag Problem, the objective is to awaken a set of “asleep ” robots, starting with only one “awake ” robot. A robot awakens a sleeping robot by moving to the sleeping robot’s...
Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization (2007)
He, Simai, Luo, Zhi-Quan, Nie, Jiawang, Zhang, Shuzhong
In this paper we study the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic...
Randomized Portfolio Selection, with Constraints (2007)
Jiang Xie, Simai He, Shuzhong Zhang
In this paper we propose to deal with the combinatorial difficulties in mean-variance portfolio selection, caused by various side constraints, via the randomization approach. As examples of such side...
Simai He, Zhi-quan Luo, Jiawang Nie, Shuzhong Zhang
This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic...
Bounding Probability of Small Deviation: A Fourth Moment Approach (2007)
Simai He, Jiawei Zhang, Shuzhong Zhang
In this paper we study the problem of bounding the value of the probability distribution function of a random variable X at E[X] + a where a is a small quantity in comparison with E[X], by means of...
Sorting by length-weighted reversals: Dealing with signs and circularity (2004)
Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter
Abstract. We consider the problem of sorting linear and circular permutations and 0/1 sequences by reversals in a length-sensitive cost model. We extend the results on sorting by length-weighted...
Improved Bounds on Sorting with Length-Weighted Reversals (Extended Abstract) (2004)
Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, ...
Michael A. Bender y Dongdong Ge Simai He Haodong Hu Ron Y. Pinter Steven Skiena Firas Swidan Abstract We study the problem of sorting integer sequences and permutations by length-weighted reversals....
Sorting by length-weighted reversals: Dealing with signs and circularity (2004)
Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter
Abstract. We consider the problem of sorting linear and circular permutations and 0/1 sequences by reversals in a length-sensitive cost model. We extend the results on sorting by length-weighted...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2003)
Bender, Michael A., Farach-Colton, Martin, He, Simai, Kuszmaul, Bradley C., Leiserson, Charles E.
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2003)
Bender, Michael A., Farach-Colton, Martin, He, Simai, Kuszmaul, Bradley C., Leiserson, Charles E.
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of...
The Cost of Cache-Oblivious Searching (2003)
Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, ...
Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log B N block transfers...
Gerth Stølting Brodal, Michael A. Bender, Dongdong Ge, Simai He, John Iacono (polytechnic, ...
– Cache oblivious model
Improved Approximation Algorithms for the Freeze-Tag Problem
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He
In the Freeze-Tag Problem, the objective is to awaken a set of \asleep" robots, starting with only one \awake" robot. A robot awakens a sleeping robot by moving to the sleeping robot's...