Abner's Postgraduate Days

Ref.: Optimization Theory

For optimimzation of intertemporal allocation of resources, there are two usual appraoches, optimal control and dynamic programming. The former one is good for analysis and the later one is good for simulation.

Ref. Dynamic optimization problems:

Dynamic optimization problems involve dynamic variables whose values change in time. Such problems exist in the areas of optimal control, parameter estimation for dynamic models, reactor network synthesis where the dynamic models arise from the differential modeling of the tubular reactors (plug flow reactors), and for dynamic simulation and optimization.

Some links

• MIT OCW 14.128 Dynamic Optimization & Economic Applications (Recursive Methods), Spring 2003
• Texas A&M University. Agec 637 Production Economics and Dynamic Optimization, Prof. Woodward.
• Course 02711: Static and Dynamic Optimization

Dynamic Programming

Optimal Control Theory

:

Ref. : Optimal control From Wikipedia, the free encyclopedia.

Optimal control theory is a mathematical field that is concerned with control policies that can be deduced using optimization algorithms.

The control that minimizes a certain cost functional is called the optimal control. It can be derived using Pontryagin's maximum principle, or by solving the Hamilton-Jacobi-Bellman equation.

Ref. : The Mathematical Atlas 49: Calculus of variations and optimal control; optimization

Reference book:

• Elements of Dynamic Optimization by Alpha C. Chiang.
• Stokey, Nancy L., and Robert E. Lucas, Jr., with Edward C. Prescott. Recursive Methods in Economic Dynamics. Cambridge, MA: Harvard University Press, 1989.
• Optimal Control Theory: An Introduction, by Donald E. Kirk
• Optimal Control and Estimation (Dover Books on Advanced Mathematics), by Robert F. Stengel
• Optimal Control Theory and Static Optimization in Economics by Daniel Leonard, Ngo van Long

• Title: SubGemini: Identifying Subcircuits using a Fast Subgraph Isomorphism Algorithm
• Authors: Miles Ohlrich, Carl Ebeling, Eka Ginting, and Lisa Sather
• Source: Proceedings of IEEE/ACM Design Automation Conference,Dallas,1993:31-37
• Speaker: C. S. Ou
• Time: 03.09 (Friday) 19:30-21:00
• Place: Room 550, Department of Computer Science, NTHU

The authors proposed the heuristic algorithm to solve the problem Subgraph Isomorphism which is in NP-C.

Since the citcuit of VLSI design is a complicated network as hypergraph representation, for simplicity, they defined some kinds of vertices, P node for pMOS, C node for cMOS, etc. And they define the bubble node to represent the wire of IC circuit which is a hyperedge.

They labelled some informations on each vertex. Those informations about connection configuration will help them to find some ``key vertex'' as candidate for starting to check subgraph isomorphism.

That is the first phase of SubGemini.

The second phase is the procedure of checking subgraph isomorphism as traditional appraoch like BFS. Since we got those special ``key vertices'' as starting point, this algorithm will find subgraph isomorphism very fast. However this algorithm is not guarantee to find every isomorphic subgraph if those subgraphs coupled very close.



After the introduction of SubGemini, the speaker C. S. Ou also introduces his research that solve this problem by a very large matrix consisting of many small connection configuration matrices, e.g. one pMOS P1 and one CMOS C3 is connected by source of P1 and drain of C3, then its connection configuration matrix is look like the 3X3 0-1 matrix M which all entries are zero besides M(s,d).

They code thus connection configurations for some possible cases and set up some rules to filter most useless cases, eventually reduce such very large matrix into a much smaller one.

Finally they solve this reduced matrix as the problem SUBMATRIX which is also in NP-C. And the experimental results show that this algorthm got better performance.

ef.: Teresa M. Przytycka: An Important Connection Between Network Motifs and Parsimony Models. RECOMB 2006: 321-335

We demonstrate an important connection between network motifs in certain biological networks and validity of evolutionary trees constructed using parsimony methods.

We introduce a graph theoretical characterization that helps to select correct characters. Given a set of characters and a set of taxa, we construct a network called character overlap graph.

Here "taxa" means a grouping or classifing of organisms. It does not implies the specific biological class of organisms.

Given a set of taxa and a set of characters, one could constcut the character overlap graph, that the vertices are characters and the edge exists iff. there exists a taxon contains both characters.

Each taxon is described by a binary vector of attributes. Those attributes so called characters. If a taxon has a attributes, then it assigns 1 to the attribute in the binary vector, otherwise assgins 0.

Therefore we could use those informations like taxon to build an evolution tree using parsimony approach, i.e., Maximum Parsimony Tree Problem. Most variations of it are in NP-C. In spite of it, the correctness problem, i.e., the correctness of the bulit evolution tree, is also open.

Intuitively, its correctness depends strongly on choosing appropriately charactors and taxa. The goal of this paper is to give a method to improve the correctness of evolution tree which is contructed by parsimony approach.

First, author defined "persistent," i.e., a charactor is persistent if it is gained exactly once and lost at most once, and persistent parsimony means all charactors are persistent.

The author found that the hole, chordless cycle of length at least four, is rare in charactor overlap graph whose charactors are chose as protein domains. In contrast, the hole is abundant in charactor overlap graph whose charactors are chose as introns. Furthermore the correctness of tree built by domain overlap graph is better than built by intron overlap graph. (refers the references [11], [27], [10], [29] of this paper.)

The author believe this phenomenon is meaningful. He prove that

If all charactors are persistent then corresponding charactor overlap graph is chordal.

Therefore we could measure whether the chosen charactors lead to incorrect evolutionary tree by the Edge-Deletion Problem of chordal graph. Unfortunately it is in NP-C.

The author adapt the idea of network motif. He just counts the number of squares, the chordless cycles with length 4, of the charactor overlap graph, and compare it to the number of squares of charactor overlap graph whose charactors gain or loss randomly.

Although the relation between non-persistent charactors and the number of squares is not so clear. Few non-persistent charactors might lead to large number of squares, and large number of squares might have small non-persistent charactors. We still could benefit from it by finding the charactors involved in a large number of squares. It is a significant noise of the data. (In domain overlap graph, those charactors, that involved in a large number of squares, are the promiscuous domains which are known to appear in many diverse multidomain proteins.)

Ref.: Teresa M. Przytycka, Chordal Graphs in Computational Biology - New Insights & Applications, Seminars, Computing Science, Simon Fraser University.

we introduced and studied graph theoretical representation of multidomain proteins called domain overlap graph. In the domain overlap graph, the vertices are protein domains and two domains are connected by an edge if there is a protein that contains both domains.

This leads the studies of a graph-theoretical framework, based on properties of chordal graphs and cographs [3].

References:

1. Teresa M. Przytycka, George Davis, Nan Song, Dannie Durand: Graph Theoretical Insights into Evolution of Multidomain Proteins. RECOMB 2005: 311-325
2. Teresa M. Przytycka. An important connection between network motifs and parsimony models. RECOMB 2006, Lecture Notes in Computational Biology, 2006. (My Note)
3. Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations, Zotenko E, Guimaraes KS, Jothi R, Przytycka TM. Algorithms for Molecular Biology 2006, 1:7

The blog, [Lowerbounds, Upperbounds], is to build a community among the Theory group members of CMU.

There are two entries catching my eyes. The first one is the Theory Seminar 2007-02-16: Adaptive Analysis of Algorithms, Erik D. Demaine, MIT.

It is common sense that worst-case analysis of algorithms is not good enough, and Average-case analysis is hard to do.

verage-case analysis gives a better sense about possible performance, but requires some knowledge about the distribution of inputs, making results more specific. In contrast, adaptive analysis parameterizes the input space by one or more additional parameters beyond the problem size, and the goal becomes to optimize simultaneously for all values of those parameters, which is a substantially stronger form of worst-case analysis. When possible, strong adaptive bounds give a fine sense of the intrinsic difficulty of inputs and a better sense of which algorithms are better than which others.

The most promising direction might be "Smoothed Analysis". However it seems also tough and doesn't get the corresponding success.(I am not sure!?)

Erik D. Demaine talked about adaptive analysis of algorithms that I didn't hear before, but there is no slides and bibliography in such entry. I found some articles, that seem to be related to adaptive analysis, on prof. Demaine's homepage.

Ref.: Ilya Baran and Erik D. Demaine, ``Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve,'' in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9-11, 2004, pages 220-229.

Ref.: Ilya Baran, Erik D. Demaine, and Dmitriy A. Katz, ``Optimally Adaptive Integration of Univariate Lipschitz Functions,'' in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20-24, 2006, pages 142-153.



The other is Theory Seminar 2007-02-23: The Price of Privacy and the Limits of LP Decoding, Kunal Talwar, Microsoft Research.

But there is no material, too. But this result is accepted for presentation in STOC 2000.

Nature has a short article about Brain Drain of Italian. And two italian researchers Luca Trevisan and Luca Aceto gave comments "The Runaway Brains" and "Brain Drain and Brain Gain", respectively.

It discuss the bad phenomenon that Italian universities and research institutions can't keep the good Italian researchers and appeal foreign researchers.

Taiwan got the same problem. We all need introspections!

Currently I am writing a draft for the 24th workshop on combinatorial mathematics and computation theory.

I found that the author ordering tradition of TCS, i.e., alpha-by-author ordering, is not always satisfied.

Ref.: Machine Learning (Theory) Best Practices for Collaboration

I found a new journal ``Internet Mathematics'' which publishes research papers that address fundamental problems in dealing with large complex information networks such as the Internet.

This journal seems not famous yet, but its Editorial Board impresses me. Many big heads on it such as Fan Chung Graham, Noga Alon, Jon Kleinberg.

It has short history, but there are many interesting papers:

Volume 1 (2003¡V2004)

• Coupling Scale-Free and Classical Random Graphs by Bela Bollobas and Oliver Riordan
• Graph Clustering and Minimum Cut Trees by Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis
• Coupling Online and Offline Analyses for Random Power Law Graphs by Fan Chung and Linyuan Lu
• Network Applications of Bloom Filters: A Survey by Andrei Broder and Michael Mitzenmacher

Volume 2 (2005¡V2006)

• Lower Bounds and Algorithms for Dominating Sets in Web Graphs by Colin Cooper, Ralf Klasing, and Michele Zito

Volume 3

• Estimating Entropy and Entropy Norm on Data Streams by Amit Chakrabarti, Khanh Do Ba, and S. Muthukrishnan
• Concentration Inequalities and Martingale Inequalities: A Survey by Fan Chung and Lincoln Lu

Prof. Tang required me to prepare the slides about hashing for the course Data Structure. Actually the idea of hashing is applied to many different fields, e.g., Cryptography, Error correction, Identification and verification.

Wikipedia:: The origins of the term

The term "hash" comes by way of analogy with its standard meaning in the physical world, to "chop and mix." Knuth notes that Hans Peter Luhn of IBM appears to have been the first to use the concept, in a memo dated January 1953; the term hash came into use some ten years later.

The following is some resources about hashing

• Linear hash From Wikipedia, the free encyclopedia
• Trie From Wikipedia, the free encyclopedia
• Dynamic hash tables, Communications of the ACM
• Hash Functions and Block Ciphers
• Distributed hash table From Wikipedia, the free encyclopedia
• Hash table From Wikipedia, the free encyclopedia
• MapReduce From Wikipedia, the free encyclopedia
• Powerpoint presentations for Fundamentals of Data Structures in C++, Second Edition, prepared by Prof Sartaj Sahni using Powerpoint 2000.
• J. Rufino, A. Pina, Albano Alves and J. Exposto, Distributed Paged Hash Tables, "5th International Meeting on High Performance Computing for Computational Science (VECPAR '02) - Selected Papers and Invited Talks, Springer, 679-692, Porto, Portugal, June 2002
• M. Bienkowski, M. Korzeniowski, and F. M. auf der Heide. Dynamic load balancing in distributed hash tables. Manuscript, 2004.
• Routing Networks for Distributed Hash Tables, Gurmeet Singh Manku
• Bloom filter From Wikipedia, the free encyclopedia

And Here is the slides I made.

Department of Computer Science and College of Life Science, National Tsing Hua University, collaberate to host a talk series about Systems Biology and Computational Biology.

The speaker of this week is Professor Tao Jiang. He is real a nice guy!



I was assigned the job to serve Professor Tao Jiang in this period. I have written a note about it in chinese.