論文の概要: A Polynomial-Time Algorithm for EFX Orientations of Chores

• arxiv url: http://arxiv.org/abs/2501.13481v1
• Date: Thu, 23 Jan 2025 08:53:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-24 15:55:42.656474
• Title: A Polynomial-Time Algorithm for EFX Orientations of Chores
• Title（参考訳）: 雑草のEFX配向に対する多項式時間アルゴリズム
• Authors: Kevin Hsu, Valerie King,
• Abstract要約: 品物件と雑用件との間には意外な分離が見られる。 また、多重グラフがNP完全であるような類似的な決定問題も示している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: This paper addresses the problem of finding EFX orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its corresponding edge is not incident to the vertex corresponding to the agent. Recently, Zhou~et~al.~(IJCAI,~2024) analyzed the complexity of deciding whether graphs containing a mixture of goods and chores admit EFX orientations, and conjectured that deciding whether graphs containing only chores admit EFX orientations is NP-complete. In this paper, we resolve this conjecture by exhibiting a polynomial-time algorithm that finds an EFX orientation of a graph containing only chores if one exists, even if the graph contains self-loops. Remarkably, our first result demonstrates a surprising separation between the case of goods and the case of chores, because deciding whether graphs containing only goods admit EFX orientations of goods was shown to be NP-complete by Christodoulou et al.~(EC,~2023). In addition, we show the analogous decision problem for multigraphs to be NP-complete.
• Abstract（参考訳）: 本稿では,各頂点がエージェントに対応し,各端がコレットに対応し,対応する端がエージェントに対応する頂点に入らない場合に,その端がエージェントにゼロな限界効用を有するような,コレットのグラフのEFX配向を求める問題に対処する。 最近、Zhou〜et〜al。 ～(IJCAI,~2024)は、商品と雑貨の混合を含むグラフがEFX配向を許容するか否かを決定する複雑さを分析し、雑貨のみを含むグラフがEFX配向を許容するかどうかを決定することはNP完全であると予想した。 本稿では,グラフが自己ループを含む場合でも,そのグラフが存在する場合にのみ振れを含むグラフのEFX配向を求める多項式時間アルゴリズムを提示することにより,この予想を解消する。 商品のみを含むグラフが商品のEFX配向を許容するかどうかを決定することは、Christodoulou et al ~(EC,–2023) によってNP完全であることが示されている。 さらに,マルチグラフがNP完全である場合の類似的な決定問題を示す。

関連論文リスト

• Testing Dependency of Weighted Random Graphs [4.0554893636822]
  本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。 一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
  論文  参考訳（メタデータ） (2024-09-23T10:07:41Z)
• Mitigating Label Noise on Graph via Topological Sample Selection [72.86862597508077]
  トポロジ情報を活用することで,グラフ内の情報的サンプル選択プロセスを促進できる$textitTopological Sample Selection$ (TSS)法を提案する。 提案手法は,対象のクリーン分布下での予測されるリスク上限の上限を最小化し,最先端のベースラインと比較して,提案手法の優位性を実験的に示す。
  論文  参考訳（メタデータ） (2024-03-04T11:24:51Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。 問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
  論文  参考訳（メタデータ） (2023-12-12T07:54:30Z)
• Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
  グラフレベルの異常検出(GLAD)は、コレクションの大多数と比べて顕著な相違を示すグラフを識別することを目的としている。 本稿では,異常なグラフを検出し,同時に情報的説明を生成する自己解釈グラフaNomaly dETectionモデル(SIGNET)を提案する。
  論文  参考訳（メタデータ） (2023-10-25T10:10:07Z)
• ALEX: Towards Effective Graph Transfer Learning with Noisy Labels [11.115297917940829]
  本稿では,グラフ伝達学習の課題に対処するため,バランスアライメントと情報認識試験(ALEX)と呼ばれる新しい手法を提案する。 ALEXはまず特異値分解を使用して、重要な構造的意味論を持つ異なるビューを生成し、堅牢なノード表現を提供する。 この基礎の上に構築され、複雑なマルチモーダル分布の暗黙的な領域アライメントのために、対向領域判別器が組み込まれている。
  論文  参考訳（メタデータ） (2023-09-26T04:59:49Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Towards Explanation for Unsupervised Graph-Level Representation Learning [108.31036962735911]
  既存の説明手法は,教師付き設定,例えばノード分類,グラフ分類に重点を置いているが,教師なしグラフレベルの表現学習に関する説明はまだ探索されていない。 本稿では,非教師付きグラフ表現における説明問題に対処するために,インフォメーション・ボトルネックの原則(IB)を推進し,新しい原理であるtextitUnsupervised Subgraph Information Bottleneck(USIB)を導出する。 また,グラフ表現とラベル空間上の説明部分グラフの関連性も理論的に解析し,表現の堅牢性が説明部分グラフの忠実性に寄与することを明らかにする。
  論文  参考訳（メタデータ） (2022-05-20T02:50:15Z)
• Graph-wise Common Latent Factor Extraction for Unsupervised Graph Representation Learning [40.70562886682939]
  我々は、教師なしグラフ表現学習のための新しい原則を提案する:グラフワイド共通潜在因子抽出(GCFX) GCFXは入力グラフから一般的な潜伏因子を明示的に抽出し、現在の最先端のタスクで改善された結果を達成する。 広範囲な実験と分析により,GCFXは個々のノードや周辺地域の局所的な変動による障害を軽減するため,グラフレベルのタスクに有用であることを示す。
  論文  参考訳（メタデータ） (2021-12-16T12:22:49Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)

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

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