Fugu-MT 論文翻訳(概要): Kemeny ranking is NP-hard for 2-dimensional Euclidean preferences

論文の概要: Kemeny ranking is NP-hard for 2-dimensional Euclidean preferences

arxiv url: http://arxiv.org/abs/2106.13054v1
Date: Thu, 24 Jun 2021 14:25:20 GMT
ステータス: 処理完了
システム内更新日: 2021-06-25 19:26:24.492985
Title: Kemeny ranking is NP-hard for 2-dimensional Euclidean preferences
Title（参考訳）: 2次元ユークリッド選好におけるケメニーランクはNPハードである
Authors: Bruno Escoffier and Olivier Spanjaard and Magdalena Tydrichova
Abstract要約: 有権者の選好が共通の構造を共有しているという仮定は、社会的選択問題においてNPの硬さを回避する標準的な方法である。ケメニーランキング問題は、d>=2のd-次元ユークリッド選好に対してNPハードであることを証明する。
参考スコア（独自算出の注目度）: 7.328653027656632
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The assumption that voters' preferences share some common structure is a standard way to circumvent NP-hardness results in social choice problems. While the Kemeny ranking problem is NP-hard in the general case, it is known to become easy if the preferences are 1-dimensional Euclidean. In this note, we prove that the Kemeny ranking problem is NP-hard for d-dimensional Euclidean preferences with d>=2. We note that this result also holds for the Slater ranking problem.
Abstract（参考訳）: 有権者の選好が共通の構造を共有しているという仮定は、社会的選択問題においてNPの硬さを回避する標準的な方法である。ケメニー階数問題は一般の場合NPハードであるが、選好が 1 次元ユークリッドであれば容易であることが知られている。本稿では、d>=2 の d-次元ユークリッド選好に対してケメニーランク問題はNPハードであることを示す。この結果がスレーターランキング問題にも当てはまることに留意する。

関連論文リスト

Towards Generalized Inverse Reinforcement Learning [11.880139160394958]
本稿では、最適でないかもしれない観察行動(政治)について、MDPの基本成分を学習する問題を考察する。 GIRLにおける2つの重要な課題に対処する: 第一に、観測された政策と基礎となる最適政策の相違を定量化する必要性、第二に、基礎となる最適政策を数学的に特徴づけることの難しさ。
論文参考訳（メタデータ） (2024-02-11T17:10:31Z)
Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文参考訳（メタデータ） (2024-02-01T09:18:34Z)
Parameterized Aspects of Distinct Kemeny Rank Aggregation [4.792851066169871]
パラメータ化複雑性のレンズの下で,異なるケメニーランクの計算問題について検討する。ランニング時間を大幅に増加させることなく、望ましいケメニーランキングが見つかることもわかりました。
論文参考訳（メタデータ） (2023-09-07T06:58:19Z)
Space reduction techniques for the $3$-wise Kemeny problem [0.0]
ケメニーの法則は、計算社会選択と生物学に様々な重要な応用がある最も研究されよく知られた投票方式の1つである。我々は、ミロシュとハメルがケメニーの統治のために得たような、大位数定理のいくつかの一般化を確立する。我々は、ベッツラーらによるケメニーの法則の有名な3/4ドルのマジョリティルールが、一般的には5ドル以上の選択肢のない選挙に対してのみ有効であることを示す。
論文参考訳（メタデータ） (2023-04-29T01:21:23Z)
Optimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes [0.0]
ケンダルタウ距離の3ドルは、古典的なケメニー則と比較して興味深い利点を示す。 3$-wise Kemeny 問題は NP-hard であるので,本研究は空間縮小法として有用である。
論文参考訳（メタデータ） (2023-04-28T17:04:14Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
A Necessary and Sufficient Entanglement Criterion of N-qubit System Based on Correlation Tensor [18.123649659460465]
一般N-量子系に対する必要十分かつ十分な絡み合い基準を提案する。以上の結果から, より一般的な症例に対して, 絡み合い・分離性基準を解く方法が示された。
論文参考訳（メタデータ） (2022-05-11T08:01:28Z)
The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文参考訳（メタデータ） (2022-03-18T08:03:20Z)
Social Distancing is Good for Points too! [91.3755431537592]
点が近すぎるとFCNNの動作が悪くなることを示す。そして、そのようなケースを避けるためにアルゴリズムの修正に成功した。この修正はアルゴリズムの近似保証とともに有用な上界を証明するのに十分である。
論文参考訳（メタデータ） (2020-06-28T16:49:59Z)
Fractional norms and quasinorms do not help to overcome the curse of dimensionality [62.997667081978825]
マンハッタンの距離や分数的な準位数 lp は、分類問題における次元性の呪いを克服するのに役立ちます。系統的な比較では、p=2, 1, 0.5 の lp に基づく kNN の性能の違いは統計的に重要でないことが示されている。
論文参考訳（メタデータ） (2020-04-29T14:30:12Z)
From Matching with Diversity Constraints to Matching with Regional Quotas [51.33676030875284]
分布制約に適合する2つの重要な公理の間の公式な関係を示す。 1)に対する実現可能かつ安定な結果が存在するかどうかを確認することはNP完全であることを示す。病院医師と地域基準との整合性に関するさらなる発展が,学校選択と多様性の両立につながると結論づける。
論文参考訳（メタデータ） (2020-02-17T02:51:46Z)

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