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

Research Output 1988 2017

Filter
Article
2017
2 Citations (Scopus)

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis

Johnsen, A., Kao, M-Y. & Seki, S., Feb 1 2017, In : Journal of Combinatorial Optimization. 33, 2, p. 496-529 34 p.

Research output: Contribution to journalArticle

NP-hardness
Self-assembly
Tile
Self assembly
Hardness
2016
1 Citation (Scopus)

Optimal search for parameters in Monte Carlo simulation for derivative pricing

Wang, C. J. & Kao, M-Y., Mar 1 2016, In : European Journal of Operational Research. 249, 2, p. 683-690 8 p.

Research output: Contribution to journalArticle

Pricing
Monte Carlo Simulation
Online Algorithms
Derivatives
Derivative
2015

Outstanding principal as prepayment value: A closed-form formula for mortgage pricing

Tsai, Y. C., Lei, C. L., Ho, J. M., Kao, M-Y. & Liao, S. L., May 1 2015, In : Journal of Information Science and Engineering. 31, 3, p. 925-942 18 p.

Research output: Contribution to journalArticle

pricing
Risk management
Costs
Values
financial market
2014
2 Citations (Scopus)

Linear-time accurate lattice algorithms for tail conditional expectation

Chen, B., Hsu, W. W. Y., Ho, J. M. & Kao, M-Y., Jan 1 2014, In : Algorithmic Finance. 3, 1-2, p. 87-140 54 p.

Research output: Contribution to journalArticle

Conditional Expectation
Linear Time
Tail
Extrapolation
Fractional Step
2013
1 Citation (Scopus)

Deterministic polynomial-time algorithms for designing short DNA words

Kao, M-Y., Leung, H. C. M., Sun, H. & Zhang, Y., Jul 8 2013, In : Theoretical Computer Science. 494, p. 144-160 17 p.

Research output: Contribution to journalArticle

Deterministic Algorithm
Polynomial-time Algorithm
DNA
Polynomials
Randomized Algorithms
2011
1 Citation (Scopus)

Discovering almost any hidden motif from multiple sequences

Fu, B., Kao, M-Y. & Wang, L., Mar 1 2011, In : ACM Transactions on Algorithms. 7, 2, 26.

Research output: Contribution to journalArticle

Motif Discovery
Probabilistic Model
Efficient Algorithms
Strings
Subset
2010

Testing whether a set of code words satisfies a given set of constraints

Wei, H. W., Lu, W. C., Huang, P. C., Shih, W. K. & Kao, M-Y., Mar 1 2010, In : Journal of Information Science and Engineering. 26, 2, p. 333-346 14 p.

Research output: Contribution to journalArticle

Table lookup
Testing
Hamming distance
DNA
2009
9 Citations (Scopus)

An approximation algorithm for a bottleneck traveling salesman problem

Kao, M-Y. & Sanghi, M., Sep 1 2009, In : Journal of Discrete Algorithms. 7, 3, p. 315-326 12 p.

Research output: Contribution to journalArticle

Traveling salesman problem
Approximation algorithms
Travelling salesman problems
Approximation Algorithms
Operations research
1 Citation (Scopus)

Linear-time haplotype inference on pedigrees without recombinations and mating loops

Chan, M. Y., Chan, W. T., Chin, F. Y. L., Fung, S. P. Y. & Kao, M-Y., Jun 1 2009, In : SIAM Journal on Computing. 38, 6, p. 2179-2197 19 p.

Research output: Contribution to journalArticle

Pedigree
Haplotype
Linear equations
Recombination
Linear Time
6 Citations (Scopus)

On approximating four covering and packing problems

Ashley, M., Berger-Wolf, T., Berman, P., Chaovalitwongse, W., DasGupta, B. & Kao, M-Y., Aug 1 2009, In : Journal of Computer and System Sciences. 75, 5, p. 287-302 16 p.

Research output: Contribution to journalArticle

Covering Problem
Packing Problem
Inapproximability
Approximability
Profitability
2 Citations (Scopus)

Probabilistic analysis of a m otif discovery algorithm for multiple sequences

Fui, B., Kao, M-Y. & Wang, L., Dec 1 2009, In : SIAM Journal on Discrete Mathematics. 23, 4, p. 1715-1737 23 p.

Research output: Contribution to journalArticle

Probabilistic Analysis
Motif Discovery
Probabilistic Model
Strings
Character
6 Citations (Scopus)

Randomized fast design of short DNA words

Kao, M-Y., Sanghi, M. & Schweller, R., Oct 1 2009, In : ACM Transactions on Algorithms. 5, 4, 43.

Research output: Contribution to journalArticle

Strings
DNA Computing
Coding Theory
Local Search Algorithm
Self-assembly
2008
5 Citations (Scopus)

Reconstructing phylogenies from noisy quartets in polynomial time with a high success probability

Wu, G., Kao, M-Y., Lin, G. & You, J. H., Jan 24 2008, In : Algorithms for Molecular Biology. 3, 1, 1.

Research output: Contribution to journalArticle

Phylogeny
Polynomial time
Polynomials
Topology
Computational Biology
2007
2 Citations (Scopus)

Average case analysis for tree labelling schemes

Kao, M-Y., Li, X. Y. & Wang, W., Jun 9 2007, In : Theoretical Computer Science. 378, 3, p. 271-291 21 p.

Research output: Contribution to journalArticle

Average-case Analysis
Labeling Scheme
Labeling
Labels
Separator
9 Citations (Scopus)

On constructing an optimal consensus clustering from multiple clusterings

Berman, P., DasGupta, B., Kao, M-Y. & Wang, J., Nov 15 2007, In : Information Processing Letters. 104, 4, p. 137-145 9 p.

Research output: Contribution to journalArticle

Clustering
Partition
Approximation algorithms
Similarity Measure
Data mining
67 Citations (Scopus)

Reversible sketches: Enabling monitoring and analysis over high-speed data streams

Schweller, R., Li, Z., Chen, Y., Gao, Y., Gupta, A., Zhang, Y., Dinda, P. A., Kao, M-Y. & Memik, G., Oct 1 2007, In : IEEE/ACM Transactions on Networking. 15, 5, p. 1059-1072 14 p.

Research output: Contribution to journalArticle

Monitoring
Data storage equipment
Intrusion detection
Routers
Data structures
2006
40 Citations (Scopus)

Design optimization methods for genomic DNA tiling arrays

Bertone, P., Trifonov, V., Rozowsky, J. S., Schubert, F., Emanuelsson, O., Karro, J., Kao, M-Y., Snyder, M. & Gerstein, M., Feb 1 2006, In : Genome research. 16, 2, p. 271-281 11 p.

Research output: Contribution to journalArticle

Oligonucleotide Array Sequence Analysis
Genome
DNA Fragmentation
Oligonucleotides
DNA
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
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
2004
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
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
2001
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

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
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)
2000
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
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
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
1999
39 Citations (Scopus)

Linear-time succinct encodings of planar graphs via canonical orderings

He, X., Kao, M. Y. & Lu, H. I., Jan 1 1999, In : SIAM Journal on Discrete Mathematics. 12, 3, p. 317-325 9 p.

Research output: Contribution to journalArticle

Planar graph
Linear Time
Encoding
Exponential time
Undirected Graph
8 Citations (Scopus)

On-line difference maximization

Kao, M. Y. & Tate, S. R., Jan 1 1999, In : SIAM Journal on Discrete Mathematics. 12, 1, p. 78-90 13 p.

Research output: Contribution to journalArticle

Optimal Algorithm
Scenarios
Line
Stochastic Games
Maximise
5 Citations (Scopus)

Optimal bidding algorithms against cheating in multiple-object auctions

Kao, M. Y., Qi, J. & Tan, L., Dec 1 1999, In : SIAM Journal on Computing. 28, 3, p. 955-969 15 p.

Research output: Contribution to journalArticle

Bidding
Auctions
Closed-form Solution
Object
Multivariate Distribution
7 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 1999, In : Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 119-128 10 p.

Research output: Contribution to journalArticle

Game theory
Financial markets
1998
8 Citations (Scopus)

A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Hsu, T. S. & Kao, M. Y., Jan 1 1998, In : Journal of Combinatorial Optimization. 2, 3, p. 237-256 20 p.

Research output: Contribution to journalArticle

Edge-connectivity
Augmentation
Edge-disjoint Paths
Disjoint Paths
Graph in graph theory

Efficient submesh permutations in wormhole-routed meshes

Ho, C. T. & Kao, M. Y., Jan 1 1998, In : Information Sciences. 107, 1-4, p. 1-13 13 p.

Research output: Contribution to journalArticle

Wormhole
Congestion
Permutation
Routing
Mesh

Gridding and discretization for divergence form (semiconductor-like) PDEs

Kao, M. Y., Rose, D. J. & Shao, H., Jan 1 1998, In : VLSI Design. 6, 1-4, p. 111-115 5 p.

Research output: Contribution to journalArticle

Partial differential equations
Conservation
Semiconductor materials
Finite element method
Convection
32 Citations (Scopus)

Optimal Constructions of Hybrid Algorithms

Kao, M. Y., Ma, Y., Sipser, M. & Yin, Y., Jan 1 1998, In : Journal of Algorithms. 29, 1, p. 142-164 23 p.

Research output: Contribution to journalArticle

Hybrid Algorithm
Randomized Algorithms
Competitive Ratio
Deterministic Algorithm
Resolve