論文の概要: Maximum Satisfiability of Simple Temporal Problems
- arxiv url: http://arxiv.org/abs/2607.23785v1
- Date: Sun, 26 Jul 2026 18:00:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:15.226799
- Title: Maximum Satisfiability of Simple Temporal Problems
- Title（参考訳）: 簡単な時間的問題に対する最大限の満足度
- Abstract要約: MAXSTP は W[1]-ハードパラメータを $n$ で表す。
また、MAXSTP の FPT アルゴリズムは、$k + vc$ などのパラメータで実現可能であることも示している。
- 参考スコア（独自算出の注目度）: 6.86481959784681
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables $n$ (instance scale), the maximum coefficient magnitude $k$ (numeric range), and structural parameters of the constraint graph such as treewidth $tw$ (decomposability) and vertex cover size $vc$ (density). We show that MAXSTP is W[1]-hard parameterized by $n$, implying that $n$ and parameters that depend on $n$ (including $tw$ and $vc$) are insufficient for fixed-parameter tractability. For combined parameters, we give an $O^*(k^n)$-time algorithm, yielding single-exponential solvability for fixed $k$. While $k+tw$ remains W[1]-hard, MAXSTP is in XP via an $O^*((n\cdot k)^{tw})$ algorithm. Our results suggest that MAXSTP is often computationally harder than optimizing qualitative CSPs. We verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by $n$ or $tw$. However, we also demonstrate that FPT algorithms for MAXSTP are indeed possible but with other parameters such as $k + vc$.
- Abstract（参考訳）: 単純な時間的問題(STP)は、時間的制約の定量化のための中核となるフレームワークである。
STPデータが矛盾する可能性があるため、MAXSTP: 制約の最大心性一貫した部分集合を計算する。
この拡張はNPハードであり、変数数$n$(インスタンススケール)、最大係数等級$k$(数値範囲)、木幅$tw$(分解性)、頂点カバーサイズ$vc$(密度)といった制約グラフの構造パラメータといった、実際に関係するインスタンスの特徴を捉える尺度の下でパラメータ化された複雑性を解析する。
MAXSTPは$n$でパラメータ化され、$n$と$n$に依存するパラメータ($tw$と$vc$を含む)は固定パラメータのトラクタビリティには不十分であることを示す。
組み合わせたパラメータに対しては、$O^*(k^n)$-timeアルゴリズムが与えられ、固定された$k$に対して単一指数可解性が得られる。
k+tw$ は W[1]-ハードのままであるが、MAXSTP は$O^*((n\cdot k)^{tw})$アルゴリズムで XP に含まれる。
その結果,MAXSTPは定性的CSPを最適化するよりも計算が難しいことが示唆された。
我々は、そのような問題(RCC-8 やアレン代数を含む)が $n$ あるいは $tw$ でパラメタ化されると FPT であることが検証される。
しかし、MAXSTP の FPT アルゴリズムは、$k + vc$ などの他のパラメータで実現可能であることも示している。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - On efficient robust regression with subquadratic samples [2.017649213266693]
ここでは,$widetildeO(d/4)$サンプルを用いたニア線形時間アルゴリズムが,$lesssim 1$条件下で予測誤差$O(sqrt)$を達成することを示す。
また、$lesssim 1$のような仮定がなければ、効率的なアルゴリズムには$tildeleft(mind22, 2d2right)$サンプルが必要であるという詳細な証拠を与える低次下界も証明する。
論文 参考訳（メタデータ） (2026-05-18T08:34:07Z) - Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
論文 参考訳（メタデータ） (2026-04-17T14:47:52Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology [0.0]
我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。
解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。
MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
論文 参考訳（メタデータ） (2023-12-15T09:42:46Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of
Random CSPs [4.023424709659175]
制約あたり$k$変数(k-CSP)によるランダム制約満足度問題の強い反響を証明する。
割当数$p$の制約で満たされたランダムk-CSPインスタンスの場合、最適値が最大値$p+O_k(epsilon)$の制約で満足する証明書を効率的に計算できる。
論文 参考訳（メタデータ） (2022-04-20T16:21:21Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。