Joeの精進記録

旧:競プロ練習記録

2020-01-01から1年間の記事一覧

A Faster Parameterized Algorithm for Treedepth

木分解上のDPによってtreedepthを求める。 アルゴリズム自体が結構むずかしく、正当性は非自明 木分解上の各bagは、「そのbag以下の部分木のbagのUnionに含まれるノードについてのtreedepth decompositionのpartial decomposition」をもつ。partial decompos…

Computing Tree-Depth Faster Than $2^n$

タイトルの通り アルゴリズムの概略は以下の通り ほぼ愚直なアルゴリズムがあり、アルゴリズムの探索空間を狭めた、を構築して、大部分の問題を解く。 うまく行かない場合のグラフは、任意のminimalな分解がproblematic node を含む形になっている。 グラフ…

木幅が1のグラフの木分解と動的計画法

普通に木DPをします。 ei1333.hateblo.jp

DDCC2020参加記

NHK杯で羽生結弦を(オンサイトで)見ていたら予選出れなかった じょえくんとしてDDCCに参加していません— 卒論に内容はいらない!🐄 (@ei1333) January 25, 2020 うしくんもぐもぐ笑 これはなに? たぷりすたべる

Minimum Feedback Vertex Setの乱択アルゴリズム

Feedback Vertex Set (FVS)とは、グラフの頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。 最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知…

卒論名言集

1年前の卒論関連のSlackを見返していたらわりと面白かったのでまとめます ちなみに締切は2/1だったみたいです。 1/19 DDCCの装置実装部門の話で盛り上がっている 1/20 けんしん「またライブラリの闇と戦っていたら1日が終了しかけている」 1/21 (ラボ内締切…

define-by-runじゃないと困る問題

Hanjun-Daiのgraphnnがdefine-by-runじゃないせいで困った 複数グラフの、頂点ごとの確率を推論して、CrossEntropyしたい状況 batchあたりのlossを定義するために入力は複数グラフ(ひとつずつやってlossを足すということはできない) グラフごとにCrossEntrop…

強化学習アルゴリズム整理

久しぶりにPolicy Gradientやろうとしたら全部忘れていた DQN アルゴリズム とりあえずプレイアウトしてをreplay memoryに保存する と、そのステップ後のを取り出してきて、後者の価値を古いネットワークで推定し、そこからrewardを逆算した前者の価値に近づ…

Dynamic Connectivityについて

kopricky.github.io なんかやばすぎる記事を発見した。めっちゃ研究を追ってみたいけど人生が終了しそう

2020年の抱負

今年の目標は ICML/NeurIPS/AAAI/ICLRのどれかに通す グラフアルゴリズム系の学会のどれかに通す 強いメンタルをもつ です。がんばるぞ〜