論文の概要: Improved Algorithms for Allen's Interval Algebra by Dynamic Programming
with Sublinear Partitioning
- arxiv url: http://arxiv.org/abs/2305.15950v1
- Date: Thu, 25 May 2023 11:45:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 15:27:06.473769
- Title: Improved Algorithms for Allen's Interval Algebra by Dynamic Programming
with Sublinear Partitioning
- Title（参考訳）: 部分線形分割を用いた動的プログラミングによるアレン区間代数のアルゴリズムの改良
- Authors: Leif Eriksson and Victor Lagerkvist
- Abstract要約: アレンの区間代数は質的時間的推論において最もよく知られた計算の1つである。
NPハードな定性推論問題を解くための新しい枠組みを提案する。
我々はアレンの区間代数に対して$O*((fraccnlogn)n)$の大きな改善を得る。
- 参考スコア（独自算出の注目度）: 9.594432031144716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Allen's interval algebra is one of the most well-known calculi in qualitative
temporal reasoning with numerous applications in artificial intelligence.
Recently, there has been a surge of improvements in the fine-grained complexity
of NP-hard reasoning tasks, improving the running time from the naive
$2^{O(n^2)}$ to $O^*((1.0615n)^{n})$, with even faster algorithms for unit
intervals a bounded number of overlapping intervals (the $O^*(\cdot)$ notation
suppresses polynomial factors). Despite these improvements the best known lower
bound is still only $2^{o(n)}$ (under the exponential-time hypothesis) and
major improvements in either direction seemingly require fundamental advances
in computational complexity. In this paper we propose a novel framework for
solving NP-hard qualitative reasoning problems which we refer to as dynamic
programming with sublinear partitioning. Using this technique we obtain a major
improvement of $O^*((\frac{cn}{\log{n}})^{n})$ for Allen's interval algebra. To
demonstrate that the technique is applicable to more domains we apply it to a
problem in qualitative spatial reasoning, the cardinal direction point algebra,
and solve it in $O^*((\frac{cn}{\log{n}})^{2n/3})$ time. Hence, not only do we
significantly advance the state-of-the-art for NP-hard qualitative reasoning
problems, but obtain a novel algorithmic technique that is likely applicable to
many problems where $2^{O(n)}$ time algorithms are unlikely.
- Abstract（参考訳）: アレンの区間代数は質的時間推論で最もよく知られた計算の1つであり、人工知能に多くの応用がある。
最近、npハードな推論タスクのきめ細かい複雑さが大幅に改善され、naive $2^{o(n^2)}$ から $o^*((1.0615n)^{n})$ への実行時間が改善され、単位間隔のより高速なアルゴリズムでも重複区間の有界な数($o^*(\cdot)$表記は多項式因子を抑制する)。
これらの改善にもかかわらず、最もよく知られた下限は(2^{o(n)$(指数時間仮説)であり、どちらの方向でも大きな改善は計算複雑性の根本的な進歩を必要とするように見える。
本稿では,線形分割を用いた動的プログラミングと呼ぶNP-hard質的推論問題を解くための新しい枠組みを提案する。
この手法を用いることで、アレンの区間代数に対して$O^*((\frac{cn}{\log{n}})^{n})$の大きな改善が得られる。
この手法がより多くの領域に適用可能であることを示すために、定性的空間的推論(英語版)における問題、基方向点代数(英語版)に適用し、$O^*((\frac{cn}{\log{n}})^{2n/3})$時間で解く。
したがって、NPハード質的推論問題に対する最先端の問題を著しく前進させるだけでなく、2$2^{O(n)}$タイムアルゴリズムが不可能な多くの問題に適用可能な新しいアルゴリズム技術を得る。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。
これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
論文 参考訳（メタデータ） (2024-09-19T21:40:57Z) - Second-order optimization with lazy Hessians [55.51077907483634]
一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。
我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:26Z) - A Multivariate Complexity Analysis of Qualitative Reasoning Problems [9.594432031144716]
我々は、それぞれ$f(k) cdot 2O(n)$, $f(k)n$, timeで解ける問題のクラス FPE と XE を紹介する。
有効幅$k$の部分順序時間問題は16kn$時間で解決可能であり,XEに含まれることを示す。
また、アレンの区間代数のネットワーク整合性問題は、$k$以上と重複しないが、$(2nk)2k cdot 2n$ timeで解決可能であり、その中に含まれることを示す。
論文 参考訳（メタデータ） (2022-09-30T07:29:53Z) - An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem [2.1485350418225244]
線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。
PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
論文 参考訳（メタデータ） (2022-03-02T01:16:10Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Solving Infinite-Domain CSPs Using the Patchwork Property [17.101875753030754]
制約問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。
非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。
基本関係がパッチワーク特性を持つCSPに対して、これを$f(w)cdot nO(1)$に制限する。
論文 参考訳（メタデータ） (2021-07-03T13:04:41Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。