論文の概要: Parameterized Aspects of Distinct Kemeny Rank Aggregation
- arxiv url: http://arxiv.org/abs/2309.03517v1
- Date: Thu, 7 Sep 2023 06:58:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-08 14:11:14.825874
- Title: Parameterized Aspects of Distinct Kemeny Rank Aggregation
- Title（参考訳）: 異なるケメニーランクアグリゲーションのパラメータ化
- Authors: Koustav De, Harshil Mittal, Palash Dey, Neeldhara Misra
- Abstract要約: パラメータ化複雑性のレンズの下で,異なるケメニーランクの計算問題について検討する。
ランニング時間を大幅に増加させることなく、望ましいケメニーランキングが見つかることもわかりました。
- 参考スコア（独自算出の注目度）: 4.792851066169871
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Kemeny method is one of the popular tools for rank aggregation. However,
computing an optimal Kemeny ranking is NP-hard. Consequently, the computational
task of finding a Kemeny ranking has been studied under the lens of
parameterized complexity with respect to many parameters. We first present a
comprehensive relationship, both theoretical and empirical, among these
parameters. Further, we study the problem of computing all distinct Kemeny
rankings under the lens of parameterized complexity. We consider the target
Kemeny score, number of candidates, average distance of input rankings, maximum
range of any candidate, and unanimity width as our parameters. For all these
parameters, we already have FPT algorithms. We find that any desirable number
of Kemeny rankings can also be found without substantial increase in running
time. We also present FPT approximation algorithms for Kemeny rank aggregation
with respect to these parameters.
- Abstract（参考訳）: ケメニー法はランクアグリゲーションの一般的な道具の1つである。
しかし、最適なケメニーランクの計算はNPハードである。
その結果,多くのパラメータに対するパラメータ化複雑性のレンズの下で,ケメニーランクを求める計算タスクが研究されている。
まず,これらのパラメータの包括的関係,理論的および経験的関係について述べる。
さらに,パラメータ化複雑性のレンズの下で,異なるケメニーランクの計算問題について検討する。
対象ケメニースコア,候補数,入力ランキングの平均距離,任意の候補の最大範囲,一致幅をパラメータとして検討した。
これらのパラメータに対して、既にFPTアルゴリズムがあります。
ケメニーランキングの望ましい数も、実行時間を大幅に増加させることなく発見できることがわかった。
また,これらのパラメータに関して,ケメニーランクアグリゲーションに対するFPT近似アルゴリズムを提案する。
関連論文リスト
- Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers [0.5490714603843316]
HodgeRankはグラフと離散外部計算を用いて、実世界の(しばしば不完全な)データに基づいてランキングアルゴリズムを一般化してランク付けする。
我々は,次元に依存しない複雑性を持つHodgeRank解を近似する量子アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-07-29T23:16:23Z) - Ranking with Slot Constraints [25.715799711674457]
我々はスロット制約問題に対する新しいランキングアルゴリズムであるMatchRankを考案した。
MatchRankの目標は、候補者がランキングの順に人間の意思決定者によって評価される場合、満たされたスロットの数を最大化するランキングを作成することである。
我々の理論的分析は、MatchRankがスロットや候補間の独立性の仮定なしで、強い近似保証を持つことを示している。
論文 参考訳（メタデータ） (2023-10-27T03:14:50Z) - Partitioned Saliency Ranking with Dense Pyramid Transformers [4.449304130658638]
サリエンシランキングは、インスタンスレベルのサリエンシの度合いを評価することに焦点を当てた、挑戦的なタスクとして登場した。
従来のアプローチでは、固有の曖昧さを明示的に解決していない有能なインスタンスのランクスコアを直接ソートすることで、サリエンシのランク付けを行っている。
本稿では,非順序の有意なインスタンスをパーティションに分割し,それらのパーティション間の相関に基づいてランク付けするパーティション・バイ・パーティション・パラダイムを提案する。
論文 参考訳（メタデータ） (2023-08-01T02:33:10Z) - Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。
xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。
提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
論文 参考訳（メタデータ） (2023-07-27T07:42:44Z) - Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。
我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
論文 参考訳（メタデータ） (2023-06-05T06:55:39Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。
これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-03-14T15:21:18Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-01-21T16:43:03Z) - On the Linear Ordering Problem and the Rankability of Data [0.0]
線形度合いを使用して、データの割合が最適なランキングと一致するかを定量化します。
スポーツの文脈では、これはランキングが後から正確に予測できるゲームの数に類似している。
LOPを用いて計算した最適ランキングは、ランキングの後方精度を最大化することを示す。
論文 参考訳（メタデータ） (2021-04-12T21:05:17Z) - Concentric mixtures of Mallows models for top-$k$ rankings: sampling and
identifiability [0.0]
上位ランクの2つのMallowsモデルの混合について検討する。
我々はMallows Top-k$ランキングの効率的なサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-27T13:00:37Z) - Necessarily Optimal One-Sided Matchings [49.0517583218216]
我々は、$n$エージェントと$n$オブジェクトとをマッチングする古典的な問題について研究する。
エージェントに完全な選好を報告させる代わりに、私たちのゴールは部分的な選好から望ましいマッチングを学ぶことです。
我々は,与えられたマッチングが NPO か NRM かを確認し,そのようなマッチングが与えられたトップ$k$ の部分的選好が存在するかどうかを確認するために,効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-07-17T16:01:34Z) - Augmented Parallel-Pyramid Net for Attention Guided Pose-Estimation [90.28365183660438]
本稿では、注意部分モジュールと微分可能な自動データ拡張を備えた拡張並列ピラミドネットを提案する。
我々は、データ拡張のシーケンスをトレーニング可能なCNNコンポーネントとして定式化する新しいポーズ検索空間を定義する。
特に,本手法は,挑戦的なCOCOキーポイントベンチマークとMPIIデータセットの最先端結果において,トップ1の精度を実現する。
論文 参考訳（メタデータ） (2020-03-17T03:52:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。