DNA Self-Assembly For Constructing 3D Boxes (Extended Abstract) (2008)
Abstract. 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, just as...
Detecting Stealthy Spreaders Using Online Outdegree Histograms ABSTRACT (2008)
Yan Gao, Yao Zhao, Robert Schweller, Shobha Venkataraman, Yan Chen, Dawn Song, ...
We consider the problem of detecting the presence of a sufficiently large number of hosts that connect to more than a certain number of unique destinations within a given time window, over high-speed...
Using Nash Implementation to Achieve Better Frugality Ratios (2008)
Chien-chung Huang, Ming-yang Kao, Xiang-yang Li, Weizhao Wang
Abstract. Most of the recent works on algorithmic mechanism design exploit the solution concept of dominant strategy equilibria. Such work designs a proper payment scheme so that selfish agents...
Monitoring Flow-level High-speed Data Streams with Reversible Sketches (2008)
Robert Schweller, Zhichun Li, Yan Chen, Yan Gao, Ashish Gupta, Yin Zhang, ...
A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to...
Detecting Stealthy Spreaders Using Online Outdegree Histograms ABSTRACT (2008)
Yan Gao, Yao Zhao, Robert Schweller, Shobha Venkataraman, Yan Chen, Dawn Song, ...
We consider the problem of detecting the presence of a sufficiently large number of hosts that connect to more than a certain number of unique destinations within a given time window, over high-speed...
Detecting Stealthy Spreaders Using Online Outdegree Histograms ABSTRACT (2008)
Yan Gao, Yao Zhao, Robert Schweller, Shobha Venkataraman, Yan Chen, Dawn Song, ...
We consider the problem of detecting the presence of a sufficiently large number of hosts that connect to more than a certain number of unique destinations within a given time window, over high-speed...
Ting Chen, Ming-yang Kao, Matthew Tepel, John Rush, George M. Church
Tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged molecules of prefix and suffix peptide subsequences, and then measures mass/charge ratios of...
An Approximation Algorithm for a Bottleneck Traveling Salesman Problem ∗ (2008)
Consider a truck running along a road. It picks up a load Li at point βi and delivers it at αi, carrying at most one load at a time. The speed on the various parts of the road in one direction is...
Flexible Word Design and Graph Labeling ∗ (2008)
Ming-yang Kao, Manan Sanghi, Robert Schweller
Motivated by emerging applications for DNA code word design, we consider a generalization of the code word design problem in which an input graph is given which must be labeled with equal length...
Reversible Sketches: Enabling Monitoring and Analysis over High-speed Data Streams (2008)
Robert Schweller, Zhichun Li, Yan Chen, Yan Gao, Ashish Gupta, Elliot Parsons, ...
Abstract — A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be...
Flexible Word Design and Graph Labeling ⋆ (2008)
Ming-yang Kao, Manan Sanghi, Robert Schweller
Abstract. Motivated by emerging applications for DNA code word design, we consider a generalization of the code word design problem in which an input graph is given which must be labeled with equal...
Running Head: Searching in an Unknown Environment (2008)
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...
Chapter 8 OPPORTUNITY COST ALGORITHMS FOR COMBINATORIAL AUCTIONS (2008)
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Abstract Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder...
FAST UNIVERSALIZATION OF INVESTMENT STRATEGIES ∗ (2008)
Karhan Akcoglu, Petros Drineas, Ming-yang Kao
Abstract. A universalization of a parameterized investment strategy is an online algorithm whose average daily performance approaches that of the strategy operating with the optimal parameters...
Wu, Gang, Kao, Ming-Yang, Lin, Guohui, You, Jia-Huai
Abstract Background In recent years, quartet-based phylogeny reconstruction methods have received considerable attentions in the computational biology community. Traditionally, the accuracy of a...
On Approximating Four Covering and Packing Problems (2008)
Mary Ashley, Tanya Berger-wolf, Piotr Berman, Wanpracha Chaovalitwongse, Bhaskar Dasgupta, Ming-yang Kao
In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or...
On Approximating Four Covering and Packing Problems (2008)
Mary Ashley, Tanya Berger-wolf, Piotr Berman, Wanpracha Chaovalitwongse, Bhaskar Dasgupta, Ming-yang Kao
In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or...
Reconstructing Evolutionary Trees In A General Markov Model (2007)
. In this paper we study sequence evolution in a general Markov model that incorporates practically every stochastic model used in the literature. In particular, we study the error in the estimation...
. This paper describes a novel algorithm that builds an evolutionary tree with n leaves in O(n 2 log #) time from a distance matrix computed from sample sequences of length #. Our algorithm combines...
Algorithms for Informed Cows (2007)
Ming-yang Kao, Michael L. Littman
We extend the classic on-line search problem known as the cow-path problem to the case in which goal locations are selected according to one of a set of possible known probability distributions. We...
Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder
A preliminary version of this paper appeared in the 2 nd Workshop on Algorithms in Bioinformatics,
URL: www.cs.luc.edu/~mhg (2007)
Michael H. Goldwasser, Ming-yang Kao, Hsueh-i Lu
URL: www.cs.northwestern.edu/~kao
Multi-Domain Sandboxing: An Overview (2007)
Multi-domain S, Boxing An Overview, Robert Fischer, Robert Fischer, Ming-yang Kao, Ming-yang Kao
In today's computing world, computer code is most often developed on one computer and run on another. Code is increasingly downloaded and run on a casual basis, as the line between code and data...
James Aspnes, Julia Hartling, Ming-yang Kao, Junhyong Kim, Gauri Shah
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 level, one wishes to...
James Aspnes, David F. Fischer, Michael J. Fischer, Ming-yang Kao
This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the...
Ming-yang Kao, Tak-wah Lam, Teresa M. Przytycka, Hing-fung Ting
This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming...
James Aspnes, David F. Fischer, Michael J. Fischer, Ming-yang Kao
This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agentbased model for a stock market where the...
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
1 Supported in part by NSF Grant CCR-9896165. 2
Anja Feldmann, Ming-yang Kao, Shang-hua Teng
We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific...
Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search (2007)
Piotr Berman, Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder
In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to find a set of tiles such that they...
On Constructing An Optimal Consensus Clustering from Multiple Clusterings (2007)
Piotr Berman, Bhaskar Dasgupta, Ming-yang Kao, Jie Wang
Computing a suitable measure of consensus among several clusterings on the same data is an important problem that arises in several areas such as computational biology and data mining. In this paper,...
Reducing Tile Complexity for Self-Assembly Through Temperature Programming (2006)
Kao, Ming-Yang, Schweller, Robert
We consider the tile self-assembly model and how tile complexity can be eliminated by permitting the temperature of the self-assembly system to be adjusted throughout the assembly process. To do...
Randomized Fast Design of Short DNA Words (2006)
Kao, Ming-Yang, Sanghi, Manan, Schweller, Robert
We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA...
Linear-Time Haplotype Inference on Pedigrees without Recombinations (2006)
M. Y. Chan, Wun-tat Chan, Ming-yang Kao
Abstract. In this paper, a linear-time algorithm, which is optimal, is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no...
James Aspnes, Julia Hartling, Ming-yang Kao, Junhyong Kim, Gauri Shah
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 level, one wishes to...
Zhichun Li, Manan Sanghi, Yan Chen, Ming-yang Kao, Brian Chavez
Zero-day polymorphic worms pose a serious threat to the security of Internet infrastructures. Given their rapid propagation, it is crucial to detect them at edge networks and automatically generate...
Design optimization methods for genomic DNA tiling arrays (2006)
Paul Bertone, Valery Trifonov, Joel S. Rozowsky, Falk Schubert, Olof Emanuelsson, John Karro, ...
A recent development in microarray construction entails the unbiased coverage, or tiling, of non-repetitive genomic DNA for the experimental identification of unannotated transcribed sequences and...
Randomized fast design of short dna words (2005)
Ming-yang Kao, Manan Sanghi, Robert Schweller
Abstract. We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations...
Tight approximability results for test set problems in bioinformatics (2005)
Piotr Berman, Bhaskar Dasgupta, Ming-yang Kao
Abstract. In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished ” by...
Tight approximability results for test set problems in bioinformatics (2005)
Piotr Berman, Bhaskar Dasgupta, Ming-yang Kao
In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished ” by a family...
Towards truthful mechanisms for binary demand games: a general framework (2005)
The family of Vickrey-Clarke-Groves (VCG) mechanisms is arguably the most celebrated achievement in truthful mechanism design. However, VCG mechanisms have their limitations. They only apply to...
Average Case Analysis for Tree Labelling Schemes (2005)
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. For trees, Gavoille et al. [7] proved that for any such...
Design optimization methods for genomic DNA tiling arrays (2005)
Bertone, Paul, Trifonov, Valery, Rozowsky, Joel S., Schubert, Falk, Emanuelsson, Olof, Karro, John, ...
A recent development in microarray research entails the unbiased coverage, or tiling, of genomic DNA for the large-scale identification of transcribed sequences and regulatory elements. A central...
Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications (2004)
Robert Schweller, Zhichun Li, Yan Chen, Yan Gao, Ashish Gupta, Yin Zhang, ...
A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to...
Complexities for generalized models of self-assembly (2004)
Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-yang Kao, Pablo Moisset, De Espanes, ...
Abstract. In this paper, we study the complexity of self-assembly under models that are natural generalizations of the tile self-assembly model. In particular, we extend Rothemund and Winfree’s...
Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications (2004)
Robert Schweller, Zhichun Li, Yan Chen, Yan Gao, Ashish Gupta, Yin Zhang, ...
A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to...
Complexities for generalized models of self-assembly (2004)
Gagan Aggarwal, Michael H. Goldwasser, Ming-yang Kao, Robert T. Schweller
In this paper, we extend Rothemund and Winfree’s examination of the tile complexity of tile self-assembly [6]. log N They provided a lower bound of Ω ( log log N) on the tile complexity of...
Hon, Wing-Kai, Kao, Ming-Yang, Lam, Tak-Wah, Sung, Wing-Kin, Yiu, Siu-Ming
The number of the non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edges are also the building block for approximating a more...
Goldwasser, Michael H., Kao, Ming-Yang, Lu, Hsueh-I
We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (a_i,w_i) for i = 1,..,n and w_i>0, a segment A(i,j) is a consecutive subsequence of A...
Fast Universalization of Investment Strategies with Provably Good Relative Returns (2002)
Akcoglu, Karhan, Drineas, Petros, Kao, Ming-Yang
A universalization of a parameterized investment strategy is an online algorithm whose average daily performance approaches that of the strategy operating with the optimal parameters determined...
Opportunity cost algorithms for combinatorial auctions (2002)
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Two general algorithms based on opportunity costs are given for approximating a revenuemaximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder oers a price...
Opportunity cost algorithms for combinatorial auctions (2002)
James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Abstract Two general algorithms based on opportunity costs are given for approximating a revenuemaximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder...
Fast optimal genome tiling with applications to microarray design and homology search (2002)
Piotr Berman, Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder
In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to find a set of tiles of maximum total...
Fast optimal genome tiling with applications to microarray design and homology search (2002)
Piotr Berman, Paul Bertone, Bhaskar Dasgupta, Mark Gerstein, Ming-yang Kao, Michael Snyder, ...
Abstract. In this paper we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size bound parameters, we want to nd a set of tiles such that...
DNA Self-Assembly For Constructing 3D Boxes (2001)
Kao, Ming-Yang, Ramachandran, Vijay
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, just as Rothemund...
Ieong, Samuel, Kao, Ming-Yang, Lam, Tak-Wah, Sung, Wing-Kin, Yiu, Siu-Ming
The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms...
The Risk Profile Problem for Stock Portfolio Optimization (2001)
Kao, Ming-Yang, Nolte, Andreas, Tate, Stephen R.
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 probability...
The Enhanced Double Digest Problem for DNA Physical Mapping (2001)
Kao, Ming-Yang, Samet, Jared, Sung, Wing-Kin
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. Although this new...
Common-Face Embeddings of Planar Graphs (2001)
Chen, Zhi-Zhong, He, Xin, Kao, Ming-Yang
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 {1,...,q}, there...
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets (2001)
Chen, Yuyu, Kao, Ming-Yang, Lu, Hsueh-I
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 class of...
Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time (2001)
Hsu, Tsan-sheng, Kao, Ming-Yang
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 smallest number of...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (2001)
Chuang, Richie Chih-Nan, Garg, Ashim, He, Xin, Kao, Ming-Yang, Lu, Hsueh-I
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 which all take...
Akcoglu, Karhan, Kao, Ming-Yang, Raghavan, Shuba
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-degree. The first...
Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings (2001)
He, Xin, Kao, Ming-Yang, Lu, Hsueh-I
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 bits, improving on...
Data Security Equals Graph Connectivity (2001)
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 security of a...
Tree Contractions and Evolutionary Trees (2001)
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 trees are useful...
Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees (2001)
Kao, Ming-Yang, Lam, Tak-Wah, Sung, Wing-Kin, Ting, Hing-Fung
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 best known time...
Total Protection of Analytic Invariant Information in Cross Tabulated Tables (2001)
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 the suppressed...
Optimal Constructions of Hybrid Algorithms (2001)
Kao, Ming-Yang, Ma, Yuan, Sipser, Michael, Yin, Yiqun
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
On-Line Difference Maximization (2001)
Kao, Ming-Yang, Tate, Stephen R.
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 in random order,...
A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs (2001)
He, Xin, Kao, Ming-Yang, Lu, Hsueh-I
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 satisfies certain...
Aspnes, James, Hartling, Julia, Kao, Ming-Yang, Kim, Junhyong, Shah, Gauri
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 level, one wishes to...
A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry (2001)
Chen, Ting, Kao, Ming-Yang, Tepel, Matthew, Rush, John, Church, George M.
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 these ions. The de...
Multiple-Size Divide-and-Conquer Recurrences (2001)
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(3n/5) + 4 T(n/100)...
Kao, Ming-Yang, Lam, Tak-Wah, Sung, Wing-Kin, Ting, Hing-Fung
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 only concerned with...
A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry (2001)
Ting Chen, Ming-yang Kao, Matthew Tepel, John Rush, George M. Church
Tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged molecules of pre � x and suf � x peptide subsequences and then measures mass/charge ratios...
MIRACLE: A Music Information Retrieval System with Clustered Computing Engines (2001)
Jiang-chun Chen, Ming-yang Kao
This paper presents a music information retrieval system based on parallel and distributed computing. The system, called MIRACLE (Music Information Retrieval Acoustically with Clustered and paralleL...
DNA Self-Assembly For Constructing 3D Boxes (2001)
Abstract. 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, just as...
DNA Self-Assembly For Constructing 3D Boxes (2001)
Abstract. 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, just as...
Provably Fast and Accurate Recovery of Evolutionary Trees through Harmonic Greedy Triplets (2000)
Csuros, Miklos, Kao, Ming-Yang
We give a greedy learning algorithm for reconstructing an evolutionary tree based on a certain harmonic average on triplets of terminal taxa. After the pairwise distances between terminal taxa are...
Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions (2000)
Kao, Ming-Yang, Qi, Junfeng, Tan, Lei
This paper studies some basic problems in a multiple-object auction model using methodologies from theoretical computer science. We are especially concerned with situations where an adversary bidder...
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns (2000)
Chen, Gen-Huey, Kao, Ming-Yang, Lyuu, Yuh-Dauh, Wong, Hsing-Kuo
In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to investigate...
Designing Proxies for Stock Market Indices is Computationally Hard (2000)
Kao, Ming-Yang, Tate, Stephen R.
In this paper, we study the problem of designing proxies (or portfolios) for various stock market indices based on historical data. We use four different methods for computing market indices, all of...
A Decomposition Theorem for Maximum Weight Bipartite Matchings (2000)
Kao, Ming-Yang, Lam, Tak-Wah, Sung, Wing-Kin, Ting, Hing-Fung
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N and W be the node count, the largest edge weight and the total weight of G. Let k(x,y) be...
Opportunity Cost Algorithms for Combinatorial Auctions (2000)
Akcoglu, Karhan, Aspnes, James, DasGupta, Bhaskar, Kao, Ming-Yang
Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a...
Aspnes, James, Fischer, David F., Fischer, Michael J., Kao, Ming-Yang, Kumar, Alok
This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the...
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets (2000)
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 class of...
Opportunity Cost Algorithms for Combinatorial Auctions (2000)
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Two general algorithms based on opportunity costs are given for approximating a revenue maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a...
T. Chen, Ting Chen, Ming-yang Kao, Matthew Tepel, John Rush, George M. Church
) Ting Chen Ming-Yang Kao y Matthew Tepel z John Rush x George M. Church -- Abstract The tandem mass spectrometry fragments molecules of the same peptide sequence into charged prefix and suffix...
Given a multiset $X=\{x_1,..., x_n\}$ of real numbers, the {\it floating-point set summation} problem asks for $S_n=x_1+...+x_n$. Let $E^*_n$ denote the minimum worst-case error over all possible...
Reducing Randomness via Irrational Numbers (1999)
Chen, Zhi-Zhong, Kao, Ming-Yang
We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable...
Linear-time succinct encodings of planar graphs via canonical orderings (1999)
Xin He, Ming-yang Kao, Hsueh-i Lu
Abstract. 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 m − 1 bits,...
Abstract. Given a multiset X = {x1,..., xn} of real numbers, the floating-point set summation problem asks for Sn = x1 + · · · + xn. Let E ∗ n denote the minimum worst-case error over all...
Balanced randomized tree splitting with applications to evolutionary tree constructions (1999)
Ming-yang Kao, Andrzej Lingas, Anna Ostlin
Abstract. We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on e#cient...
H.K.: Optimal buy-and-hold strategies for financial markets with bounded daily returns (1999)
Gen-huey Chen, Ming-yang Kao, Yuh-dauh Lyuu, Hsing-kuo Wong
A general solution is presented for any finite requestanswer game to derive its optimal competitive ratio and optimal randomized on-line algorithm against the oblivious adversary. The solution is...
A Fast General Methodology For Information-Theoretically Optimal Encodings Of Graphs (1999)
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 is called a -graph. If satisfies certain properties,...
Recovering Evolutionary Trees Through Harmonic Greedy Triplets (Extended Abstract) (1999)
. We give a greedy learning algorithm for reconstructing an evolutionary tree based on a harmonic average on triplets of taxa. This algorithm runs in polynomial time in the input size. Using the...
Lower Bounds on Sequence Lengths Required to Recover the Evolutionary Tree (Extended Abstract (1999)
. In this paper we study the sequence length requirements of distance-based evolutionary tree building algorithms in the Jukes-Cantor model of evolution. By deriving lower bounds on sequence lengths...
. This paper addresses the informational asymmetry for constructing an ultrametric evolutionary tree from upper and lower bounds on pairwise distances between n given species. We show that the...
On-line difference maximization (1999)
Abstract. 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 in...
The Risk Profile Problem for Stock Portfolio Optimization (1999)
Ming-yang Kao, Andreas Nolte, Stephen R. Tate
In this paper we study the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The probability distribution of the...
H.K.: Optimal buy-and-hold strategies for financial markets with bounded daily returns (1999)
Gen-huey Chen, Ming-yang Kao, Yuh-dauh Lyuu, Hsing-kuo Wong
Abstract. In the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. We then use the tools to...
Balanced randomized tree splitting with applications to evolutionary tree constructions (1999)
Ming-yang Kao, Andrzej Lingas, Anna Östlin
Abstract. We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on efficient...
Fast Recovery of Evolutionary Trees through Harmonic Greedy Triplets (1998)
We give a greedy learning algorithm for reconstructing an evolutionary tree based on a harmonic average on triplets of terminal taxa. After the pairwise distances between terminal taxa are computed,...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (1998)
Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-i Lu
. We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all...
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (1998)
ASHIM GARG, XIN HE, MING-YANG KAO, Hsueh-i Lu
. 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 which all take...
Optimal On-line Scheduling of Parallel Jobs with Dependencies (1998)
Anja Feldmann, Ming-yang Kao, Jirí Sgall, Shang-Hua Teng
We study the following general on-line scheduling problem. Parallel jobs arrive on a parallel machine dynamically according to the dependencies between them. Each job requests a certain number of...
Optimal on-line scheduling of parallel jobs with dependencies (1998)
Anja Feldmann, Ming-yang Kao, Shang-hua Teng
Abstract We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a...
Reducing Randomness Via Irrational Numbers (1997)
. We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable...
Ming-yang Kao, Stephen R. Tate
In this paper, we examine the problem of “blocked online bipartite matching”. This problem is similar to the online matching problem except that the vertices arrive in blocks instead of one at a...
Optimal Bi-Level Augmentation for Selectively Enhancing Graph Connectivity with Applications (1996)
Our main problem is abstracted from several optimization problems for protecting information in cross tabulated tables and for improving the reliability of communication networks. Given an undirected...
Optimal Augmentation For Bipartite Componentwise Biconnectivity In Linear Time (1996)
. A graph is componentwise fully biconnected if every connected component either is an isolated vertex or is biconnected. We consider the problem of adding the smallest number of edges to make a...
Regular Edge Labelings and Drawings of Planar Graphs (1995)
The problems of nicely drawing planar graphs have received increasing attention due to their broad applications [5]. A technique, regular edge labeling, was successfully used in solving several...
Regular Edge Labelings and Drawings of Planar Graphs (1995)
The problems of nicely drawing planar graphs have received increasing attention due to their broad applications [5]. A technique, regular edge labeling, was successfully used in solving several...
Regular Edge Labelings and Drawings of Planar Graphs (1995)
The problems of nicely drawing planar graphs have received increasing attention due to their broad applications [5]. A technique, regular edge labeling, was successfully used in solving several...
Load balancing in the L_p norm (1995)
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....
Load balancing in the L_p norm (1995)
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....
Online Perfect Matching and Mobile Computing (1995)
Edward Grove, Ming-yang Kao, P. Krishnan, Jeffrey Scott Vitter
. We present a natural online perfect matching problem motivated by problems in mobile computing. A total of n customers connect and disconnect sequentially, and each customer has an associated set...
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....
Online perfect matching and mobile computing (1995)
Edward F. Grove, Ming-yang Kao, P. Krishnan
Abstract. We present a natural online perfect matching problem motivated by problems in mobile computing. A total of n customers connect and disconnect sequentially, and each customer has an...
Online Matching with Blocked Input (1994)
Ming-yang Kao, Stephen R. Tate
In this paper, we examine the problem of "blocked online bipartite matching". This problem is similar to the online matching problem except that the vertices arrive in blocks instead of one...
Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem (1993)
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...
Optimal Online Scheduling of Parallel Jobs with Dependencies (1993)
We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific...
Ming-yang Kao, Andreas Nolte, Stephen R. Tate
In this paper we study the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The probability distribution of the...
Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem (1992)
Ming-yang Kao, Ming-yang Kao, John H. Reif, John H. Reif, Stephen R. Tate, 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...
Planar Strong Connectivity Helps in Parallel Depth-First Search (1992)
. This paper shows that for a strongly connected planar directed graph of size n, a depth-first search tree rooted a specified vertex can be computed in O(log 5 n) time using n= log n processors....
Design optimization methods for genomic DNA tiling arrays
Bertone, Paul, Trifonov, Valery, Rozowsky, Joel S., Schubert, Falk, Emanuelsson, Olof, Karro, John, ...
A recent development in microarray research entails the unbiased coverage, or tiling, of genomic DNA for the large-scale identification of transcribed sequences and regulatory elements. A central...
Design optimization methods for genomic DNA tiling arrays
Bertone, Paul, Trifonov, Valery, Rozowsky, Joel S., Schubert, Falk, Emanuelsson, Olof, Karro, John, ...
A recent development in microarray research entails the unbiased coverage, or tiling, of genomic DNA for the large-scale identification of transcribed sequences and regulatory elements. A central...