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...
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...
The Fixed-Hub Single Allocation Problem: A Geometric Rounding Approach (2007)
Dongdong Ge, Yinyu Ye, Jiawei Zhang
This paper discusses the fixed-hub single allocation problem. In the model hubs are fixed and fully connected; and each terminal node is connected to a single hub which routes all its traffic. The...
John Carlsson, Dongdong Ge, Arjun Subramaniam, Amy Wu, Yinyu Ye
The Multi-Depot Vehicle Routing Problem (MDVRP) is a generalization of the Single-Depot Vehicle Routing Problem (SDVRP) in which vehicle(s) start from multiple depots and return to their depots 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...
Improved approximation algorithms for the freeze-tag problem (2003)
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai Hejoseph, S. B. Mitchell
Abstract The following scheduling problem naturally arises in thestudy of swarm robotics. Consider a set of n robots, mod-eled as points in some metric space (e.g., vertices of an edge-weighted...
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...