論文の概要: A General Framework for Stable Roommates Problems using Answer Set Programming

• arxiv url: http://arxiv.org/abs/2008.03050v1
• Date: Fri, 7 Aug 2020 09:12:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-02 01:46:41.965142
• Title: A General Framework for Stable Roommates Problems using Answer Set Programming
• Title（参考訳）: 解答集合プログラミングを用いた安定ルームメイト問題の一般的な枠組み
• Authors: Esra Erdem, Muge Fidan, David Manlove, Patrick Prosser
• Abstract要約: 安定ルームメイト問題(SR)は、ルームメイトとして他のエージェントよりもエージェントの好みが特徴である。 SRTI-ASPと呼ばれる形式的なフレームワークを導入する。
• 参考スコア（独自算出の注目度）: 1.6344851071810071
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are motivated by applications (e.g., the preference lists may be incomplete (SRI) and involve ties (SRTI)), and that try to find a more fair solution (e.g., Egalitarian SR). Unlike the Stable Marriage problem, every SR instance is not guaranteed to have a solution. For that reason, there are also variations of SR that try to find a good-enough solution (e.g., Almost SR). Most of these variations are NP-hard. We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set Programming, that is provable and general enough to solve many of such variations of SR. Our empirical analysis shows that SRTI-ASP is also promising for applications. This paper is under consideration for acceptance in TPLP.
• Abstract（参考訳）: 安定的ルームメイト問題 (stable roommates problem, sr) は、他のエージェントよりもエージェントの好みをルームメイト(roommates)として挙げることによって特徴づけられる。 srに対する解決策は、それぞれのペアが部屋を共有するようにエージェントをペアに分割することであり、このマッチングをブロックするエージェントのペアは存在しない(つまり、マッチングにおいて相手をルームメイトに好む)。 SRの興味深いバリエーションは、アプリケーションによって動機づけられる(例えば、選好リストは不完全(SRI)であり、関係(SRTI)を伴い、より公平な解を見つけようとする(例えば、平等主義的SR)。 安定結婚問題とは異なり、全てのSRインスタンスが解を持つことは保証されない。 そのため、良好な解(例えば、ほぼSR)を見つけようとするSRのバリエーションもある。 これらの変種のほとんどはNPハードである。 我々は,srti-aspと呼ばれる形式的フレームワークを導入し,論理プログラミングパラダイムの解集合プログラミングを活用し,srの変形の多くを解決するための証明可能かつ汎用的な手法を提案する。 私たちの実証分析は、SRTI-ASPがアプリケーションにも有望であることを示している。 本論文はTPLPの受容について検討中である。

関連論文リスト

• AnySR: Realizing Image Super-Resolution as Any-Scale, Any-Resource [84.74855803555677]
  我々はAnySRを導入し、既存の任意のスケールのSRメソッドを任意のソース実装に再構築する。 私たちのAnySRは、1)任意のスケールタスクを任意のリソース実装として構築し、追加のパラメータなしで小さなスケールのリソース要件を減らします。 その結果,AnySR は SISR タスクをより効率的な計算方法で実装し,既存の任意のスケールの SISR メソッドに匹敵する性能を示した。
  論文  参考訳（メタデータ） (2024-07-05T04:00:14Z)
• When Search Meets Recommendation: Learning Disentangled Search Representation for Recommendation [56.98380787425388]
  シークエンシャルレコメンデーション(SESRec)のための検索強化フレームワークを提案する。 SESRec は、S&R の振る舞いにおいて類似および異種表現を分離する。 産業用と公共用両方のデータセットの実験では、SESRecが最先端のモデルより一貫して優れていることが示されている。
  論文  参考訳（メタデータ） (2023-05-18T09:04:50Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。 本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
  論文  参考訳（メタデータ） (2023-05-01T06:46:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
  SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。 本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。 R-UCBE と R-SR の2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-15T08:01:37Z)
• Resource Sharing Through Multi-Round Matchings [27.98321373077565]
  1ラウンド当たりのマッチングの集合は、もし存在するなら、効率的に見つけることができることを示す。 提案アルゴリズムを合成ネットワーク上で実験的に評価し,2つの実環境 – 共有オフィススペースとマッチングコース – に適用した。
  論文  参考訳（メタデータ） (2022-11-30T17:46:43Z)
• Symbolic Regression is NP-hard [1.5330785573575156]
  シンボリック回帰(シンボリックレグレッション、英: Symbolic regression、SR)は、数学的表現の形でデータのモデルを学ぶタスクである。 SRは計算集約的なタスクであることを示す。 SR が NP-hard であることを示すことによって、答えがおそらく負であることを示す証拠を提供する。
  論文  参考訳（メタデータ） (2022-07-03T12:10:28Z)
• Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods [1.58310730488265]
  安定結婚問題(Stable Marriage problem)のバリエーションについて検討し、すべての男女が好みを不完全で結びつきのある選好リストとして表現する。 この問題は、Ties and Incomplete preferences (SMTI) による安定結婚問題と呼ばれる。 SMTI, Max Cardinality, Sex-Equal, Egalitarianの3つの最適化変種について検討し, それらの解法を実証的に比較した。
  論文  参考訳（メタデータ） (2021-08-11T11:39:51Z)
• Knowledge-Based Stable Roommates Problem: A Real-World Application [2.741266294612776]
  安定ルームメイト問題(Stable Roommates problem with Ties and Incomplete list, SRTI)は、ルームメイトとして他のエージェントよりもエージェントを優先することが特徴である。 本稿では,ドメイン固有知識を考慮した知識ベース手法をSRTIに導入する。
  論文  参考訳（メタデータ） (2021-08-10T21:52:55Z)
• Omniscient Video Super-Resolution [84.46939510200461]
  本論文では,従来のSR出力を利用するだけでなく,現在と未来からのSR出力を活用するためのフレームワークを提案する。 本手法は客観的指標,主観的視覚効果,複雑度において最先端手法よりも優れている。
  論文  参考訳（メタデータ） (2021-03-29T15:09:53Z)

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

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