論文の概要: The Complexity of Envy-Free Graph Cutting

• arxiv url: http://arxiv.org/abs/2312.07043v1
• Date: Tue, 12 Dec 2023 07:54:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-13 16:57:55.546089
• Title: The Complexity of Envy-Free Graph Cutting
• Title（参考訳）: Envy-Free Graph Cutting の複雑さ
• Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
• Abstract要約: 我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。 問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
• 参考スコア（独自算出の注目度）: 44.58084909019557
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.
• Abstract（参考訳）: 我々は,異なる好みのエージェント間で,不均質な資源の集合を公平に分割する問題を考える。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結部分を割り当てなければならない。 問題はNP完全であり、エージェント数とグラフ内のエッジ数という2つの自然な複雑性尺度に関して、その複雑さを分析する。 この問題は2つのエージェントを持つインスタンスに対してもNPハードのままであるが、グラフの構造特性に基づいてエージェント数が一定である場合の複雑性を特徴付ける二分法を提供する。 後者の場合、グラフが一定数のエッジを持つ場合、多項式時間アルゴリズムを設計する。

関連論文リスト

• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。 相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
  論文  参考訳（メタデータ） (2023-02-10T18:21:35Z)
• Graphical House Allocation [18.119269486735245]
  このような問題の鍵となる基準は、うらやましい自由さのような公正な制約を満たすことである。 我々のゴールは、自然公正の目的として、エージェント間の集合的うらやみを最小限にすることである。 同一のバリュエーションが不均一な場合、私たちはこの古典的な問題から脱却する深遠で驚くべき方法をいくつか示します。
  論文  参考訳（メタデータ） (2023-01-03T19:26:15Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。 提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。 第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
  論文  参考訳（メタデータ） (2022-12-01T11:49:07Z)
• A New Heterogeneous Graph Representation in a Social Media Platform: Steemit [2.127049691404299]
  グラフの各成分に時間を含む新しい異種グラフ表現を提案する。 また、機械学習やディープラーニングの問題に対処するために、4つの時間依存クエリを導入します。
  論文  参考訳（メタデータ） (2022-09-02T04:59:21Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。 提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
  論文  参考訳（メタデータ） (2020-10-12T03:01:40Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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