https://xuzijian629.hatenadiary.jp/entry/2019/07/27/154356 以前環境構築についてまとめた 今回は実装を読んでいく。 MVCについて読むが多分構造は他も一緒 構造 eps_start = 1.0 eps_end = 0.05 eps_step = 10000.0 for iter in range(int(opt['max_iter…

www.sciencedirect.com 説 明 が ウ ン チ ー コ ン グ writerやめろ 概要 「木と、正整数が与えられたとき、を次元hypercubeに埋め込めるか」という判定問題はNP-Complete. まあこれが成り立つので、はより一般にグラフに拡張できる。 証明がExact Cover by…

論文のメモと証明テクの確認 dl.acm.org www.sciencedirect.com それぞれ3-Partition ProblemかExact Cover by 3-sets. あとで追記するかも

www.sciencedirect.com 概要 グラフがcubicalであるとは、あるhypercubeが存在して、そのsubgraphとなることをいう。が与えられたとき、がcubicalであるか判定するのはNP-Complete hypercube 頂点番号がからからなり、頂点番号のbinary表現で1bitだけ異なる…

Euclidean TSPをやって、100頂点程度までなら最適解を出せた、という研究 この先行研究は1990年代とかでかなり古いっぽい。 入力は、2次元平面上の点の座標で、出力はのpermutation. RLで、policy を学習するっぽい。 条件付き確率で分解する。 ただしは先頭…

https://papers.nips.cc/paper/7214-learning-combinatorial-optimization-algorithms-over-graphs.pdf NeurIPS 2019でもしゃべていたのでついにちゃんと読んだ はじめに 界隈はこの論文を最強だと思っているらしい。多分グラフ機械学習で離散最適化やってい…

www.semanticscholar.org を読んだ。 先行研究のミスを指摘していてワロタ。 概要 二分木をsquare gridに埋め込めるかどうかはNP-Complete 最大次数に注目すると、最大次数2のグラフはサイクルまたはパスグラフなので、埋め込みは自明に可能 最大次数を3に許…

解く問題を増やす Maximum Independent Set Maximum Clique Maximum Cut TSP Minimum Feedback Vertex Set (?) まあ他にもいろいろ 実装を改善する もっと演算を速くしたいですね S2V-DQNと比較することにする なんか他によくできる点がないか考えるか

arxiv.org Yoichi Iwataに教えてもらった、MIS最強系の論文。Exactなアルゴリズムではないが、最適解がわかっているデータセットで軒並み最適解を出していて強い。 Kernelに遺伝的アルゴリズムを使用することを再帰的に行うアルゴリズム Evolutionary Algori…

まあ別に初めてではないのであれなんですが 今回はちゃんと1~2週間ぐらい網羅的にサーベイして、完全にかぶっていないことを確認したつもりだったんですが、 先行研究のciteが2とかだった上に、問題の英語名が特殊で、自分の検索ワードと全然マッチしなくて…

グリッドグラフの描画とか、horizontalとverticalしか使っちゃだめ系描画など、一般に「自由度が相対的に制限される」ようなセッティングにおける可能性判定の証明に使える気がする。 証明のテクは、「必ずこの配置しかありえない」ような配置を組み合わせ、…

arxiv.org ウ ン チ ー コ ン グ ！ グリッドに描画できるグラフのクラスをいろいろ考えて、PolynomialなものとNP-Completeなものに分けた。一般の描画はNP-Complete(そもそも木が無理なので) 次数がの要素のみからなるグラフを-Graphとよぶことにする。たと…

タイトル練り直せ www.sciencedirect.com Theorem 最大次数が4の木をグリッドに埋め込めるかはNP-Complete 証明 not-all-equal 3satに帰着する。これは、3CNF式が与えられたときに、各clauseに少なくともひとつfalseになるリテラルが含まれるように充足可能…

http://www.graphclasses.org/classes/gc_440.html 判定はNP-Completeでした。 arxiv.org ウ ン チ ー コ ン グ ！ ウ ン チ ー コ ン グ ！ ウ ン チ ー コ ン グ ！ ウ ン チ ー コ ン グ ！ ウ ン チ ー コ ン グ ！ ウ ン チ ー コ ン グ ！ ウ ン チ ー…

お待たせいたしました。Competitive Programming Advent Calendar 2019 8日目の記事です。 平面グラフとは 平面グラフとは、平面に辺を交差させずに描画できるグラフのことをいいます。現実世界の例では多くのroad mapがそうであったりします。平面グラフで…

IPのBranch&Broundを、GCNNを使って決定するという論文。なんでGCNNなのか結局ポスターを見る限りはわからなかった。比較対象がみんなアで、そんなに強くなさそう感がすごい。 joisino論文。distributed local algorithmという視点がいいし安心の解析がある…

https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf LP緩和の解はシンプレックスの端点であり、シンプレックスの端点は、「異なる2つの実行可能解の合成でかけないこと」と同値。 non-halfintがあったとすると、その解をεだけ上下にずらした…

https://hochbaum.ieor.berkeley.edu/html/pub/EJOR-3var.pdf IPの制約がMonotoneのときは、minCutに帰着して多項式時間でhalfintegral解が求まるっぽい。目的関数は非線形でもいいらしい。 あとで読む。

writeupです。 ++age;今日誕生日なので, 1日限定でCTFを開催してみました。https://t.co/U02CnUnGge問題はあまり難しくないかもしれませんが, 息抜きにでも参加してみてください！— Tasker (@task4233) December 4, 2019 深夜にツイッターを見ていたら面白そ…

www.crcpress.com この本がすごい。というかほしい。

link.springer.com 線形計画問題は Unbounded Infeasible has an optimal solution の3通りしかないけど整数計画問題はそうとは限らなく、 いくらでもいい結果が存在する というパターンがある。 たとえば、 maximize subject to , is positive integer など…

www.sciencedirect.com 自分の問題の解決になるかなあと思って読んだけど特にならなかった。 https://xuzijian629.hatenadiary.jp/entry/2019/11/28/133732 こちらの記事とはかなりやり方が違う。 初めにtriangulateするところは同じだけど、かなり幾何的に…

www.semanticscholar.org 無料PDFが見つからなかったのでスライドを読んだ。 https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf?_ga=2.178289380.1937718360.1574912307-1595927464.1574667430 アルゴリズムは3ステップに別…

https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-25.pdf をざっと見た。 平面グラフのsubgraph isomorphismで、のサイズを定数をすると、時間で解ける、という論文。 とくに、の木幅をとすると、時間で判定できるっぽい。 細かくは読んでいない。

cs.smith.edu Grid Graph がsolidであるとは、格子点におけるの補グラフの連結であるということである。 グリッドグラフ上でのハミルトンパス（もしくはサイクル）問題は、solidなグリッドグラフ（穴を含まない）なら多項式時間で解くことができるが、一般の…

優勝しました！ これでやっと競プロのコンテスト優勝者を名乗れる… 申し込み ICPCとかぶっているということで、賞金チャンスがかなり高まったのでモチベがあがります。 Girigiriは仲がいいのでこういう情報はちゃんと隠されずにシェアされてうれしいですね〜…

https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf この資料が秀逸だった。

http://proceedings.mlr.press/v48/cohenb16.pdf を読んだ。 概要 ConvNetの理論解析をテンソル分解で行っている。 結果として、ReLU + max-poolでのuniversality, ReLU + ave-poolでのnon-universality, depth efficiencyなどを解析している。 Related Work…

元論文はhttp://hinkali.com/Education/PlanarityTesting.pdf ここが日本語で説明してくれている http://www.th.cs.meiji.ac.jp/assets/researches/2007/toyota/index.html アルゴリズム グラフをdfsし、訪れた順にidを振っていく。dfs木と後退辺を覚えてお…

https://arxiv.org/pdf/1905.01004.pdf を読んだ。 問題設定 データセットと学習アルゴリズムを固定したときに、入力に対する予測の誤差の期待値を抑えるのではなく、その期待値と、有限個の入力での誤差の平均の差(Generalization Error)を抑える。 →何個ぐ…