-
xhl_kogitsune
- 1924
- 0
- 0
- 0
-
- いいね！0
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
右側のセッション全く理解できなくてつらいw #air_STACS
2012-03-01 19:34:45
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
@ir5 http://t.co/fpKY6GxO 参加しましょう!!!
2012-03-01 19:35:16
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
. @kinaba 先生が普通に読んでてﾔﾊﾞｲ #air_STACS
2012-03-01 19:43:16
kinaba
@kinaba
#air_STACS では https://t.co/sL20KegD の論文を現地で開催されているはずの時間に合わせて読んでエア実況をしております（説明口調）
2012-03-01 19:50:54
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Preemptive and Non-Preemptive Generalized Min Sum Set Cover #air_STACS
2012-03-01 20:03:46
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Non-Preemptive Generalized Min Sum Set Cover: n個の要素と、その部分集合{Si}とk(Si)が与えられた時、n個の要素を並び替えて、最初からti個の要素までにSiの要素がk(Si)個以上あるようなtiの和を最小化 #air_STACS
2012-03-01 20:06:12
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
で、preemptive版は並び替えが整数個以下の単位でできる、と。 #air_STACS
2012-03-01 20:08:10
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
preemptiveで近似比2アルゴリズム、preemptive->nonpreemptiveの変換方法(但し和は最大6.1倍大きくなる)、よってnonpreemptiveの近似比12.6(既存のは28)。 #air_STACS
2012-03-01 20:09:22
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
なんか問題だけ理解して終了の感があってヤバイw #air_STACS
2012-03-01 20:10:20
kinaba
@kinaba
#air_STACS なんとかかんとかセットカバーというのは問題はabstに書いてある通りで、LP！最大フロー！ランダマイズド！と頑張ると素晴らしい定数近似値比のアルゴリズムが出たらしい
2012-03-01 20:14:54
kinaba
@kinaba
#air_STACS 、エアPOPLよりは自分はだいぶ理解できるんだけど他人に意味がわかるように140文字以内で発言するのが至難を極める。
2012-03-01 20:11:47
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Ehrenfeucht-Fraïssé goes elementarily automatic: 分からんorz #air_STACS
2012-03-01 20:16:15
kinaba
@kinaba
#air_POPL Ehrenfeucht-Fraïssé Game ってなんだっけ、あっちとこっちに石置き合うやつだっけ。Gameって書いてある論文は他の全ての単語と比べて難易度高い気がするのでいつも恐れおののいている気がしますね
2012-03-01 19:53:14
kinaba
@kinaba
#air_STACS 「オートマトンで表せるハイパーグラフ（頂点＝文字列、辺＝文字の組上の正規言語）のbounded degreeな奴上の一階述語論理が3EXPTIMEとか」グラフ同士の同値を格好良く定めるE-F relをautomatic構造に格好良く応用したのが格好いいっぽい
2012-03-01 20:06:14
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
LP can be a cure for Parameterized Problems: vertex coverをO^*(2.6181^(k-u))時間で解く。uは最小vertex cover sizeのLP緩和解。k以下のv.c.の存在問題 #air_STACS
2012-03-01 20:28:01
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
それ自体はbranch-and-boundで、むしろ計算量評価(k-uがbranch-and-bound中に減少するとは限らない)に力入れたのかな。他の問題に応用して色々計算量下げたらしい。 #air_STACS
2012-03-01 20:29:14
kinaba
@kinaba
#air_STACS 整数計画を線形計画に緩和して解いた緩和解との差をパラメタにした計算量でvertex covertとか色々解くとか。これも結構面白い気がする。こっち方面全然知らないので新規性とかがよくわからないが。LP後の実装も重くなさそうなので実用的にどんなもんなんだろう。
2012-03-01 20:43:48
kinaba
@kinaba
#air_STACS Field of Reals is not omega-Automatic これは面白かった。あとでちゃんと読もう。標数0の体がオートマトンメソッドで扱えるとするとなんかの同値類が有限個になるはずなんだけどならない矛盾みたいな証明。
2012-03-01 20:28:36
kinaba
@kinaba
#air_POPL 「実数の加減乗除に関する論理は決定可能であることが（自然数だと無理なのに！）TarskiのQEという方法でできると知られてますが、論理の決定可能性というとオートマトンに落とすオートマトン狂メソッドも有名ですがそっちの手法ではできないの！？→できない」という論文
2012-03-01 20:20:36
Ikegami Daisuke
@ikegami__
#air_STACS The field of Reals is not omega-automatic についての補足ですが、(R, +) や (R, ・) は ω-automatic なのだけれど、(R, +, ・) についてはそうでないということがわかりましたよという論文
2012-03-01 20:25:28
kinaba
@kinaba
@ikegami__ ある種の Abelian group のある種の等差数列がどうこうという定理 [Freiman66] が重要みたいなことが書いてあります（代数の香りを匂わせて @ikegami__ さんに詳細を読ませようメソッド
2012-03-01 20:31:31
Ikegami Daisuke
@ikegami__
@kinaba [Freiman 66] in russian って書いてあるので原典をあたるのは僕には無理ぽいので解説（３節）読まないといけないですね
2012-03-01 20:39:56