If you made any changes in Pure, your changes will be visible here soon.

Research Output 1988 2017

2005
103 Citations (Scopus)

Complexities for generalized models of self-assembly

Aggarwal, G., Cheng, Q. I., Goldwasser, M. H., Kao, M-Y., De Espanes, P. M. & Schweller, R. T., Dec 1 2005, In : SIAM Journal on Computing. 34, 6, p. 1493-1515 23 p.

Research output: Contribution to journalArticle

Self-assembly
Tile
Self assembly
Lower bound
Glues
5 Citations (Scopus)

Fast universalisation of investment strategies

Akcoglu, K., Drineas, P. & Kao, M-Y., Apr 15 2005, In : SIAM Journal on Computing. 34, 1, p. 1-22 22 p.

Research output: Contribution to journalArticle

Approximation algorithms
Beaches
Computer science
Trading Strategies
Universal Cover
34 Citations (Scopus)

Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

Goldwasser, M. H., Kao, M-Y. & Lu, H. I., Mar 1 2005, In : Journal of Computer and System Sciences. 70, 2, p. 128-144 17 p.

Research output: Contribution to journalArticle

Bioinformatics
Linear-time Algorithm
Computing
Sequence Analysis
Subsequence
4 Citations (Scopus)

Optimal augmentation for bipartite componentwise biconnectivity in linear time

Hsu, T. S. & Kao, M-Y., Dec 1 2005, In : SIAM Journal on Discrete Mathematics. 19, 2, p. 345-362 18 p.

Research output: Contribution to journalArticle

Augmentation
Linear-time Algorithm
Connected Components
Bipartite Graph
Tables
6 Citations (Scopus)

Randomized fast design of short DNA words

Kao, M-Y., Sanghi, M. & Schweller, R., Oct 19 2005, In : Lecture Notes in Computer Science. 3580, p. 1275-1286 12 p.

Research output: Contribution to journalConference article

DNA
Strings
DNA Computing
Coding Theory
Local Search Algorithm
23 Citations (Scopus)

Tight approximability results for test set problems in bioinformatics

Berman, P., DasGupta, B. & Kao, M-Y., Aug 1 2005, In : Journal of Computer and System Sciences. 71, 2, p. 145-162 18 p.

Research output: Contribution to journalArticle

Approximability
Test Set
Bioinformatics
DNA sequences
Coloring
22 Citations (Scopus)

Towards truthful mechanisms for binary demand games: A general framework

Kao, M-Y., Li, X. Y. & Wang, W., Dec 1 2005, p. 213-222. 10 p.

Research output: Contribution to conferencePaper

Polynomials
Chemical analysis
2004
33 Citations (Scopus)

Complexities for Generalized Models of Self-Assembly

Aggarwal, G., Goldwasser, M. H., Kao, M-Y. & Schweller, R. T., Apr 15 2004, p. 873-882. 10 p.

Research output: Contribution to conferencePaper

Self-assembly
Tile
Self assembly
Lower bound
Glues
10 Citations (Scopus)

Fast optimal genome tiling with applications to microarray design and homology search

Herman, P., Bertone, P., Dasgupta, B., Gerstein, M., Kao, M-Y. & Snyder, M., Sep 28 2004, In : Journal of Computational Biology. 11, 4, p. 766-785 20 p.

Research output: Contribution to journalArticle

Microarrays
Tile
Tiling
Microarray
Homology
2 Citations (Scopus)

Non-shared edges and nearest neighbor interchanges revisited

Hon, W. K., Kao, M-Y., Lam, T. W., Sung, W. K. & Yiu, S. M., Aug 16 2004, In : Information Processing Letters. 91, 3, p. 129-134 6 p.

Research output: Contribution to journalArticle

Interchanges
Nearest Neighbor
Phylogeny
Approximation algorithms
Dissimilarity

Subtree Transfer Distance for Degree-d Phylogenies

Hon, W. K., Kao, M. Y. & Lam, T. W., 2004, In : International Journal of Foundations of Computer Science. 15, p. 893-909

Research output: Contribution to journalArticle

5 Citations (Scopus)
Approximability
Test Set
Bioinformatics
DNA sequences
Coloring
2003
1 Citation (Scopus)

Common-face embeddings of planar graphs

Chen, Z. Z., He, X. & Kao, M-Y., Feb 1 2003, In : SIAM Journal on Computing. 32, 2, p. 408-434 27 p.

Research output: Contribution to journalArticle

Planar graph
Computational complexity
Face
Recovery
Processing

Foreword

Hwang, J. K., Kao, M-Y., Sun, C. T. & Hsu, W. L., Nov 1 2003, In : Journal of Information Science and Engineering. 19, 6

Research output: Contribution to journalEditorial

Biotechnology
Information management
Computer science
Data mining
Data reduction
45 Citations (Scopus)

Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs

Ieong, S., Kao, M-Y., Lam, T. W., Sung, W. K. & Yiu, S. M., Dec 1 2003, In : Journal of Computational Biology. 10, 6, p. 981-995 15 p.

Research output: Contribution to journalArticle

RNA Secondary Structure
Stacking
Secondary Structure
RNA
Approximation algorithms
2 Citations (Scopus)

The enhanced double digest problem for DNA physical mapping

Kao, M. Y., Samet, J. & Sung, W. K., Mar 1 2003, In : Journal of Combinatorial Optimization. 7, 1, p. 69-78 10 p.

Research output: Contribution to journalArticle

DNA sequences
DNA
NP-complete problem
DNA Sequence
Linear Time
2002
1 Citation (Scopus)

A combinatorial toolbox for protein sequence design and landscape analysis in the grand canonical model

Aspnes, J., Hartling, J., Kao, M-Y., Kim, J. & Shah, G., Dec 1 2002, In : Journal of Computational Biology. 9, 5, p. 721-741 21 p.

Research output: Contribution to journalArticle

Canonical Model
Protein Sequence
Proteins
Network Flow
Protein
15 Citations (Scopus)

Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics

Goldwasser, M. H., Kao, M-Y. & Lu, H. I., Jan 1 2002, Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. Guigo, R. & Gusfield, D. (eds.). Springer Verlag, p. 157-171 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2452).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bioinformatics
Fast Algorithm
Sequence Analysis
Subsequence
Consecutive
3 Citations (Scopus)

Fast optimal genome tiling with applications to microarray design and homology search

Berman, P., Bertone, P., DasGupta, B., Gerstein, M., Kao, M-Y. & Snyder, M., Jan 1 2002, Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. Guigo, R. & Gusfield, D. (eds.). Springer Verlag, p. 419-433 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2452).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Microarrays
Tile
Tiling
Microarray
Homology
3 Citations (Scopus)

Fast universalization of investment strategies with provably good relative returns

Akcoglu, K., Drineas, P. & Kao, M-Y., Dec 1 2002, Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. p. 888-900 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2380 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Trading Strategies
Universal Cover
Log-concave
Concave function
Exponential time

Opportunity Cost Algorithms for Combinatorial Auctions: Computational Methods in Decision-Making, Economics, and Finance

Kao, M-Y., 2002, Applied Optimization #74: Computational Methods in Decision-Making, Economics, and Finance. Springer, p. 455-479

Research output: Chapter in Book/Report/Conference proceedingChapter

The Risk Profile Problem for Stock Portfolio Optimization: Computational Methods in Decision-Making, Economics, and Finance

Kao, M-Y., 2002, Applied Optimization #74: Computational Methods in Decision-Making, Economics, and Finance. Springer, p. 213-230

Research output: Chapter in Book/Report/Conference proceedingChapter

2001

A combinatorial toolbox for protein sequence design and landscape analysis in the grand canonical model

Aspnes, J., Hartling, J., Ming-Yang, K., Kim, J. & Shah, G., Dec 1 2001, Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. p. 403-415 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2223 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Canonical Model
Protein Sequence
Proteins
Network Flow
Protein
38 Citations (Scopus)

A decomposition theorem for maximum weight bipartite matchings

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2001, In : SIAM Journal on Computing. 31, 1, p. 18-26 9 p.

Research output: Contribution to journalArticle

Bipartite Matching
Decomposition Theorem
Decomposition
Computing
Vertex of a graph
187 Citations (Scopus)

A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry

Chen, T., Tepel, M., Rush, J., Church, G. M. & Kao, M. Y., Jan 1 2001, In : Journal of Computational Biology. 8, 3, p. 325-337 13 p.

Research output: Contribution to journalArticle

Mass Spectrometry
Tandem Mass Spectrometry
Dynamic programming
Peptides
Sequencing
43 Citations (Scopus)

An even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2001, In : Journal of Algorithms. 40, 2, p. 212-233 22 p.

Research output: Contribution to journalArticle

Bipartite Matching
Labeled Trees
Matching Problem
Leaves
Evolutionary Tree

Designing proxies for stock market indices is computationally hard

Kao, M-Y. & Tate, S. R., 2001, In : Quantitative Finance. 1, p. 361-371

Research output: Contribution to journalArticle

Stock market index
Market index
Relative prices
Margin
Stock market
14 Citations (Scopus)

DNA self-assembly for constructing 3D boxes (Extended Abstract)

Kao, M-Y. & Ramachandran, V., Dec 1 2001, Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. p. 429-441 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2223 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Self-assembly
Self assembly
DNA
Tile
Nanostructures
6 Citations (Scopus)

Fast pricing of European Asian options with provable accuracy: Single-stock and basket options?

Akcoglu, K., Kao, M. Y. & Raghavan, S. V., Jan 1 2001, Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings. Springer Verlag, p. 404-415 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2161).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Asian Options
European Options
Pricing
Polynomials
Costs

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

Kao, M. Y. & Wang, J., Aug 2 2001, In : Theoretical Computer Science. 262, 1-2, p. 101-115 15 p.

Research output: Contribution to journalArticle

Rounding error
Prefix
Worst Case Error
Floating point
Subsequence
26 Citations (Scopus)

Optimal buy-and-hold strategies for financial markets with bounded daily returns

Chen, G. H., Kao, M. Y., Lyuu, Y. D. & Wong, H. K., Jan 1 2001, In : SIAM Journal on Computing. 31, 2, p. 447-459 13 p.

Research output: Contribution to journalArticle

Financial Markets
Investment Analysis
Game
Competitive Ratio
Online Algorithms
3 Citations (Scopus)

Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs

Ieong, S., Kao, M-Y., Lam, T. W., Sung, W. K. & Yiu, S. M., Jan 1 2001, Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001. Institute of Electrical and Electronics Engineers Inc., p. 183-190 8 p. 974428. (Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Approximation algorithms
RNA
Polynomials
14 Citations (Scopus)

Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets

Csurös, M. & Kao, M. Y., Jan 1 2001, In : SIAM Journal on Computing. 31, 1, p. 306-322 17 p.

Research output: Contribution to journalArticle

Evolutionary Tree
Recovery
Harmonic
Distance Matrix
Trees (mathematics)

Theoretical Computer Science: Foreword

Hsu, W. L. & Kao, M. Y., Aug 1 2001, In : Theoretical Computer Science. 261, 2, 1 p.

Research output: Contribution to journalConference article

Computer science
Computer Science
3 Citations (Scopus)

Towards understanding the predictability of stock markets from the perspective of computational complexity

Aspnes, J., Fischer, D. F., Fischer, M. J., Kao, M. Y. & Kumar, A., Dec 1 2001, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 745-754 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Predictability
Stock Market
Computational complexity
Computational Complexity
Polynomials
2000

A faster and unifying algorithm for comparing trees

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2000, Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. Sankoff, D. & Giancarlo, R. (eds.). Springer Verlag, p. 129-142 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1848).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Labeled Trees
Leaves
Evolutionary Tree
Distinct
Similarity Measure
37 Citations (Scopus)

A fast general methodology for information-theoretically optimal encodings of graphs

He, X., Kao, M. Y. & Lu, H. I., Jan 1 2000, In : SIAM Journal on Computing. 30, 3, p. 838-846 9 p.

Research output: Contribution to journalArticle

Labels
Encoding
Methodology
Triangulation
Graph in graph theory
9 Citations (Scopus)

Cavity matchings, label compressions, and unrooted evolutionary trees

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2000, In : SIAM Journal on Computing. 30, 2, p. 602-624 23 p.

Research output: Contribution to journalArticle

Evolutionary Tree
Labels
Cavity
Compression
Backbone
18 Citations (Scopus)

Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry

Chen, T., Kao, M. Y., Tepel, M., Rush, J. & Church, G. M., Jan 1 2000, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, p. 389-398 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Mass Spectrometry
Dynamic programming
Peptides
Sequencing
Mass spectrometry
1 Citation (Scopus)

Improved phylogeny comparisons: Non-shared edges, nearest neighbor interchanges, and subtree transfers

Hon, W. K., Kao, M. Y. & Lam, T. W., Jan 1 2000, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Teng, S-H., Lee, D. T. & Teng, S-H. (eds.). Springer Verlag, p. 527-538 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1969).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Phylogeny
Interchanges
Nearest Neighbor
Approximation algorithms
Approximation Algorithms
5 Citations (Scopus)

Linear-time approximation algorithms for computing numerical summation with provably small errors

Kao, M. Y. & Wang, J., Jan 1 2000, In : SIAM Journal on Computing. 29, 5, p. 1568-1576 9 p.

Research output: Contribution to journalArticle

Worst Case Error
Approximation algorithms
Linear-time Algorithm
Summation
Approximation Algorithms

Optimal bid sequences for multiple-object auctions with unequal budgets

Chen, Y., Kao, M. Y. & Lu, H. I., Jan 1 2000, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lee, D. T., Teng, S-H. & Teng, S-H. (eds.). Springer Verlag, p. 84-95 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1969).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Auctions
Unequal
Bidding
Object
Genes
23 Citations (Scopus)

Reducing randomness via irrational numbers

Chen, Z. Z. & Kao, M. Y., Jan 1 2000, In : SIAM Journal on Computing. 29, 4, p. 1247-1256 10 p.

Research output: Contribution to journalArticle

Irrational number
Randomness
Methodology
Polynomials
Polynomial

Risk profile problem for stock portfolio optimization

Kao, M. Y., Nolte, A. & Tate, S. R., Dec 3 2000, In : Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 228-234 7 p.

Research output: Contribution to journalArticle

Approximation algorithms
Probability distributions
Distribution functions
Profitability
Sampling
6 Citations (Scopus)

The enhanced double digest problem for dna physical mapping

Kao, M. Y., Samet, J. & Sung, W. K., Jan 1 2000, Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Springer Verlag, p. 383-392 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1851).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

DNA sequences
NP-complete problem
DNA Sequence
Linear Time
Restriction

Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2000, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lee, D. T., Teng, S-H. & Teng, S-H. (eds.). Springer Verlag, p. 479-490 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1969).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bipartite Matching
Labeled Trees
Matching Problem
Matching Algorithm
Evolutionary Tree
1999
21 Citations (Scopus)

A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 1999, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Nešetřil, J. (ed.). Springer Verlag, p. 438-449 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1643).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bipartite Matching
Evolutionary Tree
Decomposition Theorem
Decomposition
Computing
4 Citations (Scopus)

A fast general methodology for information — theoretically optimal encodings of graphs

He, X., Kao, M. Y. & Lu, H. I., Jan 1 1999, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Nešetřil, J. (ed.). Springer Verlag, p. 540-549 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1643).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Encoding
Methodology
Graph in graph theory
Separators
Planar graph
7 Citations (Scopus)

Balanced randomized tree splitting with applications to evolutionary tree constructions

Kao, M. Y., Lingas, A. & Östlin, A., Jan 1 1999, STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag, p. 184-196 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1563).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Evolutionary Tree
Binary trees
Approximation algorithms
Experiments
Distance Matrix

Designing proxies for stock market indices is computationally hard

Kao, M. Y. & Tate, S. R., Jan 1 1999, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Anon (ed.). SIAM

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Stock Market
Computational complexity
Financial markets
Computational Complexity
NP-complete problem