Rijuyuezhu's Blog

Record every drop in my life

OT:除MS和MAX-CUT外,近似算法还可用于解决其它问题,例如SCP(JH算法4.3.2.11)、SKP(JH算法4.3.4.1和4.3.4.2)等,请调研至少2种近似算法(其中至多1种来自上述例子,图上的优化问题不在调研范围内),结合例子介绍算法的设计与分析,重点阐述近似比的证明过程。

Read more »

OT:除福特-法尔克森算法外,最大流问题还有很多其它算法,例如 Edmonds-Karp 算法、Dinitz 算法、Push-Relabel 算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与福特-法尔克森算法比较异同并分析优劣。

Read more »
0%