論文の概要: Recognizing and Eliciting Weakly Single Crossing Profiles on Trees

• arxiv url: http://arxiv.org/abs/1611.04175v4
• Date: Thu, 24 Jul 2025 05:38:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-25 15:10:39.916581
• Title: Recognizing and Eliciting Weakly Single Crossing Profiles on Trees
• Title（参考訳）: 木上の弱い単一交差プロファイルの認識と除去
• Authors: Palash Dey,
• Abstract要約: 我々は、社会的選択論において、よく研究された単交差領域の一般化である木上の弱い単交差領域について研究する。 この領域に属する好みプロファイルを認識するための時間アルゴリズムを設計する。 そこで我々は,この領域に対して,優先権が逐次的にのみアクセス可能である場合でも有効である効率的なエレケーションアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 4.8951183832371
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce and study the weakly single-crossing domain on trees which is a generalization of the well-studied single-crossing domain in social choice theory. We design a polynomial-time algorithm for recognizing preference profiles which belong to this domain. We then develop an efficient elicitation algorithm for this domain which works even if the preferences can be accessed only sequentially and the underlying single-crossing tree structure is not known beforehand. We also prove matching lower bound on the query complexity of our elicitation algorithm when the number of voters is large compared to the number of candidates. We also prove a lower bound of $\Omega(m^2\log n)$ on the number of queries that any algorithm needs to ask to elicit single crossing profile when random queries are allowed. This resolves an open question in an earlier paper and proves optimality of their preference elicitation algorithm when random queries are allowed.
• Abstract（参考訳）: 我々は、社会的選択論において、よく研究された単交差領域の一般化である木上の弱い単交差領域を紹介し、研究する。 この領域に属する好みプロファイルを認識する多項式時間アルゴリズムを設計する。 そこで我々は,この領域に対する効率的なエレケーションアルゴリズムを開発した。これは,優先権が逐次的にのみアクセス可能であり,基礎となる単交木構造が事前に分かっていない場合にも有効である。 また,候補数に比べて有権者数が多い場合,提案アルゴリズムの問合せ複雑性に一致しないことを示す。 また、ランダムなクエリが許可された場合、任意のアルゴリズムがシングルクロスプロファイルを抽出する必要があるクエリ数に対して、$\Omega(m^2\log n)$の低いバウンダリを証明します。 これにより、事前の論文でオープンな疑問を解決し、ランダムなクエリが許可された場合の選好帰納アルゴリズムの最適性を証明する。

関連論文リスト

• Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size [0.0]
  この問題に対して,各チームがさらに境界サイズでなければならないバージョンについて検討する。 我々の主な貢献は、小さなチームの木のような構造(有界枝木幅)を効率的に扱うアルゴリズムである。
  論文  参考訳（メタデータ） (2025-05-28T14:11:14Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
  我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。 限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
  論文  参考訳（メタデータ） (2024-02-16T22:17:01Z)
• Nearest Neighbour with Bandit Feedback [4.9094025705644695]
  我々のアルゴリズムは、データ生成プロセスに関する仮定が全くなされていない完全に逆向きな設定を処理します。 ユークリッド空間におけるバンドイト問題に適用した場合,アルゴリズムに対する一般的な後悔と解析を行う。
  論文  参考訳（メタデータ） (2023-06-23T20:09:01Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。 線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。 我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
  論文  参考訳（メタデータ） (2020-09-10T16:35:54Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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