論文の概要: Approximation Algorithms for Preference Aggregation Using CP-Nets

• arxiv url: http://arxiv.org/abs/2312.09162v1
• Date: Thu, 14 Dec 2023 17:31:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-15 20:37:28.793684
• Title: Approximation Algorithms for Preference Aggregation Using CP-Nets
• Title（参考訳）: CP-Netを用いた参照集約のための近似アルゴリズム
• Authors: Abu Mohammmad Hammad Ali, Boting Yang, Sandra Zilles
• Abstract要約: 本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。 その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
• 参考スコア（独自算出の注目度）: 3.337244446073836
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called \emph{swaps}, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to $4/3$. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any $\varepsilon$, the trivial algorithm can\emph{not}\/ attain a $(2-\varepsilon)$-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than $2$.
• Abstract（参考訳）: 本稿では,コンディショナル・プライス・ネットワーク(CP-nets)を用いて,組合せ領域を優先する近似アルゴリズムの設計と解析を行う。 その焦点は、いわゆる \emph{swaps} に対する選好を集約することであり、そこでは一般に最適解は既に指数的大きさであることが知られている。 まず,与えられた入力選好の最大値を単純に出力する自明な2近似アルゴリズムを解析し,このアルゴリズムの近似比を4/3$に改善する構造条件を定式化する。 次に,提案する多項式時間近似アルゴリズムにより,出力は自明なアルゴリズムよりも確実に悪いが,より優れている。 改良されたアルゴリズムが最適解を生成する問題インスタンス群を提示する一方、任意の$\varepsilon$に対して、自明なアルゴリズム can\emph{not}\/ は$(2-\varepsilon)$-approximation を達成する。 これらの結果は、近似比が2ドル以上のスワップに対するCP-net集約問題を解く最初の多項式時間近似アルゴリズムにつながるかもしれない。

関連論文リスト

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。 $mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-17T15:27:33Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。 以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
  論文  参考訳（メタデータ） (2023-02-20T05:16:18Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization [16.346069386394703]
  定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。 単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
  論文  参考訳（メタデータ） (2020-10-27T15:22:49Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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