文献

J-GLOBAL ID：202202224529685029   整理番号：22A0917438

kサーバのためのヒット集合緩和と時間窓への拡張【JST・京大機械翻訳】

A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows

著者 (3件)： Gupta Anupam (Carnegie Mellon University,Computer Science Department) ,  Kumar Amit (IIT Delhi,Dept. of Computer Science and Engg.) ,  Panigrahi Debmalya (Duke University,Department of Computer Science)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 504-515  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 時間窓によるkサーバ問題を研究した。この問題において,各要求は,時間b_iでn点計量空間のいくつかの点v_iに到達し,デッドラインe_iで来る。kサーバの1つは,この要求を満足するために,時間間隔[b_i,e_i]において,v_iに移動しなければならない。Δが計量空間のアスペクト比であるポリログ(n,Δ)の競合比を持つこの問題に対するオンラインアルゴリズムを与えた。著者らの研究の前に,この問題で知られている最良の競合比は,Azarら(STOC2017)によって与えられたO(kpolylog(n))であった。このアルゴリズムは,HST上のkサーバのための新しいカバー線形プログラム緩和に基づいている。このLPは,kサーバのミニコストフロー定式化に自然に対応し,時間窓の場合に容易に拡張する。このLPのための実行可能な分数解を得るためのオンラインアルゴリズム,および解のコストを説明するための一次二重解析フレームワークを与えた。同時に,それらは,ポリ対数競合比を有する新しいkサーバアルゴリズムを生み出して,また,時間ウィンドウケースに拡大した。著者らの主要な技術的貢献は,木の各々の内部ノードで切断された被覆LPを産出するので,被覆LPの思考にあり,サブツリーを横断したサーバの動きの考慮を可能にする。著者らは,このLP緩和とアルゴリズム/解析が,kサーバと関連問題に対処する有用なツールになると期待する。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  アスペクト比 ,  被覆 ,  時間制限 ,  *緩和現象 ,  線形性 ,  対数 ,  定式化
準シソーラス用語： *時間窓 ,  オンラインアルゴリズム ,  競合比 ,  時間間隔 ,  部分木 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： サーバ ,  集合 ,  緩和 ,  時間窓 ,  拡張