論文の概要: On Efficient Computation of DiRe Committees
- arxiv url: http://arxiv.org/abs/2402.19365v1
- Date: Thu, 29 Feb 2024 17:13:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-01 13:44:41.423065
- Title: On Efficient Computation of DiRe Committees
- Title（参考訳）: DiRe 委員会の効率的な計算について
- Authors: Kunal Relia
- Abstract要約: ほぼ2つの大きさの任意のグループに分けられる候補者からなる委員会選挙を考えてみましょう。
多様性制約は、各グループから少なくとも1つの候補を選択することを規定する。
表現制約は、承認された候補の非無効なセットを持つ各集団から少なくとも1人の候補者を選択することを規定している。
- 参考スコア（独自算出の注目度）: 4.8951183832371
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Consider a committee election consisting of (i) a set of candidates who are
divided into arbitrary groups each of size \emph{at most} two and a diversity
constraint that stipulates the selection of \emph{at least} one candidate from
each group and (ii) a set of voters who are divided into arbitrary populations
each approving \emph{at most} two candidates and a representation constraint
that stipulates the selection of \emph{at least} one candidate from each
population who has a non-null set of approved candidates.
The DiRe (Diverse + Representative) committee feasibility problem (a.k.a. the
minimum vertex cover problem on unweighted undirected graphs) concerns the
determination of the smallest size committee that satisfies the given
constraints. Here, for this problem, we discover an unconditional deterministic
polynomial-time algorithm that is an amalgamation of maximum matching,
breadth-first search, maximal matching, and local minimization.
- Abstract（参考訳）: 委員会による選挙を考える
(i)サイズ \emph{atmost} 2の各々の任意のグループに分けられる候補の組と、各グループから1つの候補が選ばれることを規定する多様性制約
(二) 任意の人口に分けた有権者の集合で、それぞれが2人の候補者を承認し、かつ、承認された候補者の非無効な集団から1人の候補者を選ぶことを規定した表現制約。
DiRe (Diverse + Representative) 委員会実現可能性問題(すなわち、非重み付き無向グラフ上の最小頂点被覆問題)は、与えられた制約を満たす最小サイズの委員会の決定に関するものである。
そこで本研究では,最大マッチング,幅優先探索,最大マッチング,局所最小化の融合である非条件決定論的多項式時間アルゴリズムを提案する。
関連論文リスト
- Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。
限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
論文 参考訳（メタデータ） (2024-02-16T22:17:01Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Concomitant Group Testing [49.50984893039441]
肯定的なテストが複数種類の項目の組み合わせを必要とするという考え方を捉えたグループテストの問題のバリエーションを紹介した。
目標は、可能な限り少数のテストを使用して、半欠陥セットをすべて確実に識別することである。
我々のアルゴリズムは、(i)決定性(ゼロエラー)かランダム化(小エラー)か、(ii)非適応性(非適応性)、完全適応性(完全適応性)、あるいは限定適応性(限定適応性)かによって区別される。
論文 参考訳（メタデータ） (2023-09-08T09:11:12Z) - On the Complexity of Finding a Diverse and Representative Committee
using a Monotone, Separable Positional Multiwinner Voting Rule [0.0]
計算社会選択における研究の線は、選挙における公正性を保証するために制約を使用することを懸念している。
最近の研究は、多様な代表委員会を見つけるためのモデルを提案し、モデルの計算的側面を研究した。
ここでは、単調で分離可能な複数投票ルールを用いて、多彩で代表的な委員会を見つける複雑さを分類する。
論文 参考訳（メタデータ） (2022-11-23T18:56:44Z) - A Nested Genetic Algorithm for Explaining Classification Data Sets with
Decision Rules [3.8271082752302137]
我々は、分類データセットを最もよく説明する一連の決定ルール(ルールセット)を自動的に抽出することを目指している。
まず、データセットでトレーニングされた一連の決定ツリーから、大規模な決定ルールを抽出する。
ルールセットは簡潔で正確で、最大カバレッジと最小数の矛盾を持つべきである。
論文 参考訳（メタデータ） (2022-08-23T11:42:15Z) - Leximax Approximations and Representative Cohort Selection [10.55182802721649]
幅広い候補から代表コホートを見つけることは、多くの文脈で発生する目標である。
レキシマックス解を見つけることは、ある群の効用の小さなバリエーションに大きく依存することができる。
線形ユーティリティを用いたレキシマックスコホート選択の整数解を見つけることはNP-Hardであることを示す。
論文 参考訳（メタデータ） (2022-05-02T18:43:25Z) - Uniformity in Heterogeneity:Diving Deep into Count Interval Partition
for Crowd Counting [56.44300325295678]
一様誤差分割(UEP)と呼ばれる新しいカウント間隔分割基準を提案する。
MCP基準は、推論中にそのカウント値を表すために、各インターバルのベストカウントプロキシを選択する。
統一誤り分割ネットワーク(UEPNet)と呼ばれる単純で効果的なモデルを提案する。
論文 参考訳（メタデータ） (2021-07-27T06:24:15Z) - Bribery as a Measure of Candidate Success: Complexity Results for
Approval-Based Multiwinner Rules [58.8640284079665]
有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。
我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。
一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
論文 参考訳（メタデータ） (2021-04-19T08:26:40Z) - Representative Committees of Peers [21.26271260313741]
投票者数に最適な社会的コストの1+O (1/k) の1+O (1/k) の範囲内で、k-sortitionが結果をもたらすことを示す。
大きな問題に対して、我々は、k-sortitionが委員会ベースの幅広いルールのファミリーの中で最悪のケース最適ルールであることを実証する。
論文 参考訳（メタデータ） (2020-06-14T08:20:47Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。