Fugu-MT 論文翻訳(概要): Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule

論文の概要: Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule

arxiv url: http://arxiv.org/abs/2202.12006v1
Date: Thu, 24 Feb 2022 10:34:46 GMT
ステータス: 処理完了
システム内更新日: 2022-02-25 18:13:05.559528
Title: Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
Title（参考訳）: Chamberlin-Courant Rule と Monroe Rule によるマルチウィンナー選挙のパラメータ化抽出性
Authors: Jiehua Chen and Sanjukta Roy
Abstract要約: したがって、$f(beta) cdot |I|O(1)$ -time アルゴリズムがあれば、$|I|$ は入力インスタンスのサイズを表す。
参考スコア（独自算出の注目度）: 9.206778211704524
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous representation voting rules: the Chamberlin-Courant (in short CC) rule [Chamberlin and Courant, APSR'83] and the Monroe rule [Monroe, APSR'95]. We show that under both rules, the problem is W[1]-hard with respect to the sum $\beta$ of misrepresentations, thereby precluding the existence of any $f(\beta) \cdot |I|^{O(1)}$ -time algorithm, where $|I|$ denotes the size of the input instance.
Abstract（参考訳）: Betzlerらによるオープンな質問に答える。 [betzler et al., jair'13] では,チャンバーリン・クーラント(略してcc)規則 [chamberlin and courant, apsr'83] とモンロー規則[monroe, apsr'95] という2つの有名な代表投票規則の下で,マルチウィンナー決定問題のパラメータ化された複雑性を解決する。両方の規則の下では、問題は$\beta$の誤表現の和に関して w[1]-hard であることを示し、したがって任意の$f(\beta) \cdot |i|^{o(1)}$-timeアルゴリズムの存在を予測し、ここで$|i|$ は入力インスタンスのサイズを表す。

関連論文リスト

G_q-concurrence and entanglement constraints in multiqubit systems [2.150800093140658]
我々は、$G_q$-concurrenceが絡み合い測度のすべての公理的条件を満たすことを示し、その収束の一般化と見なすことができる。タングルが有効性を失っても、真に複数ビットの絡み合う状態を検出することのできる絡み合い指標のセットを構築する。
論文参考訳（メタデータ） (2024-06-27T11:07:51Z)
Optimality of Matrix Mechanism on $\ell_p^p$-metric [6.076406622352115]
そのようなエラーを$(epsilon,delta)$-differential privacyで特徴づける。差分プライバシの下では、$ell_pp$エラーの点において、すべての定数$p$に対して、プレフィックス和とパリティクエリの応答に厳密な制限を与えます。
論文参考訳（メタデータ） (2024-06-04T09:27:35Z)
Parameterized multipartite entanglement measures [2.4172837625375]
我々は、$n$-partite system, $q$-$k$-ME concurrence $(qgeq2,2leq kleq n)$と$alpha$-$k$-ME concurrence $(0leqalphaleqfrac12,2leq kleq n)$の2種類の絡み合い測度を示す。厳密な証明は、提案された$k$非分離測度が絡み合い測度であるすべての要件を満たすことを示している。
論文参考訳（メタデータ） (2023-08-31T01:58:47Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
3次元のゼロレンジ力を介して相互作用する3つのボソン系のモデルハミルトンの性質について論じる。特に、適当な二次形式 $Q$ から始め、自己随伴およびハミルトンの$mathcal H$ の下から有界となるものを構築することができる。しきい値 $gamma_c$ が最適であることは、次の2次形式 $Q$ が下から非有界であるという意味では、$gamma_c$ が最適であることを示している。
論文参考訳（メタデータ） (2022-07-01T10:01:14Z)
Tightening monogamy and polygamy relations of unified entanglement in multipartite systems [1.6353216381658506]
まず、任意の二分法の下での多ビット状態に対する統一-$(q, s)$絡み合いのモノガミー不等式を導出する。次に、三元状態の生成の絡み合う$alpha$th(0leqalphaleqfracr2, rgeqsqrt2$)のモノガミー不等式を得る。
論文参考訳（メタデータ） (2022-05-12T23:27:16Z)
Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文参考訳（メタデータ） (2022-03-24T08:14:12Z)
On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文参考訳（メタデータ） (2021-12-03T21:42:33Z)
Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文参考訳（メタデータ） (2021-01-29T18:57:52Z)
On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文参考訳（メタデータ） (2020-09-21T04:13:34Z)
Informationally complete characters for quark and lepton mixings [0.0]
3世代のクォークとレプトンの混合パターンの一般的な説明は、有限群$G$のキャラ$kappa$である。ここでは、$d=cc(G)$を持つ$d$次元ヒルベルト空間、$G$の共役類の数を紹介する。
論文参考訳（メタデータ） (2020-05-05T08:48:52Z)

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