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 この本がすごい。というかほしい。