Using 3SAT to prove Knapsack, Clique's hardness

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese4.html#Q1-60004-22

NS2 Tutorial

http://www.isi.edu/nsnam/ns/tutorial/

Unix network programming

Beej's Guide is good for beginner.

Semidefinite Programming

This semester, I have a chance to study carefully SDP. Here are some useful materials from Ngo and Rudra seminar I am taking. If you want to discuss any of these, let me know.

• Laci Lovasz, Semidefinite optimization, 1995-2001. [ ps ]
• L. Vandenberghe and S. Boyd, Semidefinite Programming, SIAM Review, 38(1): 49-95, March 1996. [ pdf ]
• Zwick, Semidefinite Programming Based Approximation Algorithms. [ ppt ]
• Feige, The Use of Semidefinite Programming in Approximation Algorithms. [ ppt ]
• Arora, Semidefinite Programming and Approximation Algorithms for NP-hard Problems: A Survey. ( Slides in pdf )

Phil Collins's song

You'll be in my heart

Kenny G - Song Bird

"Stay Hungry, Stay Foolish"

This is a talk of Steve Jobs at Stanford Commencement,2005.

His third story reminds me me about a chapter in the book "The 7 habits of highly effective people", by Stephen Covey. They both advice us to "begin with the end in mind". Think about "death" to live with all our love, our passion today, but I prefer the word "the end" than "death".

With "the end", I can apply this idea on many contexts. At night, I can ask my self what I want to be done by tomorrow? Usually, many plans come up for this answer, many sometimes mean "more than enough for a day". But in those plans, there is nothing like "1 hour sitting and thinking of nothing", "1 hour lazy and not wanting to do anything on a half day",... In a context of a year, do I have have any plan? Yes, I do. How about 10 years, 20 years? Yes and yes!

I find it surprising here when I use the word "plan". I have a "plan" for today; but what about in 5 years or ten years or longer. Not much specific, but just think about "what I want to have or to be". I do not have any clear "plan" to achieve those goals. How can I get my destination if I don't have a map, and don't "plan" which roads I should take and which directions I should turn?

This talk prompts me to think about the connection between: "the end"+"plan". Nice talk! Especially love his idea "Stay Hungry. Stay Foolish."

Optimization books

Here is the good reference for optimization books.

I should read the following books now:
1. Convex Optimization
Stephen Boyd and Lieven Vandenberghe
Lecture slides and videos for this book can be found here.
2. Nonlinear programming
by Dimitri P. Bertsekas

CHOCOLATE FRUIT DIP

From: cooks.com


2/3 c. corn syrup (light or dark) (32 Tea Spoon)
1/2 c. whipping cream (24 Tea Spoon)
1 (8 oz.) pkg. Baker's semi-sweet chocolate (or 4 oz. semi-sweet & 4 oz. sweet chocolate)
Assorted fresh fruit: apple, strawberry, banana, pineapple, orange, kiwi, peach, pear

In medium saucepan, stir corn syrup and cream. Bring to a boil over medium heat. Remove from heat and add chocolate. Stir until completely melted. Serve warm with fresh fruit. Makes 1 1/2 cups.

Sublinear Time Algorithms

I am reading "Approximating the minimum spanning tree weight in sublinear time" by Chazelle, Robinfeld, and Trevisan. So far, we try to approximate problems NP. In this paper, I come to know it's very interesting to approximate polynomial time algorithms as data sets are really BIG nowadays. This raises a lot of open problems. Here is a useful page of Ronitt Rubinfeld for a starting point in this area.

Save the last dance for me

Letchworth State Park

This park is beautiful, especially in Fall. You're better hurry as the Fall is leaving soon.

Approximation Algorithms

1. Lecture notes on Approximation Algorithms by Chandra Chekuri
http://www.cs.uiuc.edu/homes/chekuri/teaching/fall2006/approx.htm
2. Using primal dual method for Approximation Algorithms, a good survey by David P. Williamson
The primal-dual method for approximation algorithms and its application to network design problems
3. Using Local Ratio method for Approximation Algorithms, a survey by Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz
Local ratio: A unified framework for approximation algorithms
4. Some time it seems that whatever way we try, we just can find a approximation. Well, maybe computing good approximation for that problem is also NP-hard. To prove the hardness of approximation, following documents are good starting point:
A survey by Sanjeev Arora, and Carsten Lund
Hardness of approximations
Another one by Luca Trevisan
Inapproximability of Combinatorial Optimization Problems
For approximating minimization problems
On the hardness of approximating minimization problems

I am trying to sing this song in English.

The Great Circle of Viet Nam

(translated by Richard Fuller)

1. From jungled hills to the distant sea,
We form a giant circle to unite our country.
From far and wide, we now return,
With joy, like a sandstorm, to the far horizons,
Let's now join hands :
A great circle of Viet Nam

Flags in the wind, happy nights and days,
Of one blood our hearts ablaze,
Reconciled, a new day.
Hamlet, town now joined as one,
Remember the dead as we bask in the sun,
And one by one, we spread our smiles.

2. From North to South, we all join hands,
From fields long abandoned to mountainous lands,
We'll ford deep streams, climb over hills.
From hamlets to the cities,
We embrace with glee an eternal circle :
Dead and living, one are we.



Nối vòng tay lớn
(Trịnh Công Sơn)

Rừng núi dang tay nối lại biển xa
Ta đi vòng tay lớn mãi để nối sơn hà
Mặt đất bao la anh em ta về
Gặp nhau mừng như bão cát
Quay cuồng trời rộng bàn tay ta nắm
Nối tròn một vòng Việt Nam

Cờ nối gió đêm vui mỗi ngày
Dòng máu nối con tim đồng loại
Dựng tình người trong ngày mới
Thành phố nối thôn xa vời vợi
Người chết nối linh thiêng vào đời
Và nụ cười nối trên môi

Từ Bắc vô Nam nối liền nắm tay
Ta đi từ đồng hoang vu vượt hết núi đồi
Vượt thác cheo leo tay ta vượt đèo
Từ quê nghèo lên phố lớn
Nắm tay nối liền biển xanh sông gấm
Nối liền một vòng tử sinh.

July 12, 2008 - Harriman State Park

Back to our hiking season, this time we went to Harriman State Park. It's bigger than Franklin D. Roosevelt State Park, we visited two weeks before. There are mountains and lakes. The trail was bit more challenging this time. The evidence was that after eating a quarter of an average-size watermelon, I felt like my legs were cemented on the rocks. You can see how happy I was when I was on top of mountain (or hill?).



Yah, now it's easy to get down to the ground.



... and enjoyed fishing time

A gift

This is a gift from "someone". I love it very much. Every day, I put those marigolds in front of the house, before I go to school, so that they can enjoy summer's sunshine. In the late afternoon, I water them when I come home. Then, I bring them to the porch, behind the living room door. There, they can enjoy sunset (and I can gaze at them). Wait and see how they will grow up.
Thanks "there" alot :)

Yah, now you should come here and see I have done good job

July 4, 2008

I went to NYC some times, enjoyed broadway shows, bars, shopping, having dinner on boat tour; but NYC haven't , really, attracted me much. Even though I am living close to NYC now, it is very convenient to catch a train to there; but it's the last thing I want to do, I guess.
Last week, I were there with 3 friends for a special day, Independence Day. After walking, watching, eating around for almost whole day, finally we settled down for fireworks . We sat on shower curtain, played cards, and ate tons of fruits IN THE RAIN. It's fun to play cards, and hold an umbrella at the same time :)
The fireworks weren't as beautiful as I expected,but didn't matter. We had something to remember :)

Franklin D. Roosevelt State Park

This is the first time of our hiking season :D We are planning to hike every weekend at different places. Here is Franklin D. Roosevelt State Park.

Sunset

Sunset here is beautiful, and enjoyable with fresh air, rock, and wave sound. Almost everyday I have a walk here after dinner. Enjoy it after struggling with a "BIG" problem for the whole day :)

June 12,2008