作為一個科研水軍
成果很少並且還都是灌水的貨色
（CCF A和B刊也不例外）
但唯獨覺得還值得我再回頭多看一眼的
是我在美國Clemson讀博時期的碩士論文
以及幾年後三作發表在Journal of Global Optimization上面的工作
眾所周知揹包問題（Knapsack Problem）是一個經典的NP完全問題
即不存在多項式時間的解法
（演算法複雜度通常是指數級的）
我的碩士論文用數學歸納法證明了一類特殊的揹包問題是多項式時間可解的！
（典型的數序系最佳化工作：提出猜想-程式設計用無數例項驗證-寫數學證明）
揹包問題（Knapsack problem）是一種組合最佳化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定揹包中。 也可以將揹包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V。
具體來說
我們證明了這類揹包問題的整數規劃（Integer Progamming）模型
它的係數矩陣是全單位模（Total Unimodular）
（我們找到了這個整數規劃問題的凸包-Convex Hull）
即：此時的整數規劃問題等價於求解一個線性規劃問題
而線性規劃問題是有多項式時間演算法的（例如橢圓演算法）
所以是多項式時間可解的
雖然這是我8年前的碩士論文的一個微小工作
但也是迄今為止最為酣暢淋漓的科研經歷
整個專案從立項到完成數學證明只花了3個月左右
而證明的關鍵突破口
是我的大老闆Warren Adams做夢夢出來的
W. Adams教授是個非常有學術品味的教授
碩士畢業後三年半才把這篇論文發表出來（他是一作）
原因之一是他覺得我用數學歸納法證明太醜（ugly）
於是乎又用全新的方法證明了上述猜想
（理論上可以水倆篇了）
論文連結如下：
https://link.springer.com/article/10.1007/s10898-016-0435-3link.springer.com
Kind Reminder:
全文全程數學公式
比較勸退
http://www.optimization-online.org/DB_FILE/2015/12/5246.pdf
我的碩士論文太ugly
就不貼了。。
作為一個科研水軍
成果很少並且還都是灌水的貨色
（CCF A和B刊也不例外）
但唯獨覺得還值得我再回頭多看一眼的
是我在美國Clemson讀博時期的碩士論文
以及幾年後三作發表在Journal of Global Optimization上面的工作
眾所周知揹包問題（Knapsack Problem）是一個經典的NP完全問題
即不存在多項式時間的解法
（演算法複雜度通常是指數級的）
我的碩士論文用數學歸納法證明了一類特殊的揹包問題是多項式時間可解的！
（典型的數序系最佳化工作：提出猜想-程式設計用無數例項驗證-寫數學證明）
揹包問題（Knapsack problem）是一種組合最佳化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定揹包中。 也可以將揹包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V。
具體來說
我們證明了這類揹包問題的整數規劃（Integer Progamming）模型
它的係數矩陣是全單位模（Total Unimodular）
（我們找到了這個整數規劃問題的凸包-Convex Hull）
即：此時的整數規劃問題等價於求解一個線性規劃問題
而線性規劃問題是有多項式時間演算法的（例如橢圓演算法）
所以是多項式時間可解的
雖然這是我8年前的碩士論文的一個微小工作
但也是迄今為止最為酣暢淋漓的科研經歷
整個專案從立項到完成數學證明只花了3個月左右
而證明的關鍵突破口
是我的大老闆Warren Adams做夢夢出來的
W. Adams教授是個非常有學術品味的教授
碩士畢業後三年半才把這篇論文發表出來（他是一作）
原因之一是他覺得我用數學歸納法證明太醜（ugly）
於是乎又用全新的方法證明了上述猜想
（理論上可以水倆篇了）
論文連結如下：
https://link.springer.com/article/10.1007/s10898-016-0435-3link.springer.com
Kind Reminder:
全文全程數學公式
比較勸退
http://www.optimization-online.org/DB_FILE/2015/12/5246.pdf
我的碩士論文太ugly
就不貼了。。