Arrow Research search

Author name cluster

Ming-Yang Kao

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers
2 author rows

Possible papers

25

TCS Journal 2013 Journal Article

Deterministic polynomial-time algorithms for designing short DNA words

  • Ming-Yang Kao
  • Henry C.M. Leung
  • He Sun
  • Yong Zhang

Designing short DNA words is a problem of constructing a set (i. e. , code) of n DNA strings (i. e. , words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e. g. , DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e. g. , 9 ⋅ max { log n, k } ) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e. g. , 2. 1 log n + 6. 28 k ) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. . Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.

Details DOI

TCS Journal 2007 Journal Article

Average case analysis for tree labelling schemes

  • Ming-Yang Kao
  • Xiang-Yang Li
  • Weizhao Wang

We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least 1 8 log 2 n − O ( log n ) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ ( log n ⋅ log ( H n ( T ) ) ), where H n ( T ) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.

Details DOI

TCS Journal 2001 Journal Article

Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees

  • Ming-Yang Kao
  • Jie Wang

The prefix-sum operation, which returns all prefix sums on a sequence of numbers, plays an important role in many applications. We study how to efficiently evaluate prefix sums on positive floating-point numbers such that the worst-case roundoff error of each sum is minimized. A direct approach to this problem builds a Huffman tree for each prefix subsequence from scratch, requiring exactly quadratic time for every input X. We can do better by taking advantage of the current Huffman tree to build the next Huffman tree, using dynamic insertions and deletions on Huffman trees. Consequently, subquadratic time suffices for various input patterns. We also provide experimental comparisons of all the algorithms studied in this paper on inputs that are randomly and uniformly generated.

Details DOI

I&C Journal 1996 Journal Article

Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem

  • Ming-Yang Kao
  • John H. Reif
  • Stephen R. Tate

Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robotics problems, as well as in problems from other areas, we want to charge a cost proportional to the distance between queries (e. g. , the time required to travel between two query points). With this cost function in mind, the abstract problem known as thew-lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem; we give the first randomized algorithm in this paper. We show that our algorithm is optimal for two paths (w=2) and give evidence that it is optimal for larger values ofw. Subsequent to the preliminary version of this paper, Kaoet al. (in“Proceedings, 5th ACM–SIAM Symposium on Discrete Algorithm, ” pp. 372–381, 1994) have shown that our algorithm is indeed optimal for allw⩾2. Our randomized algorithm gives expected performance that is almost twice as good as is possible with a deterministic algorithm. For the performance of our algorithm, we also derive the asymptotic growth with respect tow—despite similar complexity results for related problems, it appears that this growth has never been analyzed.

Details DOI

FOCS Conference 1995 Conference Paper

Load Balancing in the L p Norm

  • Baruch Awerbuch
  • Yossi Azar
  • Edward F. Grove
  • Ming-Yang Kao
  • P. Krishnan
  • Jeffrey Scott Vitter

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L/sub /spl infin// norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than the offline optimal. In many applications, the L/sub /spl infin// norm is not a suitable way to measure how well the jobs are balanced, If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

Details