論文の概要: Discounted Cuts: A Stackelberg Approach to Network Disruption

• arxiv url: http://arxiv.org/abs/2511.10804v1
• Date: Thu, 13 Nov 2025 21:12:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.330979
• Title: Discounted Cuts: A Stackelberg Approach to Network Disruption
• Title（参考訳）: Discounted Cuts: ネットワーク破壊に対するStackelbergのアプローチ
• Authors: Pål Grønås Drange, Fedor V. Fomin, Petr Golovach, Danil Sagunov,
• Abstract要約: 攻撃者とディフェンダーとの1ラウンドの対戦ゲームとしてモデル化された,古典的モスト・バイタルリンク問題のスタックルバーグ変種について検討する。 そこで我々は,カットのコストを最も高価なエッジの$k$を除くことで評価する,割引カットの数学的モデルを提案する。 そこで我々は,カット問題の様々な形態を解析するための統一的なアルゴリズムフレームワークを開発した。
• 参考スコア（独自算出の注目度）: 4.574052836738808
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a Stackelberg variant of the classical Most Vital Links problem, modeled as a one-round adversarial game between an attacker and a defender. The attacker strategically removes up to $k$ edges from a flow network to maximally disrupt flow between a source $s$ and a sink $t$, after which the defender optimally reroutes the remaining flow. To capture this attacker--defender interaction, we introduce a new mathematical model of discounted cuts, in which the cost of a cut is evaluated by excluding its $k$ most expensive edges. This model generalizes the Most Vital Links problem and uncovers novel algorithmic and complexity-theoretic properties. We develop a unified algorithmic framework for analyzing various forms of discounted cut problems, including minimizing or maximizing the cost of a cut under discount mechanisms that exclude either the $k$ most expensive or the $k$ cheapest edges. While most variants are NP-complete on general graphs, our main result establishes polynomial-time solvability for all discounted cut problems in our framework when the input is restricted to bounded-genus graphs, a relevant class that includes many real-world networks such as transportation and infrastructure networks. With this work, we aim to open collaborative bridges between artificial intelligence, algorithmic game theory, and operations research.
• Abstract（参考訳）: 攻撃者とディフェンダーの間の1ラウンドの対角ゲームとしてモデル化された,古典的Mest Vital Links問題のスタックルバーグ変種について検討する。 攻撃者は、フローネットワークから最大$k$のエッジを戦略的に取り除き、ソース$s$とシンク$t$の間のフローを最大に破壊する。 この攻撃者-防御者間相互作用を捉えるために,削減されたカットの数学的モデルを導入し,カットのコストを最も高価なエッジを除くことで評価する。 このモデルは、最も生きたリンク問題を一般化し、新しいアルゴリズム的および複雑性理論的性質を明らかにする。 本研究では, カットのコストを最小化あるいは最大化することを含む, カット問題の様々な形態を解析するための統一的なアルゴリズムフレームワークを開発する。 ほとんどの変種は一般グラフ上でNP完全であるが、本研究の主な成果は、入力が有界系グラフに制限された場合のフレームワーク内の全ての割引カット問題に対する多項式時間解法を確立することである。 本研究は,人工知能,アルゴリズムゲーム理論,オペレーション研究の連携橋渡しを目的としている。

関連論文リスト

• Spatial Supply Repositioning with Censored Demand Data [10.797160099834306]
  我々は、一方通行のオンデマンド車両共有サービスによるネットワーク在庫システムについて検討する。 このような一般的な在庫ネットワークにおいて最適なポリシーを見つけることは解析的にも計算的にも困難である。 我々の研究は、共有モビリティビジネスの生存性における在庫管理の重要性を強調している。
  論文  参考訳（メタデータ） (2025-01-31T15:16:02Z)
• On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
  我々は,100万ドル以上の分散データを用いたオンラインモデル選択について検討し,クライアント間のコラボレーションの必要性について検討する。 i) クライアント上の計算コストが$o(K)$に制限された場合, (ii) クライアント上での計算制約がない場合, (i) 協調は不要であり, (ii) クライアント上での計算コストは$o(K)$に制限される。
  論文  参考訳（メタデータ） (2024-04-15T06:32:28Z)
• Minimum Topology Attacks for Graph Neural Networks [70.17791814425148]
  グラフニューラルネットワーク(GNN)は、敵対的トポロジ攻撃に対する堅牢性において大きな注目を集めている。 本稿では,各ノードに対する攻撃を成功させるのに十分な最小摂動を適応的に見つけることを目的とした,最小予算トポロジ攻撃という新しいタイプのトポロジ攻撃を提案する。
  論文  参考訳（メタデータ） (2024-03-05T07:29:12Z)
• One-Shot Strategic Classification Under Unknown Costs [19.390528752448283]
  幅広いコストに対して、コスト関数の小さな誤推定でさえ、最悪の場合、自明な正確さを伴っていることを示す。 分析の結果,重要な戦略的応答,特にコスト操作関数に対する二重正則化の値が明らかになった。
  論文  参考訳（メタデータ） (2023-11-05T20:43:08Z)
• Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks [13.985534521589257]
  グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。 我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。 エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
  論文  参考訳（メタデータ） (2022-04-04T10:21:02Z)
• Robustness Certificates for Implicit Neural Networks: A Mixed Monotone Contractive Approach [60.67748036747221]
  暗黙のニューラルネットワークは、競合性能とメモリ消費の削減を提供する。 入力逆流の摂動に関して、それらは不安定なままである。 本稿では,暗黙的ニューラルネットワークのロバスト性検証のための理論的および計算的枠組みを提案する。
  論文  参考訳（メタデータ） (2021-12-10T03:08:55Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Towards Defending Multiple $\ell_p$-norm Bounded Adversarial Perturbations via Gated Batch Normalization [120.99395850108422]
  既存の敵防衛は、個々の摂動に対するモデル堅牢性を改善するのが一般的である。 最近の手法では、複数の$ell_p$球における敵攻撃に対するモデルロバスト性を改善するが、各摂動型に対するそれらの性能は、まだ十分ではない。 我々は,複数の$ell_pの有界摂動を守るために,摂動不変予測器を逆向きに訓練するGated Batch Normalization (GBN)を提案する。
  論文  参考訳（メタデータ） (2020-12-03T02:26:01Z)

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

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