The Complexity of Distance- Dominating Set Reconfiguration
本論文は、距離支配集合再構成問題について、の場合に分割グラフ上で多項式時間アルゴリズムを構築し複雑性の二項性を示す一方、平面グラフや二部グラフ、弦グラフなど他のグラフクラスではで完全であることを証明する結果を報告しています。
💻 Category
cs.DS
91 件の論文
Weighted Reservoir Sampling With Replacement from Data Streams
この論文は、データストリームから重みに比例した確率で要素を復元抽出する新しい手法を提案し、その正当性と効率性を理論的に証明するとともに、実験を通じて既存手法との性能比較を行ったものである。
Efficient Computation of Time-Index Powered Weighted Sums Using Cascaded Accumulators
この論文は、大規模なデータブロックの保存や多数の乗算を不要とし、カスケード型アキュムレータを用いることで、時間インデックスのべき乗が重み付けされた和を極めて効率的に計算する新規手法を提案しています。
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
本論文は、正の排他的制約付き最短経路問題の固定パラメータ tractability を研究し、解のサイズや制約グラフの構造的性質といったパラメータ化に対して、多項式サイズのコア化や固定パラメータ可決性アルゴリズムを確立するものである。
Concurrent Deterministic Skiplist and Other Data Structures
本論文は、NUMA 環境における並行決定性スキップリストの設計・分析・性能評価に加え、ロックフリーキューやハッシュテーブルの実装を Intel TBB と比較し、メモリアクセスパターンに応じたメモリ管理戦略や階層的なデータ構造の活用を通じて、リモート NUMA ノードからのアクセスを削減しメモリアクセス遅延を改善する手法を提案しています。
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
この論文は、任意の固定グラフ H に対して P_5 自由グラフ上の最大部分リスト H 彩色問題が多項式時間で解けることを示し、Agrawal らの SODA 2024 における未解決問題を解決するとともに、Chudnovsky らの SIDMA 2021 の結果を多項式時間アルゴリズムに改善したものである。
Differentially Private and Scalable Estimation of the Network Principal Component
この論文は、実グラフにおける局所感度と大域感度の差を利用した「提案・テスト・公開（PTR）」フレームワークを提案し、エッジ差分プライバシーを維持しつつ、非公開の主成分分析と同等の計算時間で高品質な結果を得られるスケーラブルな手法を開発し、密な-部分グラフ問題への応用も可能にしたことを述べています。
Bounds for the Permutation Flowshop Scheduling Problem: New Framework and Theoretical Insights
本論文は、行列定式化に基づき新しい枠組みを提案し、多項式時間で計算可能な経路集合を用いてパーミュテーションフローショップスケジューリング問題の上下界を導出することで、主要なベンチマークインスタンスの多くにおいて既存の境界値を改善し、タイルードの予想や漸近的近似比に関する理論的洞察をもたらすものである。
No exponential quantum speedup for anymore
2021 年に Chen らが提案した平均ケースの-Short Integer Solution（）問題に対する効率的な量子アルゴリズムは、本論文で提示された効率的な古典アルゴリズムにより、もはや指数関数的な量子高速化をもたらさないことが示されました。
An Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
この論文は、非減少価格条件下の 1 ブレークポイント全単位数量割引を伴う単一製品ロットサイズ問題を扱い、最適解の新たな性質を確立して 時間のハイブリッド動的計画法を開発し、既存の 時間アルゴリズムを改善したことを示しています。
Towards an algebraic approach to the reconfiguration CSP
本論文は、古典的な CSP の複雑性解析で用いられる手法に触発され、等式制約を含む還元を捉えるために全操作ではなく部分操作を採用する新たな代数的アプローチを提案し、ブール領域からより一般的な設定へと RCSP（再構成可能制約充足問題）の複雑性結果を拡張するものである。
Approximation Algorithms for the -Matching and List-Restricted Variants of MaxQAP
本論文は、最大二次割り当て問題（MaxQAP）の二つの自然な一般化であるリスト制限版と-マッチング版に対して、それぞれおよびの近似アルゴリズムを提案し、これらが既存の最良の近似率と漸近的に一致する初の近似アルゴリズムであることを示しています。
Robust Permutation Flowshops Under Budgeted Uncertainty
本論文は、各機械で最大限に所定数のジョブ処理時間が変動する予算型不確実性モデル下のロバスト順次フローショップ問題を、多項式個の名义問題の求解に帰着させることで、2 機械の場合に多項式時間で解き、任意の固定された機械数に対して多項式時間近似が可能であることを示しています。
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
本論文は、補助的な予測情報を活用しつつもその精度に依存せず頑健性を保つ「予測拡張分布テスト」の枠組みを提案し、離散分布および高次元多変量分布の独立性検定において、予測誤差に応じてサンプル複雑度を最適に削減するアルゴリズムと、その一致する下限を導出するものです。
Generalizing Fair Top- Selection: An Integrative Approach
本論文は、複数の保護グループを考慮した公平なトップ選択問題において、参照スコア関数からの乖離を最小化する課題の計算複雑性を分析し、特定の条件下で効率的なアルゴリズムを導出するとともに、重みの摂動に対して安定したスコア関数を得るための新たな「有用性損失」指標を導入し、実データを用いた実験でその有効性を示す統合的なアプローチを提案する。
Quantum Algorithms for Network Signal Coordination
この論文は、NP 完全問題であるネットワーク信号調整（NSC）問題およびその頑健な定式化に対して、グローバーの探索アルゴリズムを適用して二次的な高速化を実現し、そのシミュレーションおよび実量子コンピュータ上での実装を示したものである。
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
本論文は、単位ディスクグラフの幾何学的性質を考慮した「ディスクスケーリング」操作を、半径を固定する既存モデルから区間内での選択を許容する一般化モデルへ拡張し、クラスグラフや完全グラフなど特定のグラフクラスにおける計算複雑性（NP 困難性、多項式時間解法、FPT、W[1]-困難性など）を明らかにするとともに、既存研究の未解決問題を解決したことを示しています。
Generalized matching decoders for 2D topological translationally-invariant codes
本論文は、トーリック符号との等価性を利用し、2 次元トポロジカル並進対称符号を粗視化してグラフマッチング法で復号する手法を開発し、その誤り訂正能力と実用的な符号容量閾値の存在を証明するとともに、双変数自転車符号に対する数値実験で高性能な復号器との同等の性能を実証したものである。
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 な複雑性を決定づけたものである。
Finding Short Paths on Simple Polytopes
この論文は、単体多面体上の線形計画問題における最短単調経路や単体法による最適基底への最短ピボット列の計算が NP 困難であることを示すとともに、単体多面体の直径計算も NP 困難であることを証明し、一方で任意の多面体間の線形長経路を多項式時間で発見できる小さな拡張定式化の存在を示すものである。