如何找到求解0-1二階錐規劃的複雜性？

Question

我有一個0-1二階錐（SOC）問題，如果使用分支和剪切（B & C）方法，我需要知道解決這個問題的複雜性？我解決這個問題的方式如下：

可以使用具有指數最壞情況複雜度，即O（2^n）的B方法來解決0-1SOC問題。在C方法的每個節點處，鬆弛問題是SOC問題，可以使用具有多項式時間複雜度的內點方法來解決。但是，我還沒有表達內點法的複雜性。假設這個複雜度是O（n）。然後，我可以聲稱，使用C方法解決0-1問題的複雜性是O（n）乘以O（n）次的O（2^n）次。

Answer 1

不要這樣想。您正在解決n個節點，每個節點的複雜度爲O（n）。通過我的計算，它會變成O（2^n * n^2）。