「The matching polytope has exponential extension complexity」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* The matching polytope has exponential extension complexity
- Thomas Rothvoss
- STOC 2014
* 概要
- extension complexityって何？
-- LPで問題を表現した時の不等式の数
- mathcing polytope
-- マッチングを表現する超多面体
- 結果: matching polytopeをLPで表現するには「指数個の制約」が必要
-- マッチングはPなのに？！
-- ↑ここが驚くべきこと
- 今まで: NP-hardな問題だけだった
* Extention Complexity
- TSP polytopeは対称な多項式個の制約式では表現できない
-- LPで簡単には表現できない
-- TSPがLPでかけるからP=NPだよね～を否定
** Parity Polytope
- PP_n = 1の個数が奇数の{0,1}^nベクトルの凸包
- x∈PP_nという制約でLPは解ける
- Parity PolytopeはLPで簡単に表現できる？
-- facet（n-1次元の面），つまり不等式制約の数は指数個ある
--- 3次元なら4面体なので4つ
-- 新しい変数を導入して多項式個へ！
-- 観察: パリティごとに考える1,3,5,…
- Parity PolytopeのExtension Complexityは多項式以下: xc(PP_n) = n^O(1)
- Polytope P = {x | Ax ≦ b}
- これは変えて…
-- P = {x | ∃y: Bx+Cy ≦ d}
- こっちのが少ないかも？
- イメージ
-- Qという超多面体をP（より低次元）に射影
-- Qの制約の方が少ないかも
* TSP polytope
- TSP polytopeが多項式個の制約で書けると，TSPが多項式個で解けちゃう
- [Yannakakis, 1991]
-- 変数を追加してもだめ～
- [Fiorini et al., 2012]
-- xc(TSP(K_n)) ≧ 2^Ω(√n)
- 最近NP-hardな問題に対して色々と分かってきている
- Pは？
* Matching Polytope
- LPで適当に書くと指数個だけど
- 制約をviolateするのはフローとかで多項式時間で判定される
- でも！
- xc(perfect matching polytope) ≧ 2^Ω(n)
* The matching polytope has exponential extension complexity
- Thomas Rothvoss
- STOC 2014
* 概要
- extension complexityって何？
-- LPで問題を表現した時の不等式の数
- matching polytope
-- マッチングを表現する超多面体
- 結果: matching polytopeをLPで表現するには「指数個の制約」が必要
-- マッチングはPなのに？！
-- ↑ここが驚くべきこと
- 今まで: NP-hardな問題だけだった
* Extention Complexity
- TSP polytopeは対称な多項式個の制約式では表現できない
-- LPで簡単には表現できない
-- TSPがLPでかけるからP=NPだよね～を否定
** Parity Polytope
- PP_n = 1の個数が奇数の{0,1}^nベクトルの凸包
- x∈PP_nという制約でLPは解ける
- Parity PolytopeはLPで簡単に表現できる？
-- facet（n-1次元の面），つまり不等式制約の数は指数個ある
--- 3次元なら4面体なので4つ
-- 新しい変数を導入して多項式個へ！
-- 観察: パリティごとに考える1,3,5,…
- Parity PolytopeのExtension Complexityは多項式以下: xc(PP_n) = n^O(1)
- Polytope P = {x | Ax ≦ b}
- これは変えて…
-- P = {x | ∃y: Bx+Cy ≦ d}
- こっちのが少ないかも？
- イメージ
-- Qという超多面体をP（より低次元）に射影
-- Qの制約の方が少ないかも
* TSP polytope
- TSP polytopeが多項式個の制約で書けると，TSPが多項式個で解けちゃう
- [Yannakakis, 1991]
-- 変数を追加してもだめ～
- [Fiorini et al., 2012]
-- xc(TSP(K_n)) ≧ 2^Ω(√n)
- 最近NP-hardな問題に対して色々と分かってきている
- Pは？
* Matching Polytope
- LPで適当に書くと指数個だけど
- 制約をviolateするのはフローとかで多項式時間で判定される
- でも！
- xc(perfect matching polytope) ≧ 2^Ω(n)
&tags()
&update()
