論文の概要: The Complexity of Optimizing Atomic Congestion

• arxiv url: http://arxiv.org/abs/2312.10219v2
• Date: Tue, 22 Oct 2024 15:52:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:24:20.142234
• Title: The Complexity of Optimizing Atomic Congestion
• Title（参考訳）: 原子渋滞の最適化の複雑さ
• Authors: Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram, Fionn Mc Inerney,
• Abstract要約: アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
• 参考スコア（独自算出の注目度）: 14.845310803203724
• License:
• Abstract: Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies -- that is, a centrally planned routing that minimizes the average cost of agents -- is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.
• Abstract（参考訳）: アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックであり、様々なアプリケーション領域における混雑とフロー最適化タスクをモデル化することができる。 このようなゲームのアナーキーの価格と、彼らのナッシュ均衡の計算の複雑さは、現在よく理解されているが、システム最適化戦略の計算の複雑さ、すなわちエージェントの平均コストを最小化する集中的に計画されたルーティングは、この文献で著しく検討されている。 パラメータ化複雑性パラダイムのレンズを通して、問題に対するトラクタビリティの正確な境界を特定することで、このギャップを埋める。 極めて単純なネットワーク上でも問題は非常に難解であることを示し、問題の計算(抽出可能性)を制御する構造パラメータが、自然(例えば木幅)に基づく頂点分離子ではなく、むしろエッジ分離子に基づくものであることを示す一連の結果を得る。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。

関連論文リスト

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers [0.2150989251218736]
  我々は,多目的最適化問題を解くために,近距離量子コンピュータを応用できる手法を開発した。 量子近似最適化アルゴリズム(QAOA)に基づく実装に焦点を当てる。
  論文  参考訳（メタデータ） (2023-08-16T09:22:01Z)
• Neural Quantile Optimization for Edge-Cloud Networking [13.509945075582447]
  我々は,バースト可能な請求書に基づいて制約を満足し,コストを最小化するエッジ・クラウド・コンピューティング・ネットワークにおいて,最適なトラフィック割当方式を模索する。 本稿では,教師なし学習による最適化問題を解決するため,Gumbel-softmaxサンプリングネットワークを提案する。 トレーニングされたネットワークは、効率的なトラフィック割当スキームサンプリングとして機能し、実現可能性およびコスト関数値のランダム戦略を著しく上回る。
  論文  参考訳（メタデータ） (2023-07-11T11:05:10Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。 本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。 ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
  論文  参考訳（メタデータ） (2022-10-27T07:15:55Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• Mind Your Solver! On Adversarial Attack and Defense for Combinatorial Optimization [111.78035414744045]
  我々は,最適解法に対する敵攻撃と防御のメカニズムの開発を主導する。 本稿では, グラフ構造を改良し, 解法の堅牢性を高めるための, 単純かつ効果的な防衛戦略を提案する。
  論文  参考訳（メタデータ） (2021-12-28T15:10:15Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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