論文の概要: Graphical House Allocation

• arxiv url: http://arxiv.org/abs/2301.01323v2
• Date: Mon, 18 Sep 2023 23:37:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-20 20:20:26.394743
• Title: Graphical House Allocation
• Title（参考訳）: グラフィカルハウスアロケーション
• Authors: Hadi Hosseini, Justin Payan, Rik Sengupta, Rohit Vaish and Vignesh Viswanathan
• Abstract要約: このような問題の鍵となる基準は、うらやましい自由さのような公正な制約を満たすことである。 我々のゴールは、自然公正の目的として、エージェント間の集合的うらやみを最小限にすることである。 同一のバリュエーションが不均一な場合、私たちはこの古典的な問題から脱却する深遠で驚くべき方法をいくつか示します。
• 参考スコア（独自算出の注目度）: 18.119269486735245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical house allocation problem involves assigning $n$ houses (or items) to $n$ agents according to their preferences. A key criterion in such problems is satisfying some fairness constraints such as envy-freeness. We consider a generalization of this problem wherein the agents are placed along the vertices of a graph (corresponding to a social network), and each agent can only experience envy towards its neighbors. Our goal is to minimize the aggregate envy among the agents as a natural fairness objective, i.e., the sum of all pairwise envy values over all edges in a social graph. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied problem of linear arrangements. For identical valuations with possibly uneven spacing, we show a number of deep and surprising ways in which our setting is a departure from this classical problem. More broadly, we contribute several structural and computational results for various classes of graphs, including NP-hardness results for disjoint unions of paths, cycles, stars, or cliques, and fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call separability which results in efficient parameterized algorithms for finding optimal allocations.
• Abstract（参考訳）: 古典的な住宅割当問題は、その好みに応じて、n$ house(またはアイテム)を$n$ agentに割り当てることである。 このような問題の鍵となる基準は、うらやましい自由さのような公正な制約を満たすことである。 エージェントがグラフの頂点に沿って配置され(ソーシャルネットワークに対応する)、各エージェントが隣人に対してうらやましいだけを体験できる、この問題の一般化を考察する。 我々のゴールは、エージェント間の集合的エンビーを自然な公正目標、すなわちソーシャルグラフ内のすべてのエッジ上のすべてのペア的エンビー値の和として最小化することである。 エージェントが同一かつ等間隔のバリュエーションを持つ場合、線形配置のよく研究された問題に還元される。 同じ評価と、おそらく不均一な間隔に対して、私たちは、この古典的な問題から出発する、多くの深くて驚くべき方法を示します。 より広範に、パス、サイクル、スター、またはクリッドの解離結合に対するNP硬度結果や、パス、サイクル、スター、クリッドおよびそれらの解離結合に対する固定パラメータトラクタブルアルゴリズム(場合によっては多項式時間)など、グラフの様々なクラスに対する構造的および計算的な結果に寄与する。 さらに、我々の研究のコンセプト的貢献は、最適割り当てを見つけるための効率的なパラメータ化アルゴリズムをもたらす分離性と呼ばれる非連結グラフの構造特性の定式化である。

関連論文リスト

• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。 近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。 非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
  論文  参考訳（メタデータ） (2024-10-31T15:56:50Z)
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
  ランダム正則グラフ上での最大カットと最大独立集合問題を考える。 高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。 両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
  論文  参考訳（メタデータ） (2024-06-20T18:00:02Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。 問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
  論文  参考訳（メタデータ） (2023-12-12T07:54:30Z)
• On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem [0.0]
  我々は、進化的計算を取り入れた$mathcalNP$-hard multi-objective least- spanning tree problem (moMST)の効率的な近似に寄与する。 得られた知見に基づいて、高バイアスのサブグラフベースの突然変異演算子を設計する。 その結果,サブグラフベースの演算子が文献のベースラインアルゴリズムに勝っていることを確認した。
  論文  参考訳（メタデータ） (2023-05-31T22:35:17Z)
• Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set [0.0]
  我々は、Chiara Angelini と Federico Ricci-Tersenghi のコメントが、特定の非表現的な例を1つ挙げていると主張している。 本稿では,Angelini と Ricci-Tersenghi が提示した結果よりも,実行時のスケーリングが優れていることを示す。 我々は、グラフニューラルネットワークの内部(並列)解剖は、グリードアルゴリズムの(逐次)性質とは大きく異なると論じる。
  論文  参考訳（メタデータ） (2023-02-03T17:21:02Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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