本サイトは 12 時間以上更新されていません（通常は 3 時間ごと）。以下の内容は最新でない可能性があります。
このページに条件に合う項目はありません（絞り込みはこのページ内のみ）。
説明0.55を超える、オンライン辺重み付きマッチングの改善
要約本論文は、自由な破棄（free disposal）を許す辺重み付きオンライン二部マッチングに対し、競合比0.556195の乱択アルゴリズムを提案している。Blanc と Charikar による従来の0.5368を上回る結果である。アルゴリズムはオンライン相関選択（online correlated selection）を基礎とし、状態依存の原始・双対解析によって証明される。一部の選択不等式は計算機支援証明で検証され、検証プログラムは付属のリポジトリで公開されている。三角形の単位重み入力では、理想アルゴリズムの保証に漸近的に到達することが示され、解析が厳密であることが確認されている。
注目点辺重み付きオンライン二部マッチングの競合比を0.556へ改善し、状態依存の原始双対解析と計算機支援証明を示す。タイトな界を与える。
説明マトロイドとXOS評価関数に対する予言者秘書問題：1-1/eでの厳密な分離
要約本論文は、要素の非負の価値が独立に抽出され、ランダムな順序で到着する状況でのオンライン割当問題を扱う。アルゴリズムは独立集合または買い手ごとの束を選び、ベンチマークは離散最適解の期待値である。マトロイドについては、任意のマトロイドに対して(1-1/e+10^-6)競合比の乱択アルゴリズムを与え、多項式時間で実行できることを示す。一方、XOS評価関数を持つ組合せオークションでは、1-1/eが最適な競合比であることを示し、両者の間に厳密な分離があることを明らかにする。
注目点マトロイド預言者秘書問題で1-1/eを上回る比率を示し、XOS拍卖では1-1/eが最適となる紧界を与える。理論的貢献が大きい。
説明制約付き重み付きネットワークゲームにおける安定性と完全性：資源と容量の制約のもとでネットワーク形成の安定ネットワークの存在と精緻化概念を扱う研究。
要約本論文は、任意の連合に連続的な重みを割り当てるとともに、連合の容量制約と個人の予算制約を組み込んだ、制約付き重み付きネットワーク形成の枠組みを提案します。連合単位の安定性（coalitionwise stability）という新しい安定性概念を定義し、利得関数の連続性と成分ごとの準凹性の仮定のもとで、そのような安定ネットワークの存在を示します。さらに、ゼルテンの完全均衡とペアワイズ完全安定性に着想を得た精緻化を検討し、成分ごとの単調性の仮定のもとで2つの定式化が同値であることを示します。
説明分数的および乱択化された真実性スケジューリングの厳密な下界
要約本論文は、非関連機械上の真実性スケジューリング問題を扱い、任意の決定的な真実性分数スケジューリング機構の最悪ケース近似比が少なくとも(n+1)/2であることを示します。この下界は既知の上界と厳密に一致します。期望で真実性を満たす機構から真実性分数機構が導かれるため、この下界は期待真実機構および普遍的真実機構にも適用されます。さらに近似比n/2+o(n)の普遍的真実機構を与え、乱択化真実スケジューリングの最適な主要定数が1/2であることを確立します。
注目点アルゴリズム的メカニズム設計の長年の未解決問題に取り組み、確定的な真実性を持つ分数スケジューリングの近似比が少なくとも(n+1)/2であることを示し、ランダム化の紧界も与えている。
説明flash-comm：LLMデコーディング向けの自己同期型集団通信
要約本論文は、LLMデコーディングの効率的なデータ転送を実現する通信ライブラリflash-commを提案している。各データブロックが自身の準備完了の証拠を持つ自己同期型転送により、GPU間の個別バリアなしで受信側が必要なブロックを直接検証できる。8基のNVIDIA B300 GPUを搭載したサーバーでは、最先端のall-reduce実装であるcustom AR v2と比べ、all-reduceの遅延中央値が28.8%、最大43.7%削減された。エンドツーエンドのデコーディングでは、出力トークンあたりの時間（TPOT）が1.7〜6.8%削減された。