論文の概要: Facility Reallocation on the Line

• arxiv url: http://arxiv.org/abs/2103.12894v1
• Date: Tue, 23 Mar 2021 23:48:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-25 13:51:50.580532
• Title: Facility Reallocation on the Line
• Title（参考訳）: 路線上の施設移転
• Authors: Bart de Keijzer and Dominik Wojtczak
• Abstract要約: 我々は,$n$エージェントによって報告された位置に基づいて,施設を時間間隔で移動させる実数線上の多段施設再配置問題を考える。 再配置アルゴリズムの目的は、社会コストを最小化することであり、すなわち、施設と全てのエージェントのあらゆる段階の合計距離の合計と、施設を移動させるコストを最小化することである。
• 参考スコア（独自算出の注目度）: 9.40406631624105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by $n$ agents. The aim of the reallocation algorithm is to minimise the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We study this problem both in the offline setting and online setting. In the offline case the algorithm has full knowledge of the agent locations in all future stages, and in the online setting the algorithm does not know these future locations and must decide the location of the facility on a stage-per-stage basis. We derive the optimal algorithm in both cases. For the online setting we show that its competitive ratio is $(n+2)/(n+1)$. As neither of these algorithms turns out to yield a strategy-proof mechanism, we propose another strategy-proof mechanism which has a competitive ratio of $(n+3)/(n+1)$ for odd $n$ and $(n+4)/n$ for even $n$, which we conjecture to be the best possible. We also consider a generalisation with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.
• Abstract（参考訳）: 実線上では,n$エージェントが報告した場所に基づいて,施設が時間間隔で移動している,多段階的な施設配置問題を考える。 再配置アルゴリズムの目的は、社会コストを最小化することであり、すなわち、施設と全てのエージェントのあらゆる段階の合計距離の合計と、施設を移動させるコストを最小化することである。 オフライン設定とオンライン設定の両方でこの問題を研究する。 オフラインの場合、アルゴリズムは全ての将来の段階におけるエージェントの位置の完全な知識を持ち、オンライン設定では、アルゴリズムはこれらの将来の位置を知らないので、ステージごとに施設の位置を決定する必要がある。 どちらの場合にも最適アルゴリズムを導出する。 オンライン環境では、その競合比は$(n+2)/(n+1)$である。 いずれのアルゴリズムも戦略防御機構は得られないため、奇数$n$に対して$(n+3)/(n+1)$、偶数$(n+4)/n$が$(n+4)/n$という競合比を持つ別の戦略防御機構を提案する。 また,複数の施設と重み付きエージェントによる一般化についても検討し,一定数の施設で最適値を多項式時間で計算できることを示した。

関連論文リスト

• Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
  マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。 各ラウンドにおいて、各エージェント$i$は、オンラインの方法で、強い凸打撃コスト関数$fi_t$を受け取る。 通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
  論文  参考訳（メタデータ） (2024-11-13T05:59:04Z)
• Online Fair Allocation of Perishable Resources [1.4952056744888913]
  我々は、標準オンラインフェアアロケーション問題の事実上の動機付け型を考察する。 意思決定者は、一定回数のラウンドを割り当てるために、パーシシブルなリソースの予算を持っている。 目標は、うらやましいほど効率的で効率的なアロケーションのシーケンスを構築することです。
  論文  参考訳（メタデータ） (2024-06-04T15:14:10Z)
• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。 我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
  論文  参考訳（メタデータ） (2024-01-04T00:57:33Z)
• Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
  マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。 目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-03-03T02:40:26Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction [104.41634756395545]
  具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。 FedBiOの複雑性は$O(epsilon-1.5)$である。 本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2022-05-03T16:40:22Z)
• Improved Bounds for Online Facility Location with Predictions [14.973636284231047]
  学習強化オンラインアルゴリズムの枠組みとして,オンライン施設配置を考える。 OFLでは、要求はメートル法空間で1つずつ到着し、到着時にオープンな施設に割り当てられなければならない。 最適施設の位置の予測に不完全な可能性を生かしたOFLのオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-17T16:44:27Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost [53.968049198926444]
  スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。 このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
  論文  参考訳（メタデータ） (2021-01-02T18:41:27Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。 意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。 この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
  論文  参考訳（メタデータ） (2020-12-13T04:47:37Z)

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

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