Optimization Very often we need to solve an optimization problem. Maximize the utility/payoff/gain/... 0 Minimize the cost/penalty/loss/... Many optimization problems are NP-complete No polynomial algorithms are known,and most likely,they don't exist. Question:Do you want more of this topic? ■ Approximation:get an approximately good solution. 2Optimization ◼ Very often we need to solve an optimization problem. ❑ Maximize the utility/payoff/gain/… ❑ Minimize the cost/penalty/loss/… ◼ Many optimization problems are NP-complete ❑ No polynomial algorithms are known, and most likely, they don’t exist. ❑ Question: Do you want more of this topic? ◼ Approximation: get an approximately good solution. 2