Approximation Algorithms for the -Matching and List-Restricted Variants of MaxQAP
本論文は、最大二次割り当て問題（MaxQAP）の二つの自然な一般化であるリスト制限版と-マッチング版に対して、それぞれおよびの近似アルゴリズムを提案し、これらが既存の最良の近似率と漸近的に一致する初の近似アルゴリズムであることを示しています。
💻 Category
cs.DM
48 件の論文
Robust Permutation Flowshops Under Budgeted Uncertainty
本論文は、各機械で最大限に所定数のジョブ処理時間が変動する予算型不確実性モデル下のロバスト順次フローショップ問題を、多項式個の名义問題の求解に帰着させることで、2 機械の場合に多項式時間で解き、任意の固定された機械数に対して多項式時間近似が可能であることを示しています。
Positional s-of-k games
この論文は、勝つ集合の特定の要素数を獲得することで得点が入る「s-of-k ゲーム」という新しい位置ゲームの枠組みを提案し、最適戦略およびペアリング戦略に制限された場合の得点を、三角・正方形・菱形・六角形のグリッド上で包括的に分析している。
Minimal toughness in subclasses of weakly chordal graphs
この論文は、弱弦性グラフのいくつかの部分クラス（補グラフの直径が 3 以上の補弦性グラフ、ネット非存在補弦性グラフ、森林の補グラフ、-自由グラフ、完全多部グラフなど）における最小タフネスグラフの完全な分類を行い、既存の 2 つの結果に対する簡明な証明も提供しています。
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
平面点集合における平面スパンニングツリーの再構成（フリップ）に関する最短系列の構造を研究し、「ハッピーエッジ予想」は支持しつつ、「パーキングエッジ予想」と「リパーキング予想」の一般設定における成立を反証した。
Algebraic Characterization of Reversible First Degree Cellular Automata over
この論文は、任意のセル数を持つ有限一次元セルオートマトンの可逆性を定数時間で判定し、すべての可逆ルールを合成するための、パラメータ値に関する 3 つの代数的条件を導出する手法を提案しています。
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
この論文は、有界木幅の複体における最適モーシュマッチング問題に対して、$2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}$ 時間での解決が不可能であることを示すことで、この問題の ETH-tight な複雑性を決定づけたものである。
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
本論文は、 個の任意のマトロイド制約の交差下での非負単調サブモジュラ関数の最大化問題に対し、自然な貪欲法が保証する倍近似を初めて超える乗法的改善（約$0.819kk$-パリティ制約にも適用可能であることを示しています。