49 citations · 74 across the 40 of their papers we have counts for
21 papers · 1 filter
DNA Self-Assembly For Constructing 3D Boxes
Ming-Yang Kao, Vijay Ramachandran
We propose a mathematical model of DNA self-assembly using 2D tiles to form 3D nanostructures. This is the first work to combine studies in self-assembly and nanotechnology in 3D,…
Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
Samuel Ieong, Ming-Yang Kao, Tak-Wah Lam +2
The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial…
The Risk Profile Problem for Stock Portfolio Optimization
Ming-Yang Kao, Andreas Nolte, Stephen R. Tate
This work initiates research into the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The pr…
The Enhanced Double Digest Problem for DNA Physical Mapping
Ming-Yang Kao, Jared Samet, Wing-Kin Sung
The double digest problem is a common NP-hard approach to constructing physical maps of DNA sequences. This paper presents a new approach called the enhanced double digest problem.…
Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
Tsan-sheng Hsu, Ming-Yang Kao
A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the s…
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets
Yuyu Chen, Ming-Yang Kao, Hsueh-I Lu
In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special…
Common-Face Embeddings of Planar Graphs
Zhi-Zhong Chen, Xin He, Ming-Yang Kao
Given a planar graph G and a sequence C_1,...,C_q, where each C_i is a family of vertex subsets of G, we wish to find a plane embedding of G, if any exists, such that for each i in…
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses
Richie Chih-Nan Chuang, Ashim Garg, Xin He +2
Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need not be connected or simple (i.e., free of multiple edges). We give three sets of coding schemes for G…
Fast Pricing of European Asian Options with Provable Accuracy: Single-stock and Basket Options
Karhan Akcoglu, Ming-Yang Kao, Shuba Raghavan
This paper develops three polynomial-time pricing techniques for European Asian options with provably small errors, where the stock prices follow binomial trees or trees of higher-…
Data Security Equals Graph Connectivity
Ming-Yang Kao
To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. This paper investigates four levels of data securit…
Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
Xin He, Ming-Yang Kao, Hsueh-I Lu
Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using {4/3}m-1…
Total Protection of Analytic Invariant Information in Cross Tabulated Tables
Ming-Yang Kao
To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. An analytic invariant is a power series in terms of…
Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n^{1.5} log n) time for trees with unbounded degrees, matching the…
Tree Contractions and Evolutionary Trees
Ming-Yang Kao
An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary…
Optimal Constructions of Hybrid Algorithms
Ming-Yang Kao, Yuan Ma, Michael Sipser +1
We study on-line strategies for solving problems with hybrid algorithms. There is a problem Q and w basic algorithms for solving Q. For some lambda <= w, we have a computer with la…
On-Line Difference Maximization
Ming-Yang Kao, Stephen R. Tate
In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving…
A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
Xin He, Ming-Yang Kao, Hsueh-I Lu
We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property pi is called a pi-graph. If pi satisfi…
A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry
Ting Chen, Ming-Yang Kao, Matthew Tepel +2
The tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged prefix and suffix subsequences, and then measures mass/charge ratios of…
An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure is onl…
Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model
James Aspnes, Julia Hartling, Ming-Yang Kao +2
In modern biology, one of the most important research problems is to understand how protein sequences fold into their native 3D structures. To investigate this problem at a high le…
Multiple-Size Divide-and-Conquer Recurrences
Ming-Yang Kao
This short note reports a master theorem on tight asymptotic solutions to divide-and-conquer recurrences with more than one recursive term: for example, T(n) = 1/4 T(n/16) + 1/3 T(…