論文の概要: A Fast Algorithm for Consistency Checking Partially Ordered Time

• arxiv url: http://arxiv.org/abs/2305.15917v1
• Date: Thu, 25 May 2023 10:36:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 15:46:26.613380
• Title: A Fast Algorithm for Consistency Checking Partially Ordered Time
• Title（参考訳）: 部分順序付き時間の一貫性チェックのための高速アルゴリズム
• Authors: Leif Eriksson and Victor Lagerkvist
• Abstract要約: イベントシステムの(おそらく不完全な)記述が一貫したものであるかどうかを判断する問題を考える。 この問題の古典的な複雑さは完全に解決されているが、POTの微細な複雑さについてはほとんど分かっていない。 ランタイムを$O*((0.26n)n)$でバウンドしたより高速なアルゴリズムを構築する。
• 参考スコア（独自算出の注目度）: 9.594432031144716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Partially ordered models of time occur naturally in applications where agents or processes cannot perfectly communicate with each other, and can be traced back to the seminal work of Lamport. In this paper we consider the problem of deciding if a (likely incomplete) description of a system of events is consistent, the network consistency problem for the point algebra of partially ordered time (POT). While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT except that it can be solved in $O^*((0.368n)^n)$ time by enumerating ordered partitions. We construct a much faster algorithm with a run-time bounded by $O^*((0.26n)^n)$. This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded toward a solution. While similar ideas have been explored earlier for related problems it turns out that the analysis for POT is non-trivial and requires significant new ideas.
• Abstract（参考訳）: 部分的に順序付けられた時間のモデルは、エージェントやプロセスが互いに完全に通信できないアプリケーションで自然に起こり、ランポートの独創的な仕事まで遡ることができる。 本稿では,イベントのシステムを記述する(おそらく不完全)記述が一貫性があるかどうかを決定する問題,半順序時間(pot)の点代数におけるネットワーク一貫性問題を考える。 この問題の古典的な複雑性は完全に解決されているが、順序分割を列挙することで、$O^*((0.368n)^n)$時間で解けること以外は、POTの微細な複雑さについてほとんど知られていない。 ランタイムを$O^*((0.26n)^n)$でバウンドしたより高速なアルゴリズムを構築する。 これは全順序に類似した構造を高度に列挙することで達成され、解に対して優しく拡張される。 類似したアイデアは、関連する問題に対して以前にも検討されているが、POTの分析は非自明であり、重要な新しいアイデアを必要とすることが判明した。

関連論文リスト

• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
  EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。 EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。 我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
  論文  参考訳（メタデータ） (2024-05-16T15:11:37Z)
• Scalable network reconstruction in subquadratic time [0.0]
  本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。 我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。 本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
  論文  参考訳（メタデータ） (2024-01-02T19:00:13Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
  Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。 Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。 本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-29T05:30:54Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。