Search Results

Documents authored by Kamali, Shahin

Document
DOI: 10.4230/LIPIcs.SWAT.2024.10
Online Bin Covering with Frequency Predictions

Authors: Magnus Berg and Shahin Kamali

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We study the bin covering problem where a multiset of items from a fixed set S ⊆ (0,1] must be split into disjoint subsets while maximizing the number of subsets whose contents sum to at least 1. We focus on the online discrete variant, where S is finite, and items arrive sequentially. In the purely online setting, we show that the competitive ratios of best deterministic (and randomized) algorithms converge to 1/2 for large S, similar to the continuous setting. Therefore, we consider the problem under the prediction setting, where algorithms may access a vector of frequencies predicting the frequency of items of each size in the instance. In this setting, we introduce a family of online algorithms that perform near-optimally when the predictions are correct. Further, we introduce a second family of more robust algorithms that presents a tradeoff between the performance guarantees when the predictions are perfect and when predictions are adversarial. Finally, we consider a stochastic setting where items are drawn independently from any fixed but unknown distribution of S. Using results from the PAC-learnability of probabilities in discrete distributions, we introduce a purely online algorithm whose average-case performance is near-optimal with high probability for all finite sets S and all distributions of S.
Cite as

Magnus Berg and Shahin Kamali. Online Bin Covering with Frequency Predictions. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berg_et_al:LIPIcs.SWAT.2024.10,
  author =	{Berg, Magnus and Kamali, Shahin},
  title =	{{Online Bin Covering with Frequency Predictions}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.10},
  URN =		{urn:nbn:de:0030-drops-200504},
  doi =		{10.4230/LIPIcs.SWAT.2024.10},
  annote =	{Keywords: Bin Covering, Online Algorithms with Predictions, PAC Learning, Learning-Augmented Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.16
On the Online Weighted Non-Crossing Matching Problem

Authors: Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, and Denis Pankratov

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: 2n points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the unmatched previously arrived points. In the vanilla model, the decision on how to match (if at all) a newly arriving point is irrevocable. The goal is to maximize the total weight of matched points under the constraint that straight-line segments corresponding to the edges of the matching do not intersect. The unweighted version of the problem was introduced in the offline setting by Atallah in 1985, and this problem became a subject of study in the online setting with and without advice in several recent papers. We observe that deterministic online algorithms cannot guarantee a non-trivial competitive ratio for the weighted problem. We study various regimes of the problem which permit non-trivial online algorithms. In particular, when weights are restricted to the interval [1, U] we give a deterministic algorithm achieving competitive ratio Ω(2^{-2√{log U}}). We also prove that deterministic online algorithms cannot achieve competitive ratio better than O (2^{-√{log U}}). Interestingly, we establish that randomization alone suffices to achieve competitive ratio 1/3 even when there are no restrictions on the weights. Additionally, if one allows an online algorithm to revoke acceptances, then one can achieve a competitive ratio ≈ 0.2862 deterministically for arbitrary weights. We also establish a lower bound on the competitive ratio of randomized algorithms in the unweighted setting, and improve the best-known bound on advice complexity to achieve a perfect matching.
Cite as

Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, and Denis Pankratov. On the Online Weighted Non-Crossing Matching Problem. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.SWAT.2024.16,
  author =	{Boyar, Joan and Kamali, Shahin and Larsen, Kim S. and Lavasani, Ali Mohammad and Li, Yaqiao and Pankratov, Denis},
  title =	{{On the Online Weighted Non-Crossing Matching Problem}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.16},
  URN =		{urn:nbn:de:0030-drops-200567},
  doi =		{10.4230/LIPIcs.SWAT.2024.16},
  annote =	{Keywords: Online algorithms, weighted matching problem, Euclidean plane, non-crossing constraints, competitive analysis, randomized online algorithms, online algorithms with advice, online algorithms with revoking}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.13
Rényi-Ulam Games and Online Computation with Imperfect Advice

Authors: Spyros Angelopoulos and Shahin Kamali

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study the nascent setting of online computation with imperfect advice, in which the online algorithm is enhanced by some prediction encoded in the form of an imperfect, and possibly erroneous binary string. The algorithm is oblivious to the advice error, but defines a desired tolerance, namely an upper bound on the number of erroneous advice bits it can tolerate. This is a model that generalizes the Pareto-based advice model, in which the performance of the algorithm is only evaluated at the extreme values of error (namely, if the advice has either no errors, or if it is generated adversarially). It also subsumes the model in which the algorithm elicits a prediction on the online sequence, via imperfect responses to a number of binary queries. In this work, we establish connections between games with a lying responder, also known as Rényi-Ulam games, and the design and analysis of online algorithms with imperfect advice. Specifically, we demonstrate how to obtain upper and lower bounds on the competitive ratio for important online problems such as time-series search, online bidding, and fractional knapsack. Our techniques provide the first lower bounds for online problems in this model. We also highlight and exploit connections between competitive analysis with imperfect advice and fault-tolerance in multiprocessor systems. Last, we show how to waive the dependence on the tolerance parameter, by means of resource augmentation and robustification.
Cite as

Spyros Angelopoulos and Shahin Kamali. Rényi-Ulam Games and Online Computation with Imperfect Advice. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.MFCS.2023.13,
  author =	{Angelopoulos, Spyros and Kamali, Shahin},
  title =	{{R\'{e}nyi-Ulam Games and Online Computation with Imperfect Advice}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.13},
  URN =		{urn:nbn:de:0030-drops-185474},
  doi =		{10.4230/LIPIcs.MFCS.2023.13},
  annote =	{Keywords: Online computation, R\'{e}nyi-Ulam games, query models, beyond worst-case analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.52
Online Computation with Untrusted Advice

Authors: Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
The advice model of online computation captures the setting in which the online algorithm is given some partial information concerning the request sequence. This paradigm allows to establish tradeoffs between the amount of this additional information and the performance of the online algorithm. However, unlike real life in which advice is a recommendation that we can choose to follow or to ignore based on trustworthiness, in the current advice model, the online algorithm treats it as infallible. This means that if the advice is corrupt or, worse, if it comes from a malicious source, the algorithm may perform poorly. In this work, we study online computation in a setting in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust and perform well even when the advice is generated in a malicious, adversarial manner. To this end, we focus on well- studied online problems such as ski rental, online bidding, bin packing, and list update. For ski-rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved; this improves upon the framework of Purohit et al. [NeurIPS 2018] in which Pareto-optimality is not necessarily guaranteed. For bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or not; this is motivated by work of Lykouris and Vassilvitskii [ICML 2018] on the paging problem, but in which the competitiveness depends on the reliability of the advice. Furthermore, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm. Last, we study the effect of randomization: here we show that for ski-rental there is a randomized algorithm that Pareto-dominates any deterministic algorithm with advice of any size. We also show that a single random bit is not always inferior to a single advice bit, as it happens in the standard model.
Cite as

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.ITCS.2020.52,
  author =	{Angelopoulos, Spyros and D\"{u}rr, Christoph and Jin, Shendan and Kamali, Shahin and Renault, Marc},
  title =	{{Online Computation with Untrusted Advice}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.52},
  URN =		{urn:nbn:de:0030-drops-117372},
  doi =		{10.4230/LIPIcs.ITCS.2020.52},
  annote =	{Keywords: Online computation, competitive analysis, advice complexity, robust algorithms, untrusted advice}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.174
Online Bin Packing with Advice

Authors: Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We consider the online bin packing problem under the advice complexity model where the "online constraint" is relaxed and an algorithm receives partial information about the future requests. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with log(n)+o(log(n)) bits of advice, achieves a competitive ratio of 3/2 for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives 2n+o(n) bits of advice and achieves a competitive ratio of 4/3+e. Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.
Cite as

Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. Online Bin Packing with Advice. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 174-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boyar_et_al:LIPIcs.STACS.2014.174,
  author =	{Boyar, Joan and Kamali, Shahin and Larsen, Kim S. and L\'{o}pez-Ortiz, Alejandro},
  title =	{{Online Bin Packing with Advice}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{174--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.174},
  URN =		{urn:nbn:de:0030-drops-44565},
  doi =		{10.4230/LIPIcs.STACS.2014.174},
  annote =	{Keywords: online algorithms, advice complexity, bin packing}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact