その他の計算機科学 · 2026年9月27日(日)

分散計算、ゲーム理論、情報理論など。

arXiv cs.IT · math.CO · math.IT

A Continuous Projection Converse and a Weighted Construction for Uniquely Decodable Code Pairs

説明一意復号可能な符号対に対する連続射影の逆定理と重み付き構成

要約本論文は、一意復号可能な符号対の最大和レートを研究している。補集合接合構成を重み付きで改良し、長さ 672 で和レートが 1.318639029203 を超える明示的な符号を得ている。また、反復射影の議論を条件付きエントロピー評価と連続極限の正当化と組み合わせ、上界 1.480063425539 を与えている。

Lei Yu

arXiv cs.GT

On best of both worlds allocations with subadditive valuations

説明劣加法的評価関数の下で事前・事後の公平性を両立する配分

要約本論文は、権利が等しい主体に分割不可能な財を配分する問題で、評価関数が劣加法的な場合を扱う。ρ-MMS(最大最小シェア)配分を出力するアルゴリズムを、事後にρ-MMSを満たし、事前にはη-MES(最大期待シェア)を満たす乱択配分アルゴリズムへ変換する方法を提案する。著者らはηが少なくとも min[ρ/(2+ρ), 1/4] であることを示し、既存アルゴリズムへの適用結果も示している。

Uriel Feige

arXiv cs.DC

Adaptive Client Clustering and Coordination for Federated Learning Workflow Management in Edge Networks

説明エッジネットワークにおける連合学習ワークフロー管理のための適応的クライアントクラスタリングと協調手法(A-CoDa)

要約本論文は、エッジネットワーク上で依存関係を持つ連合学習のサービスフローを管理するための適応型フレームワーク A-CoDa を提案します。ラベル分布の乖離に基づいてクライアントをグループ化し、FedMIX が損失・遅延・不確実性によって参加者を選択します。さらに依存関係を考慮した DAG スケジューラが層ごとのタスク実行を調整します。手書き文字、ウェアラブルセンシング、商品画像、医用画像の各タスクでの実験により、端から端までの完了時間の短縮と、競争力のある精度の維持が示されています。

Jieping Luo, Qiyue Li, Yuxuan Chen ほか

arXiv math.CO · cs.IT · math.IT

Sunflowers of Reed--Solomon Codes

説明リード・ソロモン符号のサンフラワー:共通部分空間を持つ符号族の研究

要約本論文は、任意の二つの符号の共通部分が同一の固定部分空間となるリード・ソロモン符号の族「リード・ソロモン・サンフラワー」を提案し研究している。一般化されたV行列を用いた代数的判定基準を与え、計数と構成によって族の大きさを調べている。次元2では、すべての異なる符号がサンフラワーを形成し、その大きさを決定している。高次元では、再帰的構成と貪欲法による存在論証を示している。

Roni Con, Anina Gruica, Maria Montanucci ほか

arXiv cs.GT

Profit Reallocation Mechanisms in Tree-based Data Trading

説明木構造データ取引における利益再配分メカニズム

要約データは複製が容易で、購入者が加工して多数の下流買い手に転売するため、取引が木構造の連鎖を形成します。しかし上流の売り手は下流で生まれた価値を得られず、取引意欲が低下します。本論文は、木構造のデータ市場における利益再配分の枠組みとして、逐次的な取引ゲームと予算実行可能な再配分メカニズムを提案し、均衡を計算する効率的アルゴリズムを示します。理論分析と合成市場での実験により、均衡での取引量が増え、予算均衡の場合は社会厚生も改善することが示されています。

Yunxuan Ma, Wu Xin, Jichen Li ほか

arXiv cs.GT

Gaps and Augmentations in Bayesian Scheduling

説明ベイズ型スケジューリングにおけるギャップと資源拡張

要約本論文は、事前情報、ベイズ的インセンティブ両立性、ランダム化、機械側の資源拡張が、非関連機械上のメイクスパン最小化の近似比の限界をどう変えるかを研究しています。2台の機械に対するランダム化BIC機構の漸近下界は4/3であり、確定的機構との整数性ギャップは8/7と示されています。また、ジョブ割当が十分に分散している場合、O(m/ε)個のサンプル層で標準のMinWork機構が1+ε近似を達成できることが示されています。

Ahuva Mu'alem

arXiv cs.DC

Toward System-of-Systems Integration for Composable Cloud-HPC-Edge AI Platforms

説明クラウド・HPC・エッジを組み合わせ可能な AI プラットフォームのためのシステム・オブ・システムズ統合に向けて

要約現代の AI プラットフォームは、クラウドサービス、HPC ジョブ管理、クラウドネイティブなオーケストレーション、データ系、エッジ環境など、異なる前提で設計された基盤を組み合わせることが増えています。本論文は、独立して有用なシステムがそれぞれの制御・ライフサイクル・故障特性を保ちつつ、上位の AI プラットフォーム機能に寄与する構成を、システム・オブ・システムズ(SoS)として捉えることを提案します。対等な構成システムの視点、境界判定の方法、七つの統合インターフェース、横断的ワークフローの例を示し、相互運用性やガバナンス、可観測性の評価に用いる証拠の類型と研究課題を挙げています。

Sumit Rakesh, Rajkumar Saini

arXiv cs.IT · math.IT

Geometry-Aware Multi-UAV Full-Duplex Communication: System Design and Experiment

説明幾何情報を考慮した複数UAVの全二重通信:システム設計と実験

要約本論文は、高利得指向性アンテナと上り・下りチャネルの分離を用いて自己干渉を制御可能な同一チャネル干渉に変換する、幾何情報を考慮した複数UAVの帯域内全二重(MU-IBFD)通信システムを提案します。UAV上で電力消費の大きい自己干渉キャンセラを不要にする点が特徴です。著者らは幾何を考慮した干渉モデルを導出し、3次元空域でSINR要件を満たす信頼動作領域(ROR)を定義しています。2機のUAVと地上局からなる試作機で実地試験を行い、ほとんどの空域で下りの容量が理想的な全二重に近いことを示しました。

Tao Yu, Kiyomichi Araki, Tomohiro Mogi ほか