Improved Bounds for Online Facility Location with Predictions

• URL: http://arxiv.org/abs/2107.08277v4
• Date: Sun, 18 Aug 2024 07:30:46 GMT
• Title: Improved Bounds for Online Facility Location with Predictions
• Authors: Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, Nikolas Patris, Thanos Tolias,
• Abstract summary: We consider Online Facility Location in the framework of learning-augmented online algorithms. In OFL, demands arrive one-by-one in a metric space and must be assigned to an open facility upon arrival. We present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities.
• Score: 14.973636284231047
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider Online Facility Location in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We focus on uniform facility opening costs and present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases from sublogarithmic in the number of demands $n$ to constant as the so-called $\eta_1$ error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases. E.g., our analysis implies that if for some $\varepsilon > 0$, $\eta_1 = \mathrm{OPT} / n^\varepsilon$, where $\mathrm{OPT}$ is the cost of the optimal solution, the competitive ratio becomes $O(1/\varepsilon)$. We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the $\eta_1$ error is optimal, up to constant factors. Finally, we evaluate our algorithm on real world data and compare the performance of our learning-augmented approach against the performance of the best known algorithm for OFL without predictions.

Related papers

• Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
  We consider the problem of learning and using predictions for warm start algorithms with predictions. In this setting, an algorithm is given an instance of a problem, and a prediction of the solution. We give competitive guarantees against stronger benchmarks that consider a set of $k$ predictions.
  arXiv  Detail & Related papers  (2024-05-06T17:38:20Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  We present new algorithms for optimizing non-known, non-smooth objectives based on a novel analysis technique. For deterministic second-order smooth objectives, applying advanced optimistic online learning techniques enables a new $O(delta0.5) all$ to recover optimal or best-known results.
  arXiv  Detail & Related papers  (2023-02-07T22:09:20Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  We study the problem of online optimization, where a decision maker must choose points in a general metric space to the sum of per-round, non-competitive hitting costs and the costs of switching between rounds. We propose a novel algorithm, Adaptive Online Switching (AOS), and prove that, for any desired $delta 0)$competitive if predictions are perfect, it is $tildecalO(alphadelta)$ even when predictions are inaccurate.
  arXiv  Detail & Related papers  (2022-02-07T21:08:02Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• Facility Reallocation on the Line [9.40406631624105]
  We consider a multi-stage facility reallocation problem 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.
  arXiv  Detail & Related papers  (2021-03-23T23:48:45Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  We investigate the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost. To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the greedy algorithm which simply minimizes the weighted sum of the hitting cost and the switching cost.
  arXiv  Detail & Related papers  (2021-02-13T14:15:55Z)
• Online Apprenticeship Learning [58.45089581278177]
  In Apprenticeship Learning (AL), we are given a Markov Decision Process (MDP) without access to the cost function. The goal is to find a policy that matches the expert's performance on some predefined set of cost functions. We show that the OAL problem can be effectively solved by combining two mirror descent based no-regret algorithms.
  arXiv  Detail & Related papers  (2021-02-13T12:57:51Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
  arXiv  Detail & Related papers  (2020-12-17T04:56:51Z)
• Online Page Migration with ML Advice [26.929268665630342]
  We consider online algorithms for the em page migration problem that use predictions, potentially imperfect, to improve their performance. We show that if the algorithm is given a prediction of the input sequence, then it can achieve a competitive ratio that tends to $1$. Our result adds to the recent body of work that uses machine learning to improve the performance of classic'' algorithms.
  arXiv  Detail & Related papers  (2020-06-09T03:15:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.