An Improved Algorithm For Online Min-Sum Set Cover

• URL: http://arxiv.org/abs/2209.04870v3
• Date: Fri, 24 Mar 2023 23:44:49 GMT
• Title: An Improved Algorithm For Online Min-Sum Set Cover
• Authors: Marcin Bienkowski, Marcin Mucha
• Abstract summary: We study a model of online preference aggregation, where an algorithm maintains an ordered list of $n$ elements. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is $O(r2)$. This is the first algorithm whose ratio does not depend on $n$: the previously best algorithm for this problem was $O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm.
• Score: 0.45687771576879593
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a fundamental model of online preference aggregation, where an algorithm maintains an ordered list of $n$ elements. An input is a stream of preferred sets $R_1, R_2, \dots, R_t, \dots$. Upon seeing $R_t$ and without knowledge of any future sets, an algorithm has to rerank elements (change the list ordering), so that at least one element of $R_t$ is found near the list front. The incurred cost is a sum of the list update costs (the number of swaps of neighboring list elements) and access costs (position of the first element of $R_t$ on the list). This scenario occurs naturally in applications such as ordering items in an online shop using aggregated preferences of shop customers. The theoretical underpinning of this problem is known as Min-Sum Set Cover. Unlike previous work (Fotakis et al., ICALP 2020, NIPS 2020) that mostly studied the performance of an online algorithm ALG against the static optimal solution (a single optimal list ordering), in this paper, we study an arguably harder variant where the benchmark is the provably stronger optimal dynamic solution OPT (that may also modify the list ordering). In terms of an online shop, this means that the aggregated preferences of its user base evolve with time. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is $O(r^2)$ and prove the existence of a deterministic $O(r^4)$-competitive algorithm. Here, $r$ is the maximum cardinality of sets $R_t$. This is the first algorithm whose ratio does not depend on $n$: the previously best algorithm for this problem was $O(r^{3/2} \cdot \sqrt{n})$-competitive and $\Omega(r)$ is a lower bound on the performance of any deterministic online algorithm.

Related papers

• Linear Bandits on Ellipsoids: Minimax Optimal Algorithms [5.678465386088928]
  We consider computationally linear bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. A run requires only time $O(dT + d2 log(T/d) + d3)$ and memory $O(d2)$.
  arXiv  Detail & Related papers  (2025-02-24T14:12:31Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  This paper studies the design and analysis of approximation algorithms for aggregating preferences over Conditional Preference Networks (CP-nets) Its focus is on aggregating preferences over so-called emphswaps, for which optimal solutions in general are already known to be of exponential size.
  arXiv  Detail & Related papers  (2023-12-14T17:31:38Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  Two deterministic approximation algorithms are presented for the problem of non-monotone $k$-submodular complexity under a knapsack constraint. Our algorithms provide constant approximation ratios within only $O(nk)$ query complexity for the non-monotone objective.
  arXiv  Detail & Related papers  (2023-09-21T12:42:52Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [26.71898403195793]
  We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an $epsilon$-approximate minimum of a convex function $f$. We prove a new lower bound that matches this bound (up to log factors), and holds not only for randomized algorithms, but also for quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-02T10:51:43Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  We consider the problem of monotone, submodular over a ground set of size $n$ subject to cardinality constraint $k$. We introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in $lceil n / c rceil + c$ oracle queries, for any $c ge 1$.
  arXiv  Detail & Related papers  (2020-09-10T16:35:54Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

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.