“To Be or Not To Be”:
A Story of Decision, Optimization, and Randomization,

Shuzhong Zhang
Dept of Systems Engineering & Engineering Management
The Chinese University of Hong Kong

Conscious awareness and the associated ability to rational decision-making are arguably the characteristics of human beings. Our modern life is, therefore, a result of ‘quantum leaps’ in the quality of enhanced decision processes. Optimization and computational mathematics, being the backbone of the science of decisions, deserve the credits of the past and bear the responsibilities for our continued future success. If a decision problem is likened to be a hard-shell nut, and the computational power to brutal force, then finding a right spot to apply the force is the key knowledge about the nut itself. Typically, a hard nut will not yield to an unorganized and uninformed application of force. This key knowledge about where to apply the force does not come for free; indeed it takes efforts to obtain. The tradeoff between the necessary effort and value of the desired key information is administrated by Nature, who acts like a ‘fair’ arbitrator on the matter. The ‘pricelist’ in the trade is known as the complexity theory. Thus, the difficulty of a decision problem may not only be caused by its size, but also the price to obtain the ‘key’, which is set according to the complexity theory. A recent study in computer science and optimization suggests a non-intuitive method to solve some of the very hard decision and computational problems. The method in question is called randomization. Essentially, this approach tries to involve a third party in the ‘effort vs. information’ game: the chance. It turns out that if absolute certainty is relaxed to ‘confidence levels’, then the landscape of computational complexity changes dramatically. This leads to interesting results. In this talk, we shall discuss several particular applications of this technique as modern computational tools to solve problems in optimization. As examples, we mention graph problems, machine scheduling, wireless sensor network communication, signal processing, and portfolio selection problems.

# Uploaded 59 Plays / / 0 Comments Watch in Couch Mode


Kavli Frontiers of Science PRO

This channel contains session presentations that cover mathematical topics from the Kavli Frontiers of Science symposium series of the National Academy of Sciences.

For additional symposium information, please visit our web site (

Browse This Channel

Shout Box

Channels are a simple, beautiful way to showcase and watch videos. Browse more Channels. Channels