論文の概要: On Approximate MMS Allocations on Restricted Graph Classes

• arxiv url: http://arxiv.org/abs/2508.06343v1
• Date: Fri, 08 Aug 2025 14:17:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.253736
• Title: On Approximate MMS Allocations on Restricted Graph Classes
• Title（参考訳）: 制限グラフクラス上の近似MMS割当について
• Authors: Václav Blažej, Michał Dębski ad Zbigniew Lonc, Marta Piecyk, Paweł Rzążewski,
• Abstract要約: 本研究では,接続制約のある不特定商品群を公平に分割する問題について検討する。 完備グラフ、サイクル、固定された$d$に対する$d$-claw-freeグラフのようなグラフのクラスが実際に存在することは知られている。 このようなアロケーションは、ブロックグラフ、cacti、完全多部グラフ、分割グラフなど、よく研究されているクラスに存在していることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.
• Abstract（参考訳）: 本研究では,接続制約のある不特定商品群を公平に分割する問題について検討する。 具体的には、商品が連結グラフの頂点として表現され、エージェントに割り当てられた商品の集合がこのグラフの連結部分グラフであると仮定する。 我々は、広く研究されている公正性の最大シェア基準に焦点を当てている。 この基準を満たす割当は、接続制約なしでも存在せず、すなわち、商品のグラフが完全であれば存在しないことが示されている。 これを踏まえると、各エージェントが最大シェア値の少なくとも一定の割合の値で商品の連結バンドルを保証できる近似的な割り当てを求めるのは自然である。 完備グラフ、サイクル、固定された$d$に対する$d$-claw-freeグラフのようなグラフのクラスが実際に存在することは知られている。 しかし、それらがすべてのグラフのクラスに対して存在するかどうかは、未解決の問題である。 本稿では,制限グラフクラスにおける近似アロケーションの存在に関する系統的研究を継続する。 特に、ブロックグラフ、cacti、完全多部グラフ、分割グラフなど、よく研究されたクラスにそのようなアロケーションが存在することを示す。

関連論文リスト

• $σ$-Maximal Ancestral Graphs [1.6574413179773764]
  我々は''$sigma$-Maximal Ancestral Graphs'' (''$sigma$-MAGs')を造語するグラフィカルオブジェクトのクラスを紹介し、研究する。 これらのグラフィカルオブジェクトは、DAG(Directed Acyclic Graphs)の祖先関係とd-セパレーションに関する情報を符号化する これらのグラフが遅延(選択)変数を持つ方向グラフの抽象表現を提供する方法を示し、MAGがDAGを表す方法に類似している。
  論文  参考訳（メタデータ） (2025-06-30T10:08:21Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。 最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。 本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
  論文  参考訳（メタデータ） (2024-01-10T07:58:44Z)
• M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering [57.947071423091415]
  本稿では,理論収束を保証する学習自由度アルゴリズムであるM3Cを提案する。 我々は、新しいエッジワイド親和性学習と擬似ラベル選択を組み込んだ教師なしモデルUM3Cを開発した。 提案手法は,最先端のグラフマッチングと混合グラフマッチングとクラスタリングの手法を精度と効率の両面で優れている。
  論文  参考訳（メタデータ） (2023-10-27T19:40:34Z)
• Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
  我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。 我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
  論文  参考訳（メタデータ） (2023-06-07T15:04:58Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。 相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
  論文  参考訳（メタデータ） (2023-02-10T18:21:35Z)
• Variational Graph Generator for Multi-View Graph Clustering [51.89092260088973]
  マルチビューグラフクラスタリング(VGMGC)のための変分グラフ生成器を提案する。 この生成器は、複数のグラフに対する事前仮定に基づいて、信頼性のある変分コンセンサスグラフを推論する。 推論されたビュー共通グラフとビュー固有のグラフを機能と一緒に埋め込む。
  論文  参考訳（メタデータ） (2022-10-13T13:19:51Z)
• Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
  ノードがグラフのインスタンスである階層グラフにおけるノード分類問題について検討する。 本稿では階層グラフ相互情報(HGMI)を提案し,理論的保証をもってHGMIを計算する方法を提案する。 本稿では,この階層グラフモデリングとSEAL-CI法がテキストおよびソーシャルネットワークデータに与える影響を実証する。
  論文  参考訳（メタデータ） (2022-06-11T04:05:29Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。 提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
  論文  参考訳（メタデータ） (2020-10-12T03:01:40Z)
• Few-Shot Learning on Graphs via Super-Classes based on Graph Spectral Measures [14.932318540666545]
  グラフニューラルネットワーク (GNN) におけるショットグラフ分類の問題について, 限定ラベル付きグラフの場合, 未確認のクラスを認識するために検討した。 グラフ正規化ラプラシアンのスペクトルに基づいて確率測度を各グラフに割り当てる手法を提案する。
  論文  参考訳（メタデータ） (2020-02-27T17:11:14Z)

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

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