論文の概要: Solving the Workflow Satisfiability Problem using General Purpose Solvers

• arxiv url: http://arxiv.org/abs/2105.03273v1
• Date: Fri, 7 May 2021 13:59:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-10 12:11:13.791961
• Title: Solving the Workflow Satisfiability Problem using General Purpose Solvers
• Title（参考訳）: 汎用解を用いたワークフロー満足度問題の解法
• Authors: Daniel Karapetyan and Gregory Gutin
• Abstract要約: 満足のいく問題(WSP)は、ワークフローのあらゆるステップに承認されたユーザーの割り当てを求めるアクセス制御においてよく研究された問題です。 非ui制約を効率的に処理するために,制約の分岐係数の概念を導入する。 汎用ソルバが任意の制約でWSP上でFPTライクな性能を達成できることを実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The workflow satisfiability problem (WSP) is a well-studied problem in access control seeking allocation of authorised users to every step of the workflow, subject to workflow specification constraints. It was noticed that the number $k$ of steps is typically small compared to the number of users in the real-world instances of WSP; therefore $k$ is considered as the parameter in WSP parametrised complexity research. While WSP in general was shown to be W[1]-hard, WSP restricted to a special case of user-independent (UI) constraints is fixed-parameter tractable (FPT). However, restriction to the UI constraints might be impractical. To efficiently handle non-UI constraints, we introduce the notion of branching factor of a constraint. As long as the branching factors of the constraints are relatively small and the number of non-UI constraints is reasonable, WSP can be solved in FPT time. Extending the results from Karapetyan et al. (2019), we demonstrate that general-purpose solvers are capable of achieving FPT-like performance on WSP with arbitrary constraints when used with appropriate formulations. This enables one to tackle most of practical WSP instances. While important on its own, we hope that this result will also motivate researchers to look for FPT-aware formulations of other FPT problems.
• Abstract（参考訳）: ワークフロー満足性問題(workflow satisfiability problem, wsp)は、ワークフロー仕様の制約に従うワークフローの各ステップに権限のあるユーザの割り当てを求めるアクセス制御において、よく研究されている問題である。 WSPの現実世界のインスタンスのユーザ数と比較すると、通常$k$のステップ数は小さいため、WSPパラメトリド複雑性研究のパラメータとして$k$が考慮されている。 WSPは一般にW[1]ハードであることが示されているが、ユーザ非依存(UI)の制約が固定パラメータ(FPT)であることに制限されている。 しかし、ui制約の制限は実用的でないかもしれない。 非ui制約を効率的に処理するために,制約の分岐係数の概念を導入する。 制約の分岐係数が比較的小さく、UI以外の制約の数が妥当である限り、WSPはFPT時間で解決できる。 Karapetyanらによる結果の拡張。 (2019) では, 適切な定式化を用いた場合, 任意の制約でWSP上でFPTライクな性能を達成できることが実証された。 これにより、実用的なWSPインスタンスのほとんどに取り組むことができます。 それ自体は重要であるが、この結果が、他のFPT問題のFPT対応式を探す動機になることを期待している。

関連論文リスト

• Constrained Reinforcement Learning with Smoothed Log Barrier Function [27.216122901635018]
  CSAC-LB (Constrained Soft Actor-Critic with Log Barrier Function) と呼ばれる新しい制約付きRL法を提案する。 線形スムーズなログバリア関数を追加の安全評論家に適用することにより、事前トレーニングなしで競争性能を達成する。 CSAC-LBでは,様々な難易度を有する制約付き制御タスクにおいて,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2024-03-21T16:02:52Z)
• From Instructions to Constraints: Language Model Alignment with Automatic Constraint Verification [70.08146540745877]
  NLPタスクの共通制約を調査し、それらの引数の型に基づいて、それらを3つのクラスに分類する。 本稿では,ACT(ConsTraintsのアラインメント)という統合フレームワークを提案し,制約に適応したユーザアライメントのための監視信号を自動的に生成する。
  論文  参考訳（メタデータ） (2024-03-10T22:14:54Z)
• Federated Knowledge Graph Completion via Latent Embedding Sharing and Tensor Factorization [51.286715478399515]
  FLEST(Federated Latent Embedding Factorization)は、KGの完全化にFederated Factorizationを用いた新しい手法である。 FLESTは埋め込み行列を分解し、潜伏辞書の埋め込みを共有することでプライバシーリスクを低減している。 実証的な結果はFLESTの有効性と効率を示し、パフォーマンスとプライバシのバランスのとれたソリューションを提供する。
  論文  参考訳（メタデータ） (2023-11-17T06:03:56Z)
• Unlocking the Potential of Prompt-Tuning in Bridging Generalized and Personalized Federated Learning [49.72857433721424]
  Vision Transformer (ViT) と Visual Prompt Tuning (VPT) は、様々なコンピュータビジョンタスクの効率を改善して最先端のパフォーマンスを実現する。 本稿では,GFL(Generalized FL)とPFL(Personalized FL)を組み合わせた新しいアルゴリズムSGPTを提案する。
  論文  参考訳（メタデータ） (2023-10-27T17:22:09Z)
• Federated Learning with Convex Global and Local Constraints [4.094311966028137]
  実際には、多くの機械学習(ML)問題には制約が伴い、適用されたドメインには、他の人と共有できない分散機密データが含まれる。 本稿では,近似ラグランジアン(AL)法に基づくML問題に対する新しいFLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-16T06:51:32Z)
• Flexible and Robust Counterfactual Explanations with Minimal Satisfiable Perturbations [56.941276017696076]
  我々は、最小満足度摂動(CEMSP)を用いた対実的説明法という概念的に単純だが効果的な解を提案する。 CEMSPは、意味論的に意味のある正常範囲の助けを借りて、異常な特徴の値を変更することを制限している。 既存の手法と比較して、我々は合成データセットと実世界のデータセットの両方で包括的な実験を行い、柔軟性を維持しつつ、より堅牢な説明を提供することを示した。
  論文  参考訳（メタデータ） (2023-09-09T04:05:56Z)
• Computing unsatisfiable cores for LTLf specifications [3.251765107970636]
  有限トレース上の線形時間時間時間論理(LTLf)は、多くのアプリケーション領域で仕様を作成するためのデファクト標準になりつつある。 満足度チェックのための最先端手法を用いて、不満足なコアを抽出する4つのアルゴリズムを提案する。 結果は、異なるアルゴリズムやツールの実現可能性、有効性、相補性を示している。
  論文  参考訳（メタデータ） (2022-03-09T16:08:43Z)
• Controllable Summarization with Constrained Markov Decision Process [50.04321779376415]
  本研究では,ユーザが特定の属性を制御できる可制御テキスト要約について検討する。 制約付きマルコフ決定プロセス(CMDP)に基づく新しいトレーニングフレームワークを提案する。 我々のフレームワークは、長さ、被覆された実体、抽象性など、要約の重要な属性を制御するために応用できる。
  論文  参考訳（メタデータ） (2021-08-07T09:12:53Z)
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks [59.419152768018506]
  最適ポリシーは必ずk-SP制約を満たすことを示す。 本研究では,SP制約に違反するポリシーを完全に排除する代わりに,新たなコスト関数を提案する。 また,MiniGrid,DeepMind Lab,Atari,Fetchを用いた実験の結果,提案手法はPPOを著しく改善することが示された。
  論文  参考訳（メタデータ） (2021-07-13T21:39:21Z)
• A Constraint Driven Solution Model for Discrete Domains with a Case Study of Exam Timetabling Problems [6.788217433800101]
  知的制約処理進化アルゴリズム (ICHEA) のバリエーションは, ベンチマーク試験の時間変化問題を解決するために実証されている。 ICHEAはまず、与えられた制約をすべて段階的に満たすために結婚間クロスオーバー演算子を使用し、その後、ソリューションを最適化するために従来の演算子と拡張演算子の組み合わせを使用する。
  論文  参考訳（メタデータ） (2020-02-08T06:53:38Z)

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

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