-
xhl_kogitsune
- 1921
- 0
- 0
- 0
-
- いいね！0
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
アッAir STACS 始まってるじゃないですかァァァァ! #air_STACS http://t.co/fpKY6GxO
2012-03-01 17:49:24
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
13/9-approximation for Graphic TSP. graphic TSPの13/9=1.444近似アルゴリズムの提案。既存手法は30年前に1.5(一般のTSP), 最近1.461(graphic)。 #air_STACS
2012-03-01 18:53:10
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
graphic TSPとは2点間の距離が無向グラフ上のshortest path長であるような場合で、TSPの難しいインスタンスを含んでいると思われている。#air_STACS
2012-03-01 18:53:15
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Lower Bounds on the Complexity of MSO1 Model-Checking: MSO1 Model-CheckingはXPではない。MSO2 Model-CheckingがXPでない(ETH仮定)のは既知。 #air_STACS
2012-03-01 18:53:26
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
XPとはThe class of decision problems of the form (x,k) (k a parameter) that are solvable in time O(|x|f(k)) for some function f #air_STACS
2012-03-01 18:53:39
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Exponential time hypothesis (ETH) は3-SATが最悪時subexponential時間では解けないという仮説 http://t.co/kRuld6KZ #air_STACS
2012-03-01 18:53:44
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem: 組み合わせ最適化オンリー(線形計画法不要)、最大重み完全マッチングだけで動く近似MAX ATSPアルゴリズム#air_STACS
2012-03-01 18:59:06
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
ヤバイ、air POPLに比べてかなり理解度が低いwww #air_STACS
2012-03-01 18:59:58
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Weak MSO+U over infinite trees: "unboundingな量化子U【何】で拡張されたWeak MSO Logic【何】は無限木【何】上【何】で充足可能性が決定可能。" abst全く理解できない… #air_STACS
2012-03-01 19:03:24
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
これって@iwiwiせんせーとか@wata_orzせんせーとかそのあたり召喚すればよかったのか?(ﾁﾗﾁﾗｯ http://t.co/fpKY6GxO #air_STACS
2012-03-01 19:09:47
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Conflict-free Chromatic Art Gallery Coverage: 多角形内に、どの多角形上の点も1人以上のガードマンから見えるように配置します→floor(n/3)人が十分(場合によっては必要)[既存] #air_STACS
2012-03-01 19:18:30
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
どの点からも、見えるガードマン全員の色が違うようにガードマン彩色したい→O(n)色(一般)乃至O(sqrt(n))色(orthogonalな多角形)必要[既存]。色は無線周波数とかの応用が利く。 #air_STACS
2012-03-01 19:20:05
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
どの点からも、見えるガードマンのうち、他の見えるガードマンとは違う色の人が1人以上存在するようにガードマン彩色したい→O(log^2 n)色(一般)乃至O(log n)色(orthogonalまたは単調な多角形)必要[本研究]。色の数減らせたやったね! #air_STACS
2012-03-01 19:21:07
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Complexity Zoo http://t.co/tgJBh2P2 必須 #air_STACS
2012-03-01 19:28:14
kinaba
@kinaba
#air_STACS 「多角形の全域カバーする色つき監視点を置く、でも同色の監視点が複数みえる位置があっちゃダメ。最小何色？→O(log^2 n)」90度多角形の場合90度回る木みたいの作る、あまり凹すぎない場合でかい部分の縁を切って再帰塗りでlog n、てのをも一歩頑張る
2012-03-01 19:29:19
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Concurrency Makes Simple Theories Hard: HM logic【何】, EF-logic【何】の計算量が並行システムモデルにするとPSPACEから非ELEMENTARYに跳ね上がることを証明。 #air_STACS
2012-03-01 19:33:59
kinaba
@kinaba
#air_STACS abstしか読んでないけどイベント列1個に対するモデル検査がPSPACEのロジックでもイベント列n個のshuffle演算に対するモデル検査だとnon-elementaryになりえます、とかかな。そりゃそうでは。（ちゃんと読みます）
2012-03-01 19:31:39
kinaba
@kinaba
#air_STACS あ、n個じゃなくて2個の積でnonelementaryになるのか。へー。「プロセスの状態遷移図的なもの(スタックの状態遷移で表す)(BPA)の性質を表す割と単純なロジック(くりーね*だけある様相論理)(EF-logic)の真偽値評価はプロセス2本で凄く難い」
2012-03-01 19:40:19