% Master bibliography for the academic profile. % Managed by admin/index.html / profile_admin.cgi. @inproceedings{BibbensEtAl2026GreenBinPacking, author = {Jackson Bibbens and Cooper Sigrist and Bo Sun and Shahin Kamali and Mohammad Hajiesmaili}, authorurl3 = {https://sunbo-online.github.io/}, authorurl5 = {https://groups.cs.umass.edu/hajiesmaili/}, title = {Green Bin Packing}, booktitle = {Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems}, year = {2026}, note = {Also published in Proceedings of the ACM on Measurement and Analysis of Computing Systems, 10(1), 11:1--11:51.}, arxiv = {https://arxiv.org/abs/2510.26968}, venuekey = {SIGMETRICS}, abstract = {The online bin packing problem and its variants are regularly used to model server allocation problems. Modern concerns surrounding sustainability and overcommitment in cloud computing motivate bin packing models that capture costs associated with highly utilized servers. In this work, we introduce the \textit{green bin packing} problem, an online variant with a linear cost $\beta$ for filling above a fixed level $G$. For a given instance, the goal is to minimize the sum of the number of opened bins and the linear cost. We show that when $\beta \le 1/G$, classical online bin packing algorithms such as FirstFit or Harmonic perform well, and can achieve competitive ratios lower than in the classic setting. However, when $\beta > 1/G$, new algorithmic solutions can improve both worst-case and typical performance. We introduce variants of classic online bin packing algorithms and establish theoretical bounds, as well as test their empirical performance.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{DaneshvaramoliEtAl2026Fairness, author = {Mohammadreza Daneshvaramoli and Mohammad Hajiesmaili and Helia Karisani and Shahin Kamali and Cameron Musco}, authororder = {alphabetical}, authorurl1 = {https://moreda-a.github.io/}, authorurl2 = {https://groups.cs.umass.edu/hajiesmaili/}, authorurl5 = {https://people.cs.umass.edu/~cmusco/}, title = {Fairness in the $k$-Server Problem}, booktitle = {Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS)}, year = {2026}, pages = {45:1--45:21}, doi = {10.4230/LIPIcs.ITCS.2026.45}, url = {https://doi.org/10.4230/LIPIcs.ITCS.2026.45}, arxiv = {https://arxiv.org/abs/2512.20960}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2026-fair-k-server.pdf}, venuekey = {ITCS}, edition = {17}, abstract = {We initiate a formal study of fairness for the $k$-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of $(\alpha,\beta)$-fairness, where, for parameters $\alpha \ge 1$ and $\beta \ge 0$, no server incurs more than an $\alpha/k$-fraction of the total cost plus an additive term $\beta$. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any $\varepsilon > 0$, transforms any optimal solution into an $(\alpha,\beta)$-fair solution for $\alpha = 1 + \varepsilon$ and $\beta = O(\mathrm{diam} \cdot \log k / \varepsilon)$, while increasing the cost of the solution by just an additive $O(\mathrm{diam} \cdot k \log k / \varepsilon)$ term. Here $\mathrm{diam}$ is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when $k = 2$. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics. We further show that on uniform metrics (i.e., the paging problem), the deterministic First-In First-Out (FIFO) algorithm is fair. We show that any ``marking algorithm'', including the Least Recently Used (LRU) algorithm, also satisfies a weaker, but still meaningful notion of fairness.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliYazdani2026GeometricBurning, author = {Shahin Kamali and Saba Yazdani}, authororder = {alphabetical}, authorurl2 = {https://www.linkedin.com/in/saba-yazdani/}, title = {Geometric Burning Under $L_1$ and $L_\infty$ Metrics, and Beyond}, booktitle = {Proceedings of the 24th Workshop on Approximation and Online Algorithms (WAOA)}, year = {2026}, arxiv = {https://arxiv.org/pdf/2608.15954}, venuekey = {WAOA}, edition = {24}, abstract = {Burning is a discrete-time model for propagation in which a new fire starts in each round, while each existing fire expands by one unit of distance along the underlying metric. In geometric burning, the input is a finite point set, and the goal is to burn all points in as few rounds as possible. Equivalently, burning a point set in $k$ rounds corresponds to covering it with metric balls of distinct radii in $\{0,1,\ldots,k-1\}$; the objective is to minimize $k$. Previous work has studied the problem mainly under the Euclidean metric. In this paper, we study geometric burning under the $L_1$ and $L_\infty$ metrics. The problem remains NP-hard in both settings. The $L_1$ and $L_\infty$ metrics provide additional geometric structure, which allows us to obtain improved approximation guarantees, especially for anywhere burning. We first present a simple $(2+\varepsilon)$-approximation for both anywhere burning and point burning. We then improve the anywhere burning approximation to $7/4+\varepsilon=1.75+\varepsilon$, and give a $(3151/1620+\varepsilon)$-approximation for point burning, where $3151/1620<1.9451$. We also extend the anywhere burning result under $L_\infty$ to every fixed dimension $d\ge 3$ to achieve a $\left(2-\frac{1}{2^{d+1}}+\varepsilon\right)$-approximation. Finally, using standard comparisons between planar $L_p$ distances, we transfer our $L_1$ and $L_\infty$ algorithms, together with known Euclidean burning algorithms, to obtain approximation guarantees for every fixed $1\le p\le\infty$.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliMelzer2026SuccinctPolyominoes, author = {Shahin Kamali and Natan Melzer}, authororder = {alphabetical}, title = {Succinct Representation of Convex Polyominoes}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2026}, pages = {411--420}, doi = {10.1109/DCC66757.2026.00049}, url = {https://doi.org/10.1109/DCC66757.2026.00049}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2026-DCC.pdf}, venuekey = {DCC}, abstract = {We present a succinct representation of convex polyominoes, i.e., polyominoes whose intersection with every horizontal or vertical line forms a single contiguous segment. Our data structure uses 1.2074 n + o(n) bits, matching the information-theoretic lower bound up to lower-order terms. It supports the following "positional queries" in O(1) time: given a cell index c, "pos(c)" returns its coordinates, and given coordinates (x,y), "cell(x,y)" returns the index of the cell located at (x,y), if such a cell exists. These queries, in turn, can be used to support a wide range of other queries in constant time, including navigation (adjacency, neighborhood, degree), distance, and shortest-path queries.}, category = {conference}, display = {yes}, cv = {yes} } @article{KamEtAl2025Reconfiguration, author = {Jeffrey Kam and Shahin Kamali and Avery Miller and Naomi Nishimura}, authororder = {alphabetical}, authorurl3 = {https://home.cs.umanitoba.ca/~amiller/}, authorurl4 = {https://cs.uwaterloo.ca/~nishi/}, title = {Reconfiguration of Multisets with Applications to Bin Packing}, journal = {Algorithmica}, year = {2025}, volume = {87}, number = {12}, pages = {1933--1996}, doi = {10.1007/s00453-025-01324-w}, url = {https://doi.org/10.1007/s00453-025-01324-w}, arxiv = {https://arxiv.org/abs/2405.05535}, venuekey = {Algorithmica}, abstract = {We use the reconfiguration framework to analyze problems that involve the rearrangement of items among groups. In various applications, a group of items could correspond to the files or jobs assigned to a particular machine, and the goal of rearrangement could be improving efficiency or increasing locality. To cover problems arising in a wide range of application areas, we define the general Repacking problem as the rearrangement of multisets of multisets. We present hardness results for the general case and algorithms for various restricted classes of instances. By limiting the total size of items in each multiset, our results can be viewed as an offline approach to Bin Packing, in which each bin is represented as a multiset. In addition to providing the first results on reconfiguration of multisets, our contributions open up several research avenues: the interplay between reconfiguration and online algorithms and parallel algorithms; the use of the tools of linear programming in reconfiguration; and, in the longer term, a focus on extra resources in reconfiguration.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{AminianEtAl2025TelephoneBroadcasting, author = {Aida Aminian and Shahin Kamali and Seyed Mohammad Seyed Javadi and Sumedha}, authororder = {alphabetical}, title = {On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs}, booktitle = {Proceedings of the 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP)}, year = {2025}, pages = {10:1--10:17}, doi = {10.4230/LIPIcs.ICALP.2025.10}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2025.10}, arxiv = {https://arxiv.org/abs/2501.12316}, venuekey = {ICALP}, edition = {52}, abstract = {In the Telephone Broadcasting problem, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of its uninformed neighbors. For general graphs of n vertices, the problem is NP-complete, and the best existing algorithm has an approximation factor of O(log n/ log log n). The existence of a constant factor approximation for the general graphs is still unknown. In this paper, we study the problem in two simple families of sparse graphs, namely, cacti and graphs of bounded pathwidth. There have been several efforts to understand the complexity of the problem in cactus graphs, mostly establishing the presence of polynomial-time solutions for restricted families of cactus graphs. Despite these efforts, the complexity of the problem in arbitrary cactus graphs remained open. We settle this question by establishing the NP-completeness of telephone broadcasting in cactus graphs. For that, we show the problem is NP-complete in a simple subfamily of cactus graphs, which we call snowflake graphs. These graphs not only are cacti but also have pathwidth 2. These results establish that, despite being polynomial-time solvable in trees, the problem becomes NP-complete in very simple extensions of trees. On the positive side, we present constant-factor approximation algorithms for the studied families of graphs, namely, an algorithm with an approximation factor of 2 for cactus graphs and an approximation factor of O(1) for graphs of bounded pathwidth.}, category = {conference}, display = {yes}, cv = {yes} } @article{AngelopoulosEtAl2024UntrustedAdvice, author = {Spyros Angelopoulos and Christoph Dürr and Shendan Jin and Shahin Kamali and Marc P. Renault}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, authorurl2 = {https://perso.lip6.fr/Christoph.Durr/}, authorurl5 = {https://mrenault.sites.cs.wisc.edu/}, title = {Online Computation with Untrusted Advice}, journal = {Journal of Computer and System Sciences (JCSS)}, year = {2024}, volume = {144}, pages = {103545}, doi = {10.1016/j.jcss.2024.103545}, url = {https://doi.org/10.1016/j.jcss.2024.103545}, arxiv = {https://arxiv.org/abs/1905.05655}, venuekey = {JCSS}, abstract = {We study a generalization of the advice complexity model of online computation 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 if the advice is adversarial, and efficient is the advice is foolproof. We focus on four well-studied online problems, namely 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, whereas 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 adversarial. More importantly, 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.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{ZeynaliEtAl2024RobustDictionaries, author = {Ali Zeynali and Shahin Kamali and Mohammad Hajiesmaili}, authorurl3 = {https://groups.cs.umass.edu/hajiesmaili/}, title = {Robust Learning-Augmented Dictionaries}, booktitle = {Proceedings of the 41st International Conference on Machine Learning (ICML)}, year = {2024}, pages = {58470--58483}, url = {https://proceedings.mlr.press/v235/zeynali24a.html}, arxiv = {https://arxiv.org/abs/2402.09687}, venuekey = {ICML}, edition = {41}, abstract = {We present the first learning-augmented data structure for implementing dictionaries with optimal consistency and robustness. Our data structure, named RobustSL, is a skip list augmented by predictions of access frequencies of elements in a data sequence. With proper predictions, RobustSL has optimal consistency (achieves static optimality). At the same time, it maintains a logarithmic running time for each operation, ensuring optimal robustness, even if predictions are generated adversarially. Therefore, RobustSL has all the advantages of the recent learning-augmented data structures of Lin, Luo, and Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness guarantees that are absent in the previous work. Numerical experiments show that RobustSL outperforms alternative data structures using both synthetic and real datasets.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{LechowiczEtAl2024TimeFairness, author = {Adam Lechowicz and Rik Sengupta and Bo Sun and Shahin Kamali and Mohammad Hajiesmaili}, authorurl1 = {https://adamlechowicz.github.io/}, authorurl3 = {https://sunbo-online.github.io/}, authorurl5 = {https://groups.cs.umass.edu/hajiesmaili/}, title = {Time Fairness in Online Knapsack Problems}, booktitle = {Proceedings of the 12th International Conference on Learning Representations (ICLR)}, year = {2024}, url = {https://openreview.net/forum?id=9kG7TwgLYu}, arxiv = {https://arxiv.org/abs/2305.13293}, venuekey = {ICLR}, edition = {12}, abstract = {The online knapsack problem is a classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriving online into a capacity-limited knapsack so as to maximize the total value of the admitted items. Although optimal competitive algorithms are known for this problem, they may be fundamentally \emph{unfair}, i.e., individual items may be treated inequitably in different ways. We formalize a practically-relevant notion of time fairness which effectively models a trade off between static and dynamic pricing in a motivating application such as cloud resource allocation, and show that existing algorithms perform poorly under this metric. We propose a parameterized deterministic algorithm where the parameter precisely captures the Pareto-optimal trade-off between fairness (static pricing) and competitiveness (dynamic pricing). We show that randomization is theoretically powerful enough to be simultaneously competitive and fair; however, it does not work well in experiments. To further improve the trade-off between fairness and competitiveness, we develop a nearly-optimal learning-augmented algorithm which is fair, consistent, and robust (competitive), showing substantial performance improvements in numerical experiments.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BergEtAl2024Polyominoes, author = {Magnus Berg and Shahin Kamali and Katherine Ling and Cooper Sigrist}, authororder = {alphabetical}, title = {Space-Efficient Data Structures for Polyominoes and Bar Graphs}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2024}, pages = {253--262}, doi = {10.1109/DCC58796.2024.00033}, url = {https://doi.org/10.1109/DCC58796.2024.00033}, arxiv = {https://arxiv.org/abs/2311.16957}, venuekey = {DCC}, abstract = {We provide a compact data structure for representing polyominoes that supports neighborhood and visibility queries. Neighborhood queries concern reporting adjacent cells to a given cell, and visibility queries determine whether a straight line can be drawn within the polyomino that connects two specified cells. For an arbitrary small $\epsilon >0$, our data structure can encode a polyomino with $n$ cells in $(3+\epsilon)n + o(n)$ bits while supporting all queries in constant time. The space complexity can be improved to $3n+o(n)$, while supporting neighborhood queries in $\mathcal{O}(1)$ and visibility queries in $\mathcal{O}(t(n))$ for any arbitrary $t(n) \in \omega(1)$. Previous attempts at enumerating polyominoes have indicated that at least $2.00091n - o(n)$ bits are required to differentiate between distinct polyominoes, which shows our data structure is compact. In addition, we introduce a succinct data structure tailored for bar graphs, a specific subclass of polyominoes resembling histograms. We show that a bar graph comprising $n$ cells can be encoded using $n + o(n)$ bits, enabling constant-time query processing. Meanwhile, $n-1$ bits are necessary to represent any bar graph, proving our data structure is succinct.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BergKamali2024BinCoveringPredictions, author = {Magnus Berg and Shahin Kamali}, authororder = {alphabetical}, title = {Online Bin Covering with Frequency Predictions}, booktitle = {Proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT)}, year = {2024}, pages = {10:1--10:17}, doi = {10.4230/LIPIcs.SWAT.2024.10}, url = {https://doi.org/10.4230/LIPIcs.SWAT.2024.10}, arxiv = {https://arxiv.org/abs/2401.14881}, venuekey = {SWAT}, edition = {19}, abstract = {We study the discrete bin covering problem where a multiset of items from a fixed set S in(0,1] must be split into disjoint subsets while maximizing the number of subsets whose contents sum to at least 1. We study 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 12 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 also 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.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BoyarEtAl2024WeightedNonCrossing, author = {Joan Boyar and Shahin Kamali and Kim S. Larsen and Ali Mohammad Lavasani and Yaqiao Li and Denis Pankratov}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl3 = {https://imada.sdu.dk/u/kslarsen/}, authorurl5 = {https://li-ya-qiao.github.io/}, authorurl6 = {https://www.concordia.ca/faculty/denis-pankratov.html}, title = {On the Online Weighted Non-Crossing Matching Problem}, booktitle = {Proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT)}, year = {2024}, pages = {16:1--16:19}, arxiv = {https://arxiv.org/abs/2603.09262}, venuekey = {SWAT}, edition = {19}, 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 $\Omega\left(2^{-2\sqrt{\log U}}\right)$. We also prove that deterministic online algorithms cannot achieve a competitive ratio better than $O\left(2^{-\sqrt{\log U}}\right)$. Interestingly, we establish that randomization alone suffices to achieve a 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.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{SantosEtAl2024SecondLayer, author = {Saulo dos Santos and Japjeet Singh and Bakhshish Singh Dhillon and Ruppa K. Thulasiram and Shahin Kamali}, authorurl1 = {https://sites.google.com/view/saulodossantos/home}, authorurl4 = {https://umanitoba.ca/science/directory/computer-science/ruppa-thulasiram}, title = {Second Layer Network Impact on Bitcoin Mining Fees and Network Value}, booktitle = {Proceedings of the 6th International Conference on Blockchain and Cryptocurrency (ICBC)}, year = {2024}, pages = {1--2}, note = {2-page paper}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2024-second-layer.pdf}, venuekey = {ICBC}, edition = {6}, abstract = {This paper explores the impact of second-layer solutions, particularly the Lightning Network (LN), on Bitcoin mining fees. The introduction of LN promises enhanced transaction efficiency by facilitating faster and more economical off-chain transactions. Such advancements, while beneficial for network scalability, pose potential challenges to miners’ fee revenues—especially from lower-value transactions. We propose a comprehensive framework to assess the ramifications of LN adoption on miners’ fee earnings, taking into account the shift of transactions to LN. This framework not only evaluates the direct negative effects on miners’ fees but also examines the broader implications for Bitcoin’s network value as LN adoption increases, user base expands, and transaction volume grows. Moreover, our framework introduce the potential of LN to onboard millions of new users, particularly through the adoption by Superhubs. This significant expansion in network participation is posited to elevate Bitcoin’s overall value, potentially offsetting the initial decrease in mining fees.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{SantosEtAl2024LightningNetwork, author = {Saulo dos Santos and Japjeet Singh and Bakhshish Singh Dhillon and Ruppa K. Thulasiram and Cuneyt Akcora and Shahin Kamali}, authorurl1 = {https://sites.google.com/view/saulodossantos/home}, authorurl4 = {https://umanitoba.ca/science/directory/computer-science/ruppa-thulasiram}, title = {On the Impact of the Lightning Network on Bitcoin Transaction Fees and Network Value}, booktitle = {Proceedings of the 7th IEEE International Conference on Blockchain (IEEE Blockchain)}, year = {2024}, pages = {148--156}, doi = {10.1109/Blockchain62396.2024.00028}, url = {https://doi.org/10.1109/Blockchain62396.2024.00028}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2024-Lightning.pdf}, venuekey = {IEEEBlockchain}, edition = {7}, abstract = {This paper examines the influence of second-layer networks, notably the Lightning Network (LN), on Bitcoin mining fees and network valuation through Metcalfe’s law. Analyzing Bitcoin transaction data from January 2014 to November 2023, with a focus on transactions below USD 1000, we find that these transactions constitute over 27% of total mining fees in 2023, underscoring their economic importance. The LN’s facilitation of faster, cheaper off-chain transactions could notably decrease miners’ fee revenues, especially from smaller transactions which are a significant revenue source. We employ Metcalfe’s law to model Bitcoin’s value over the next six years, correlating it with the number of daily active users to gauge network growth. Incorporating LN adoption rates into our model suggests that while LN may reduce fee-based income for miners in Bitcoin terms, it is poised to enhance Bitcoin’s overall network value by expanding the user base and transaction volume. This growth, driven by LN’s improved utility and scalability, suggests a long-term net benefit despite shortterm fee revenue losses. Our analysis focused on LN’s capacity to integrate millions of new users through its adoption by Superhubs, which could exponentially boost network value, counterbalancing the potential dip in mining fees. We explore LN’s broader adoption implications, envisioning its role in expanding the Bitcoin value proposition from a Store of Value (SoV) to a Medium of Exchange (MoE). By applying Metcalfe’s law, we offer insights into the economic effects of LN’s widespread use, contributing to discussions on Bitcoin’s scalability, mining sustainability, and digital currency valuation.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamEtAl2024Reconfiguration, author = {Jeffrey Kam and Shahin Kamali and Avery Miller and Naomi Nishimura}, authororder = {alphabetical}, authorurl3 = {https://home.cs.umanitoba.ca/~amiller/}, authorurl4 = {https://cs.uwaterloo.ca/~nishi/}, title = {Reconfiguration of Multisets with Applications to Bin Packing}, booktitle = {Proceedings of the 18th International Conference and Workshop on Algorithms and Computation (WALCOM)}, year = {2024}, pages = {212--226}, arxiv = {https://arxiv.org/abs/2405.05535}, venuekey = {WALCOM}, edition = {18}, abstract = {We use the reconfiguration framework to analyze problems that involve the rearrangement of items among groups. In various applications, a group of items could correspond to the files or jobs assigned to a particular machine, and the goal of rearrangement could be improving efficiency or increasing locality. To cover problems arising in a wide range of application areas, we define the general \textsc{Repacking} problem as the rearrangement of multisets of multisets. We present hardness results for the general case and algorithms for various classes of instances that arise in real-life scenarios. By limiting the total size of items in each multiset, our results can be viewed as an offline approach to \textsc{Bin Packing}, in which each bin is represented as a multiset. In addition to providing the first results on reconfiguration of multisets, our contributions open up several research avenues:the interplay between reconfiguration and online algorithms and parallel algorithms; the use of the tools of linear programming in reconfiguration; and, in the longer term, a focus on resources in reconfiguration.}, category = {conference}, display = {yes}, cv = {yes} } @article{AngelopoulosKamali2023ContractScheduling, author = {Spyros Angelopoulos and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Contract Scheduling with Predictions}, journal = {Journal of Artificial Intelligence Research (JAIR)}, year = {2023}, volume = {77}, pages = {395--426}, url = {https://www.jair.org/index.php/jair}, arxiv = {https://arxiv.org/abs/2011.12439}, venuekey = {JAIR}, abstract = {Contract scheduling is a general technique that allows the design of systems with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study new settings in which the scheduler has access to some imperfect prediction in regards to the interruption. In the first setting, which is inspired by recent advances in learning-enhanced algorithms, the prediction describes the time that the interruption occurs. The second setting introduces a new model in which predictions are elicited as responses to a number of binary queries. For both settings, we investigate trade-offs between the robustness (i.e., the worst-case performance of the schedule if the prediction is generated adversarially) and the consistency (i.e., the performance assuming that the prediction is error-free). We also establish results on the performance of the schedules as a function of the prediction error.}, category = {journal}, display = {yes}, cv = {yes} } @article{AngelopoulosEtAl2023BinPackingPredictions, author = {Spyros Angelopoulos and Shahin Kamali and Kimia Shadkami}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Online Bin Packing with Predictions}, journal = {Journal of Artificial Intelligence Research (JAIR)}, year = {2023}, volume = {78}, pages = {1111--1141}, arxiv = {https://arxiv.org/abs/2102.03311}, venuekey = {JAIR}, abstract = {Bin packing is a classic optimization problem with a wide range of applications from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with effcient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error), and whose performance degrades nearoptimally as a function of the prediction error. This is the frst theoretical and experimental study of online bin packing in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error, and relied on overly powerful and error-free oracles.}, category = {journal}, display = {yes}, cv = {yes} } @article{BastideEtAl2023ImprovedPyrotechnics, author = {Paul Bastide and Marthe Bonamy and Anthony Bonato and Pierre Charbit and Shahin Kamali and Théo Pierron and Mikael Rabie}, authororder = {alphabetical}, authorurl1 = {https://perso.eleves.ens-rennes.fr/people/paul.bastide/}, authorurl2 = {https://www.labri.fr/perso/mbonamy/}, authorurl3 = {https://math.ryerson.ca/~abonato/}, authorurl4 = {https://www.irif.fr/~charbit/index-anglais.html}, authorurl6 = {https://perso.liris.cnrs.fr/tpierron/index.html}, title = {Improved Pyrotechnics: Closer to the Burning Number Conjecture}, journal = {The Electronic Journal of Combinatorics}, year = {2023}, volume = {30}, number = {4}, pages = {P4.2}, doi = {10.37236/11113}, url = {https://doi.org/10.37236/11113}, arxiv = {https://arxiv.org/abs/2110.10530}, venuekey = {EJC}, abstract = {The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best-known result was for graphs with minimum degree $23$.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{AngelopoulosKamali2023RenyiUlam, author = {Spyros Angelopoulos and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Rényi-Ulam Games and Online Computation with Imperfect Advice}, booktitle = {Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS)}, year = {2023}, pages = {13:1--13:15}, doi = {10.4230/LIPIcs.MFCS.2023.13}, url = {https://doi.org/10.4230/LIPIcs.MFCS.2023.13}, arxiv = {https://arxiv.org/abs/2301.01631}, venuekey = {MFCS}, edition = {48}, 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\'enyi-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.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BoyarEtAl2023IntervalScheduling, author = {Joan Boyar and Lene M. Favrholdt and Shahin Kamali and Kim S. Larsen}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl4 = {https://imada.sdu.dk/u/kslarsen/}, title = {Online Interval Scheduling with Predictions}, booktitle = {Proceedings of the 18th International Symposium on Algorithms and Data Structures (WADS)}, year = {2023}, pages = {193--207}, arxiv = {https://arxiv.org/abs/2302.13701}, github = {https://github.com/shahink84/IntervalSchedulingWithPrediction}, venuekey = {WADS}, edition = {18}, abstract = {In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each involving a pair of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. These problems have been studied under extreme settings without information about the input or with error-free advice. We study an intermediate setting with a potentially erroneous prediction that specifies the set of intervals/requests forming the input sequence. For both problems, we provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. For disjoint path allocation, our lower bound rules out any improvement over a simple algorithm that fully trusts predictions, whereas, for interval scheduling, we develop a superior algorithm. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{DurocherEtAl2023CopsRobbers, author = {Stephane Durocher and Shahin Kamali and Myroslav Kryven and Fengyi Liu and Amirhossein Mashghdoust and Avery Miller and Pouria Zamani Nezhad and Ikaro Penha Costa and Timothy Zapp}, authororder = {alphabetical}, authorurl1 = {https://home.cs.umanitoba.ca/~durocher/}, authorurl3 = {https://myroslavkryven.gitlab.io/website/}, authorurl6 = {https://home.cs.umanitoba.ca/~amiller/}, title = {Cops and Robbers on 1-Planar Graphs}, booktitle = {Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD)}, year = {2023}, note = {Pages were listed as TBD on the source webpage.}, arxiv = {https://arxiv.org/abs/2309.01001}, venuekey = {GD}, edition = {31}, abstract = {Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along edges of G. The cop number of G is the minimum number of cops that is sufficient to catch the robber. Every planar graph has cop number at most three, and there are planar graphs for which three cops are necessary [Aigner and Fromme, DAM 1984]. We study the problem for beyond-planar graphs, that is, graphs that can be drawn in the plane with few crossings. In particular, we focus on 1-planar graphs, that is, graphs that can be drawn in the plane with at most one crossing per edge. In contrast to planar graphs, we show that some 1-planar graphs have unbounded cop number. Meanwhile, for maximal 1-planar graphs, we prove that three cops are always sufficient and sometimes necessary. In addition, we characterize outer 1-planar graphs with respect to their cop number.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{DurocherEtAl2023SquarePackingPredictions, author = {Stephane Durocher and Shahin Kamali and Pouria Zamani Nezhad}, authororder = {alphabetical}, authorurl1 = {https://home.cs.umanitoba.ca/~durocher/}, title = {Online Square Packing with Predictions}, booktitle = {Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG)}, year = {2023}, pages = {9--18}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2023-CCCG2023-Packing.pdf}, venuekey = {CCCG}, edition = {35}, abstract = {Square packing is a geometric variant of the classic bin packing problem, which asks for the placement of squares of various lengths into a minimum number of unit squares. In this work, we study the online variant of the problem in which the input squares appear sequentially, and each square must be packed before the next square is revealed. We study the problem under the prediction setting, where the online algorithm is enhanced with a potentially erroneous prediction about the input sequence. We design an online algorithm that receives predictions concerning the sizes of input squares and analyze its consistency (the competitive ratio assuming no error in the predictions) and robustness (the competitive ratio under adversarial error). In particular, our algorithm has consistency $1.77\bar{9}$ and robustness at most $5.89$. These results show improvements over the best previous algorithm, designed for perfect predictions, with a consistency of 1.84 and a robustness of at least 21. We also show that the competitive ratio of our algorithm degrades slowly as the error increases.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliShabanijou2023BurningPlanar, author = {Shahin Kamali and Mohammadmasoud Shabanijou}, authororder = {alphabetical}, title = {Improved Algorithms for Burning Planar Point Sets}, booktitle = {Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG)}, year = {2023}, pages = {161--167}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2023-CCCG2023-Burning.pdf}, venuekey = {CCCG}, edition = {35}, abstract = {Given a set P of points in the plane, the geometric burning problem asks for minimizing the number of rounds to ``burn" P. It is possible to burn P in k rounds if one can cover all points in P with k disks of distinct radii from {0,1, ..., k-1}. In the anywhere-burning variant of the problem, the disks can be located at any position in the plane, while in the point-burning variant, they must be centered at points of P. Both variants are NP-hard, and the best existing algorithms have approximation factors of 1.92188 + epsilon and 1.96296 + epsilon for anywhere and point burning [Gokhale1 et al. WALCOM 2023]. In this paper, we present techniques for improving these algorithms. We first present a simple anywhere burning algorithm with an approximation factor of at most 1.865 + epsilon, and then improve this algorithm to achieve an approximation factor of 11/6 + epsilon \approx 1.833 + \epsilon for arbitrary small epsilon > 0. We also present a point-burning algorithm with an improved approximation factor of at most 1.944+\epsilon.}, category = {conference}, display = {yes}, cv = {yes} } @article{Kamali2022CompactBandwidth, author = {Shahin Kamali}, title = {Compact Representation of Graphs with Small Bandwidth or Treedepth}, journal = {Information and Computation}, year = {2022}, volume = {285}, pages = {104867--104879}, url = {https://doi.org/10.1016/j.ic.2021.104867}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2022-InfComp.pdf}, venuekey = {InfComput}, abstract = {We study the problem of compact representation of graphs that have small bandwidth as well as graphs that have small treedepth. We present navigation oracles that support degree and adjacency queries in constant time and neighborhood queries in constant time per neighbor. For graphs of size n and bandwidth k, our oracle takes $(k + \lceil \log 2k \rceil)n +o(kn)$ bits. We also show that $(k-5\sqrt{k}-4)n - O(k^2)$ bits are required to encode such graphs. For graphs of size n and treedepth k, we present an oracle that takes $(k + \lceil \log k \rceil + 2)n + o(kn)$ bits and complement it with lower bounds that show our oracle is compact for specific ranges of k. Our navigation oracles for both treedepth and treedepth parameters can be augmented, with additional $n + o(n)$ bits, to support connectivity queries in constant time.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{AngelopoulosEtAl2022OnlineSearch, author = {Spyros Angelopoulos and Shahin Kamali and Dehou Zhang}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Online Search With Best-Price and Query-Based Predictions}, booktitle = {Proceedings of the 36th AAAI Conference on Artificial Intelligence}, year = {2022}, pages = {9652--9660}, arxiv = {https://arxiv.org/abs/2112.01592}, github = {https://github.com/shahink84/OnlineSearchRBIS}, venuekey = {AAAI}, edition = {36}, abstract = {In the online (time-series) search problem, a player is presented with a sequence of prices which are revealed in an online manner. In the standard definition of the problem, for each revealed price, the player must decide irrevocably whether to accept or reject it, without knowledge of future prices (other than an upper and a lower bound on their extreme values), and the objective is to minimize the competitive ratio, namely the worst case ratio between the maximum price in the sequence and the one selected by the player. The problem formulates several applications of decision-making in the face of uncertainty on the revealed samples. Previous work on this problem has largely assumed extreme scenarios in which either the player has almost no information about the input, or the player is provided with some powerful, and error-free advice. In this work, we study learning-augmented algorithms, in which there is a potentially erroneous prediction concerning the input. Specifically, we consider two different settings: the setting in which the prediction is related to the maximum price in the sequence, as well as well as the setting in which the prediction is obtained as a response to a number of binary queries. For both settings, we provide tight, or near-tight upper and lower bounds on the worst-case performance of search algorithms as a function of the prediction error. We also provide experimental results on data obtained from stock exchange markets that confirm the theoretical analysis, and explain how our techniques can be applicable to other learning-augmented applications.}, category = {conference}, display = {yes}, cv = {yes}, github2 = {https://github.com/DehouZhang/Online-Search-with-Predictions} } @inproceedings{AngelopoulosEtAl2022BinPackingPredictions, author = {Spyros Angelopoulos and Shahin Kamali and Kimia Shadkami}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Online Bin Packing with Predictions}, booktitle = {Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI)}, year = {2022}, pages = {4574--4580}, url = {https://www.ijcai.org/proceedings/2022/0635.pdf}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2022-IJCAI-BP.pdf}, arxiv = {https://arxiv.org/abs/2102.03311}, github = {https://github.com/shahink84/BinPackingPredictions}, venuekey = {IJCAI}, edition = {31}, abstract = {Bin packing is a classic optimization problem with a wide range of applications from load balancing in networks to supply chain management. In this work we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between their consistency (i.e., the competitive ratio assuming no prediction error) and their robustness (i.e., the competitive ratio under adversarial error), and whose performance degrades gently as a function of the error. Previous work on this problem has only addressed the extreme cases with respect to the prediction error, and has relied on overly powerful and error-free prediction oracles.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliNikbakht2022SquarePackingRotation, author = {Shahin Kamali and Pooya Nikbakht}, authororder = {alphabetical}, authorurl2 = {https://www.pooya.website/home}, title = {Online Square Packing with Rotation}, booktitle = {Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG)}, year = {2022}, pages = {189--197}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2022-CCCG2022_paper_62.pdf}, venuekey = {CCCG}, edition = {34}, abstract = {We consider the square packing problem, where the goal is to place a multiset of square items of different side-lengths in $(0,1]$ into a minimum number of square bins of uniform side-length 1. We study the problem under the online setting, where the multiset of items forms a sequence revealed in an online and sequential manner. An online algorithm must place each item into a square bin without prior knowledge of the forthcoming items. Most existing results assume square items are placed orthogonally to the square bins (that is, parallel to the sides of the bins). In the presence of rotation, Kamali and Nikbakht [COCOA 2020] proved that the offline problem is NP-hard and admits an APTAS in an augmented setting. This paper investigates the online problem when item rotation is allowed. We introduce a linear-time algorithm that achieves an asymptotic competitive ratio of \sqUpper when square-items have any size $x\in(0,1]$, and a better asymptotic competitive ratio of $1.732$ when $x \in (0,1/2]$. We also study another problem where items, instead of squares, are isosceles right triangles (half-squares) and present a linear-time online algorithm with an asymptotic competitive ratio of at most 1.897.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{SantosEtAl2022DeFiReview, author = {Saulo dos Santos and Japjeet Singh and Ruppa K. Thulasiram and Shahin Kamali and Louis Sirico and Lisa Loud}, authorurl1 = {https://sites.google.com/view/saulodossantos/home}, authorurl3 = {https://umanitoba.ca/science/directory/computer-science/ruppa-thulasiram}, title = {A New Era of Blockchain-Powered Decentralized Finance (DeFi) -- A Review}, booktitle = {Proceedings of the 46th IEEE Annual Computers, Software, and Applications Conference (COMPSAC)}, year = {2022}, pages = {1286--1292}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2022-Blockchain-Review.pdf}, venuekey = {COMPSAC}, edition = {46}, abstract = {The Bitcoin whitepaper published in 2008 pro-posed a novel decentralized ledger, later called blockchain, which enabled multiple transacting parties to agree upon the shared state of the ledger without a trusted intermediary. Blockchain technology has been used to implement many decentralized payment systems, with the general term Cryptocurrency coined for the native unit of values. The launch of the Turing-complete Ethereum blockchain in 2015 extended the scope of blockchain-based financial systems beyond cryptocurrencies. The suite of non-custodial financial solutions deployed as Smart Contracts over Turing-complete blockchains is broadly called Decentralized Finance (DeFi). These solutions have gained widespread popularity as investment vehicles in the last two years, with their total value locked (TVL) exceeding USD 100 Billion. This paper reviews the key financial services offered in DeFi and draws a parallel to the corresponding services in the centralized financial industry. Some technical and economic risks associated with the DeFi investments are also discussed in the paper. Most of the existing review papers on DeFi focus on some specific DeFi services, are theoretically inclined, and are intended for academics in computer science or economics. This paper, on the other hand, aims to give an overview of the current state of the DeFi ecosystem. We aim to keep this review lucid to make it accessible to a broader audience without compromising academic rigor. The intended audience for this paper includes anyone with a basic understanding of financial markets and blockchain systems. This work will be specifically helpful for investment professionals to understand the rapidly evolving ecosystem of DeFi services.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliEtAl2022RandomizedMatching, author = {Shahin Kamali and Pooya Nikbakht and Arezoo Sajadpour}, authororder = {alphabetical}, authorurl2 = {https://www.pooya.website/home}, title = {A Randomized Algorithm for Non-crossing Matching of Online Points}, booktitle = {Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG)}, year = {2022}, pages = {198--204}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2022-CCCG2022_paper_65.pdf}, venuekey = {CCCG}, edition = {34}, abstract = {We study randomized algorithms for the online non-crossing matching problem. Given an online sequence of $n$ online points in general position, the goal is to create a matching of maximum size so that the line segments connecting pairs of matched points do not cross. In previous work, Bose et al. [CCCG 2020] showed that a simple greedy algorithm matches at least $\lceil 2n/3 - 1/3 \rceil \approx 0.\bar{66}n$ points, and it is the best that any deterministic algorithm can achieve. In this paper, we show that randomization helps achieve a better competitive ratio; that is, we present a randomized algorithm that is expected to match at least $235n/351 - 202/351 \approx 0.6695n$ points.}, category = {conference}, display = {yes}, cv = {yes} } @article{BoyarEtAl2021BinCoveringAdvice, author = {Joan Boyar and Lene M. Favrholdt and Shahin Kamali and Kim S. Larsen}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl4 = {https://imada.sdu.dk/u/kslarsen/}, title = {Online Bin Covering with Advice}, journal = {Algorithmica}, year = {2021}, volume = {83}, number = {3}, pages = {795--821}, arxiv = {https://arxiv.org/abs/1905.00066}, venuekey = {Algorithmica}, abstract = {The bin covering problem asks for covering a maximum number of bins with an online sequence of $n$ items of different sizes in the range $(0,1]$; a bin is said to be covered if it receives items of total size at least~$1$. We study this problem in the advice setting and provide asymptotically tight bounds of $\Theta(n \log$ Opt$)$ on the size of advice required to achieve optimal solutions. Moreover, we show that any algorithm with advice of size $o(\log \log n)$ has a competitive ratio of at most~$0.5$. In other words, advice of size $o(\log \log n)$ is useless for improving the competitive ratio of~$0.5$, attainable by an online algorithm without advice. This result highlights a difference between the bin covering and the bin packing problems in the advice model: for the bin packing problem, there are several algorithms with advice of constant size that outperform online algorithms without advice. Furthermore, we show that advice of size $O(\log \log n)$ is sufficient to achieve a competitive ratio that is arbitrarily close to~$0.53\bar{3}$ and hence strictly better than the best ratio~$0.5$ attainable by purely online algorithms. The technicalities involved in introducing and analyzing this algorithm are quite different from the existing results for the bin packing problem and confirm the different nature of these two problems. Finally, we show that a linear number of advice bits is necessary to achieve any competitive ratio better than $15/16$ for the online bin covering problem.}, category = {journal}, display = {yes}, cv = {yes} } @article{AzizEtAl2021PrivateGWAS, author = {Md Momin Al Aziz and Shahin Kamali and Noman Mohammed and Xiaoqian Jiang}, title = {Online Algorithm for Differentially Private Genome-wide Association Studies}, journal = {ACM Transactions on Computing for Healthcare}, year = {2021}, volume = {2}, number = {2}, pages = {13:1--13:27}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2021-ACM_TCH_3431504.pdf}, github = {https://github.com/mominbuet/DifferentialPrivacyGWAS}, venuekey = {ACMTOCH}, abstract = {Digitization of healthcare records contributed to a large volume of functional scientific data that can help researchers to understand the behaviour of many diseases. However, the privacy implications of this data, particularly genomics data, have surfaced recently as the collection, dissemination, and analysis of human genomics data is highly sensitive. There have been multiple privacy attacks relying on the uniqueness of the human genome that reveals a participant or a certain groups' presence in a dataset. Therefore, the current data sharing policies have ruled out any public dissemination and adopted precautionary measures prior to genomics data release, which hinders timely scientific innovation. In this article, we investigate an approach that only releases the statistics from genomic data rather than the whole dataset and propose a generalized Differentially Private mechanism for Genome-wide Association Studies (GWAS). Our method provides a quantifiable privacy guarantee that adds noise to the intermediate outputs but ensures satisfactory accuracy of the private results. Furthermore, the proposed method offers multiple adjustable parameters that the data owners can set based on the optimal privacy requirements. These variables are presented as equalizers that balance between the privacy and utility of the GWAS. The method also incorporates Online Bin Packing technique, which further bounds the privacy loss linearly, growing according to the number of open bins and scales with the incoming queries. Finally, we implemented and benchmarked our approach using seven different GWAS studies to test the performance of the proposed methods. The experimental results demonstrate that for 1,000 arbitrary online queries, our algorithms are more than 80% accurate with reasonable privacy loss and exceed the state-of-the-art approaches on multiple studies (i.e., EigenStrat, LMM, TDT).}, category = {journal}, display = {yes}, cv = {yes} } @article{DurrKamali2021BufferManagement, author = {Christoph Dürr and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Christoph.Durr/}, title = {Randomized Two-valued Bounded Delay Online Buffer Management}, journal = {Operations Research Letters}, year = {2021}, volume = {49}, number = {2}, pages = {246--249}, arxiv = {https://arxiv.org/abs/2004.14715}, venuekey = {ORL}, abstract = {In the bounded delay buffer management problem unit size packets arrive online to be sent over a network link. The objective is to maximize the total weight of packets sent before their deadline. In this paper we are interested in the two-valued variant of the problem, where every packet has either low (1) or high priority weight ($\alpha>1$). We show that the optimal randomized competitive ratio against an oblivious adversary is $1+(\alpha-1)/(\alpha^2+\alpha)$.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{Kamali2021CompactPolyominoes, author = {Shahin Kamali}, authorurl1 = {https://www.eecs.yorku.ca/~kamalis/papers/Compact_Polyominoes.pdf}, title = {Compact Polyominoes}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2021}, pages = {346}, note = {Short paper.}, url = {https://ieeexplore.ieee.org/document/9418759}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2021-Compact_Polyominoes.pdf}, venuekey = {DCC}, abstract = {We provide a compact representation of polyominoes with $n$ cells that supports navigation and visibility queries in constant time. Our oracle takes $3n + o(n)$ bits. Previous enumeration efforts indicate that at least $2.00091 n - o(n)$ bits (likely $2.021 n - o(n)$ bits) are required to distinguish polyominoes, hence confirming that our oracle is compact.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{AngelopoulosKamali2021ContractScheduling, author = {Spyros Angelopoulos and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Contract Scheduling With Predictions}, booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence}, year = {2021}, pages = {11726--11733}, arxiv = {https://arxiv.org/abs/2011.12439}, github = {https://github.com/shahink84/ContractSchdulingWithPredictions}, venuekey = {AAAI}, edition = {35}, abstract = {Contract scheduling is a general technique that allows to design a system with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has largely assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study the setting in which there is a potentially erroneous {\em prediction} concerning the interruption. Specifically, we consider the setting in which the prediction describes the time that the interruption occurs, as well as the setting in which the prediction is obtained as a response to a single or multiple binary queries. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e, the performance assuming that the prediction is error-free), both from the side of positive and negative results.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliXu2021MulticoreCaching, author = {Shahin Kamali and Helen Xu}, authororder = {alphabetical}, authorurl2 = {https://itshelenxu.github.io/}, title = {Beyond Worst-case Analysis of Multicore Caching Strategies}, booktitle = {Proceedings of the SIAM-ACM Symposium on Algorithmic Principles of Computer Systems (APoCS)}, year = {2021}, pages = {1--15}, arxiv = {https://arxiv.org/abs/2011.02046}, venuekey = {APoCS}, abstract = {Every processor with multiple cores sharing a cache needs to implement a cache-replacement algorithm. Previous work demonstrated that the competitive ratio of a large class of online algorithms, including Least-Recently-Used (LRU), grows with the length of the input. Furthermore, even offline algorithms like Furthest-In-Future, the optimal algorithm in single-core caching, cannot compete in the multicore setting. These negative results motivate a more in-depth comparison of multicore caching algorithms via alternative analysis measures. Specifically, the power of the adversary to adapt to online algorithms suggests the need for a direct comparison of online algorithms to each other. In this paper, we introduce cyclic analysis, a generalization of bijective analysis introduced by Angelopoulos and Schweitzer [JACM'13]. Cyclic analysis captures the advantages of bijective analysis while offering flexibility that makes it more useful for comparing algorithms for a variety online problems. In particular, we take the first steps beyond worst-case analysis for analysis of multicore caching algorithms. We use cyclic analysis to establish relationships between multicore caching algorithms, including the advantage of LRU over all other multicore caching algorithms in the presence of locality of reference.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliNikbakht2021FaultTolerantBinPacking, author = {Shahin Kamali and Pooya Nikbakht}, authororder = {alphabetical}, authorurl2 = {https://www.pooya.website/home}, title = {On the Fault-Tolerant Online Bin Packing Problem}, booktitle = {Proceedings of the International Conference on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)}, year = {2021}, pages = {1--17}, arxiv = {https://arxiv.org/abs/2107.02922}, venuekey = {ALGOCLOUD}, abstract = {We study the fault-tolerant variant of the online bin packing problem. Similar to the classic bin packing problem, an online sequence of items of various sizes should be packed into a minimum number of bins of uniform capacity. For applications such as server consolidation, where bins represent servers and items represent jobs of various loads, it is necessary to maintain fault-tolerant solutions. In a fault-tolerant packing, any job is replicated into $f+1$ servers, for some integer $f>1$, so that the failure of up to $f$ servers does not interrupt service. We build over a practical model introduced by Li and Tang [SPAA 2017] in which each job of load $x$ has a primary replica of load $x$ and $f$ standby replicas, each of load $x/\eta$, where $\eta >1$ is a parameter of the problem. Upon failure of up to $f$ servers, any primary replica in a failed bin should be replaced by one of its standby replicas so that the extra load of the new primary replica does not cause an overflow in its bin. We study a general setting in which bins might fail while the input is still being revealed. Our main contribution is an algorithm, named \Alg, which maintains fault-tolerant packings under this general setting. We prove that \Alg has an asymptotic competitive ratio of at most 1.75. This is an improvement over the best existing asymptotic competitive ratio 2 of an algorithm by Li and Tang [TPDS 2020], which works under a model that assumes bins fail only after all items are packed.}, category = {conference}, display = {yes}, cv = {yes} } @misc{AngelopoulosEtAl2021CompetitiveSequencing, author = {Spyros Angelopoulos and Diogo Arsénio and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, authorurl2 = {https://nyuad.nyu.edu/en/academics/divisions/science/faculty/diogo-arsenio.html}, title = {Competitive Sequencing with Noisy Advice}, year = {2021}, note = {Preprint.}, arxiv = {https://arxiv.org/abs/2111.05281}, abstract = {Several well-studied online resource allocation problems can be formulated in terms of infinite, increasing sequences of positive values, in which each element is associated with a corresponding allocation value. Examples include problems such as online bidding, searching for a hidden target on an unbounded line, and designing interruptible algorithms based on contract scheduling. The performance of the online algorithm, in each of these problems, is measured by the competitive ratio, which describes the multiplicative performance loss due to the absence of full information on the instance. We study such competitive sequencing problems in a setting in which the online algorithm has some (potentially) erroneous information, expressed as a $k$-bit advice string, for some given $k$. For concreteness, we follow the formulation of contract scheduling as case study. We first consider the {\em untrusted} advice setting of [Angelopoulos et al, ITCS 2020], in which the objective is to obtain a Pareto-optimal schedule, considering the two extremes: either the advice is either error-free, or it is generated by a (malicious) adversary. Here, we show a Pareto-optimal schedule, using a new approach for applying the functional-based lower-bound technique due to [Gal, Israel J. Math. 1972]. Next, we study a nascent {\em noisy} advice setting, in which a number of the advice bits may be erroneous; the exact error is unknown to the online algorithm, which only has access to a pessimistic estimate (i.e., an upper bound on this error). We give improved upper bounds, but also the first lower bound on the competitive ratio of an online problem in this setting. To this end, we combine ideas from robust query-based search in arrays, and fault-tolerant contract scheduling. Last, we demonstrate how to apply the above techniques in robust optimization without predictions, and discuss how they can be applicable in the context of more general online problems.}, category = {other}, display = {yes}, cv = {yes} } @misc{BonatoKamali2021ImprovedBurningBound, author = {Anthony Bonato and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://math.ryerson.ca/~abonato/}, title = {An Improved Bound on the Burning Number of Graphs}, year = {2021}, note = {Preprint.}, arxiv = {https://arxiv.org/abs/2110.01087}, category = {other}, display = {yes}, cv = {yes} } @inproceedings{KamaliEtAl2020BurningTwoWorlds, author = {Shahin Kamali and Avery Miller and Kenny Zhang}, authororder = {alphabetical}, authorurl2 = {https://home.cs.umanitoba.ca/~amiller/}, title = {Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs}, booktitle = {Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)}, year = {2020}, pages = {113--124}, arxiv = {https://arxiv.org/abs/1909.00530}, venuekey = {SOFSEM}, edition = {41}, abstract = {Graph burning is a model for the spread of social influence in networks. The objective is to measure how quickly a fire (e.g., a piece of fake news) can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a selected vertex and burns it. Meanwhile, the old fires extend to their adjacent vertices and burn them. A burning schedule selects where the new fire breaks out in each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds, termed the burning number of the graph. The burning problem is known to be NP-hard even when the graph is a tree or a disjoint set of paths. For connected graphs, it has been conjectured that burning takes at most $\lceil \sqrt{n} \rceil$ rounds. In this paper, we approach the algorithmic study of graph burning from two directions. First, we consider graphs with minimum degree $\delta$. We present an algorithm that burns any graph of size $n$ in at most $\sqrt{24n/(\delta+1)}$ rounds. In particular, for dense graphs with $\delta \in \Theta(n)$, all vertices are burned in a constant number of rounds. More interestingly, even when \delta is a constant that is independent of the graph size, our algorithm answers the graph-burning conjecture in the affirmative by burning the graph in at most \lceil \sqrt{n} \rceil rounds. In the second part of the paper, we consider burning graphs with bounded path-length or tree-length. These include many graph families, including connected interval graphs (with path-length 1) and connected chordal graphs (with tree-length 1). We show that any graph with path-length $pl$ and diameter $d$ can be burned in $\lceil \sqrt{d-1} \rceil + pl$ rounds. Our algorithm ensures an approximation ratio of $1 + o(1)$ for graphs of bounded path-length. We introduce another algorithm that achieves an approximation ratio of $2 + o(1)$ for burning graphs of bounded tree-length. The approximation factor of our algorithms are improvements over the best existing approximation factor of 3 for burning general graphs.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{AngelopoulosEtAl2020UntrustedAdvice, author = {Spyros Angelopoulos and Christoph Dürr and Shendan Jin and Shahin Kamali and Marc P. Renault}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, authorurl2 = {https://perso.lip6.fr/Christoph.Durr/}, authorurl5 = {https://mrenault.sites.cs.wisc.edu/}, title = {Online Computation with Untrusted Advice}, booktitle = {Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS)}, year = {2020}, pages = {52:1--52:15}, arxiv = {https://arxiv.org/abs/1905.05655}, venuekey = {ITCS}, edition = {11}, abstract = {The advice model of online computation captures a setting in which the 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, 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.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliXu2020MulticorePaging, author = {Shahin Kamali and Helen Xu}, authororder = {alphabetical}, authorurl2 = {https://itshelenxu.github.io/}, title = {Multicore Paging Algorithms Cannot Be Competitive}, booktitle = {Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, year = {2020}, pages = {547--549}, note = {Brief announcement.}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2020-MiltiCore-Paging.pdf}, venuekey = {SPAA}, edition = {32}, abstract = {Every processor with multiple cores sharing a cache needs to implement a page-replacement algorithm. Lopez-Ortiz and Salinger [ITCS 2012] demonstrated that the competitive ratio of canonical paging algorithms such as Least-Recently-Used (LRU) and Furthest-In-Future (FIF) grows with the length of the input. In this paper, we answer an open question about the existence of competitive multicore paging algorithms in the negative. Specifically, we show that all lazy algorithms, which include all practical algorithms, cannot be competitive against the optimal offline algorithm.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{Kamali2020CompactBandwidth, author = {Shahin Kamali}, title = {Compact Representation of Graphs with Small Bandwidth and Treedepth}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2020}, pages = {233--242}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2020-DCC.pdf}, venuekey = {DCC}, abstract = {We consider the problem of compact representation of graphs with small \emph{bandwidth} as well as graphs with small \emph{treedepth}. These parameters capture structural properties of graphs that come in useful in certain applications. We present simple navigation oracles that support degree and adjacency queries in constant time and neighborhood query in constant time per neighbor. For graphs of bandwidth $k$, our oracle takes $(k+ \lceil \log 2k \rceil) n + o(kn)$ bits. By way of an enumeration technique, we show that $(k - 5\sqrt{k} - 4)n - O(k^{2})$ bits are required to encode a graph of bandwidth $k$ and size $n$. For graphs of treedepth $k$, our oracle takes $(k + \lceil \log k \rceil + 2)n + o(kn)$ bits. We present a lower bound that certifies our oracle is succinct for certain values of $k \in o(n)$.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BoseEtAl2020NonCrossingMatching, author = {Prosenjit Bose and Paz Carmi and Stephane Durocher and Shahin Kamali and Arezoo Sajadpour}, authororder = {alphabetical}, authorurl1 = {https://jitbose.ca/}, authorurl3 = {https://home.cs.umanitoba.ca/~durocher/}, title = {Non-crossing Matching of Online Points}, booktitle = {Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG)}, year = {2020}, pages = {233--239}, pdf = {https://vga.usask.ca/cccg2020/papers/Non-Crossing%20Matching%20of%20Online%20Points.pdf}, venuekey = {CCCG}, edition = {32}, abstract = {We consider the non-crossing matching problem in the online setting. In the monochromatic setting, a sequence of points in general position in the plane is revealed in an online manner, and the goal is to create a maximum matching of these points such that the line segments connecting pairs of matched points do not cross. The problem is online in the sense that the decisions to match each arriving point are irrevocable and should be taken without prior knowledge about forthcoming points. The bichromatic setting is defined similarly, except that half of the points are red and the rest are blue, and each matched pair consists of one red point and one blue point. Inspired by the online bipartite matching problem~\cite{KarpVV90}, where vertices on one side of a bipartite graph appear in an online manner, we assume red points are given a priory and blue points arrive in an online manner. In the offline setting, both the monochromatic and bichromatic problems can be solved optimally with all pairs matched. In the online setting of the monochromatic version, we show that a greedy family of algorithms matches $2\lceil (n-1)/3\rceil$ points, where $n$ is the number of input points. Meanwhile, we prove that no deterministic online algorithm can match more than $2\lceil (n-1)/3 \rceil$ points, i.e., the greedy strategy is optimal. In the bichromatic setting, we introduce an algorithm that matches $\log n - o(\log n)$ points for instances consisting of $n$ red and $n$ blue points, and show that no deterministic algorithm can do better. We also consider the problem under the advice setting, where an online algorithm receives some bits of advice about the input sequence, and provide lower and upper bounds for the amount of advice that is required and sufficient to match all points.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{SantosEtAl2020MiningPool, author = {Saulo dos Santos and Shahin Kamali and Ruppa K. Thulasiram}, authorurl1 = {https://sites.google.com/view/saulodossantos/home}, authorurl3 = {https://umanitoba.ca/science/directory/computer-science/ruppa-thulasiram}, title = {Candidate Set Formation Policy for Mining Pool}, booktitle = {Proceedings of the IEEE International Conference on Blockchain (IEEE Blockchain)}, year = {2020}, pages = {415--420}, url = {https://ieeexplore.ieee.org/document/9284733}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2020-Mining_Pools.pdf}, venuekey = {IEEEBlockchain}, abstract = {Cryptocurrencies like Bitcoin use the blockchain technology to record transactions in a distributed and secure way. Miners are distributed entities responsible for validating the transactions in the network and producing and verifying new blocks of confirmed transactions. In addition, they are responsible for keeping the protocol's integrity, protecting it against the double-spending problem. Miners are rewarded when they add new blocks to the blockchain. The reward consists of fresh coins created after adding a new block as well as the fees collected from the transactions inside the added block. The amount of new coins generated with new blocks is diminishing by the protocol over time. As such, the significance of collected fees is increasing for the miners.A recent trend in large mining pools is to allow miners to select transactions in the block they aim to mine. Allowing miners to select transactions increases transparency via discretization and also helps to avoid conflict of interest with the mining pool managers. Assuming that forming blocks is in miners' hands, miners should have a strategy to maintain transactions inside the block in a way to maximize their collected fees. The mining process is a random process that is "progress free". That is, a miner can update the transactions inside the block without any impact on its chance of succeeding in adding the block. Given that transactions with higher fees might arrive at any time in an online manner, it is profitable for a miner to "refresh" its block during the mining process. In this paper, we study the impact of refreshing blocks via an experimental analysis on real-world data from Bitcoin on a controlled environment that is carefully tuned to match the real world. Our results indicate that refreshing blocks is essential for increasing miners' collected fees, and overlooking it will have a significant impact on miners' revenues.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliNikbakht2020CuttingStock, author = {Shahin Kamali and Pooya Nikbakht}, authororder = {alphabetical}, authorurl2 = {https://www.pooya.website/home}, title = {Cutting Stock with Rotation: Packing Square Items into Square Bins}, booktitle = {Proceedings of the 14th International Conference on Combinatorial Optimization and Applications (COCOA)}, year = {2020}, pages = {530--544}, doi = {10.1007/978-3-030-64843-5_36}, url = {https://doi.org/10.1007/978-3-030-64843-5_36}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2020-COCOA2020_102_final.pdf}, venuekey = {COCOA}, edition = {14}, abstract = {In the square packing problem, the goal is to place a multi-set of square-items of various sizes into a minimum number of square-bins of equal size. Items are assumed to have various side-lengths of at most 1, and bins have uniform side-length 1. Despite being studied previously, the existing models for the problem do not allow rotation of items. In this paper, we consider the square packing problem in the presence of rotation. As expected, we can show that the problem is NP-hard. We study the problem under a resource augmented setting where an approximation algorithm can use bins of size $1 + \alpha$, for some $\alpha > 0$ , while the algorithm’s packing is compared to an optimal packing into bins of size 1. Under this setting, we show that the problem admits an asymptotic polynomial time scheme (APTAS) whose solutions can be encoded in a poly-logarithmic number of bits.}, category = {conference}, display = {yes}, cv = {yes} } @article{SantosEtAl2019PairwiseTransactions, author = {Saulo dos Santos and Muskan Vinayak and Ruppa K. Thulasiram and Parimala Thulasiraman and Shahin Kamali}, authorurl1 = {https://sites.google.com/view/saulodossantos/home}, authorurl3 = {https://umanitoba.ca/science/directory/computer-science/ruppa-thulasiram}, authorurl4 = {https://umanitoba.ca/science/directory/computer-science/parimala-thulasiraman}, title = {Validating Pairwise Transactions on Cryptocurrencies: A Novel Heuristic and Network Simulation}, journal = {Journal of Banking and Financial Technology}, year = {2019}, volume = {3}, number = {1}, pages = {71--81}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2019-Validating-Transactions.pdf}, venuekey = {JBFT}, abstract = {Bitcoin, along with other cryptocurrencies, has received a lot of attention in the recent past. The popularity of Bitcoin has increased the volume of transactions in an unprecedented way. The time to complete a simple pairwise transaction is determined by proof-of-work which requires a significant time compared to other components of the Bitcoin protocol. In this study, we propose a heuristic for validating pairwise transactions on cryptocurrencies. Our heuristic is based on simulating the participants sending and receiving transactions. We use SHA256 algorithm to enhance our solution for pairwise transactions, creating a local Blockchain of transactions, which has been previously used in the development of various Blockchain systems. We tested in-file and in-memory configurations in our simulations with two million transactions, which respectively took 290.39 and 5.34 s. The peak number for transactions-per-second was 6.88 when using the in-file setting and 374.25 for in-memory setting. From these experiments, we conclude that the number of transactions processed per second improves by increasing the block size as well as avoiding file access. We also implemented a parallel version of our algorithm in order to simulate the sharding technique and ultimately achieve further improvements in performance. In addition, we used Bitcoin simulator to analyze the impact of increasing the block size on the number of forks. Our simulations show that using a secondary relay network, such as FIBRE, to propagate the new blocks significantly reduces the number of forks and consequently the number of stale blocks.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{AbdollahiEtAl2019ImageCompression, author = {Arezoo Abdollahi and Neil Bruce and Shahin Kamali and Rezaul Karim}, authororder = {alphabetical}, authorurl2 = {https://socs.uoguelph.ca/~brucen/}, title = {Lossless Image Compression Using List Update Algorithms}, booktitle = {Proceedings of the 26th International Symposium on String Processing and Information Retrieval (SPIRE)}, year = {2019}, pages = {16--34}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2019-Image-Compression.pdf}, github = {https://github.com/ArezooAbdollahi/Lossless-image-compression-with-Hilbert-Curve-and-Move-to-Front}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2019-SPIRE.pdf}, venuekey = {SPIRE}, edition = {26}, abstract = {We consider lossless image compression using a technique similar to bZip2 for sequential data. Given an image represented with a matrix of pixel values, we consider different approaches for linearising the image into a sequence and then encoding the sequence using the Move-To-Front list update algorithm. In both linearisation and encoding stages, we exploit the locality present in the images to achieve encodings that are as compressed as possible. We consider a few approaches, and in particular Hilbert space-filling curves, for linearising the image. Using a natural model of locality for images introduced by Albers et al. [J. Comput. Syst. Sci. 2015], we establish the advantage of Hilbert space-filling curves over other linearisation techniques such as row-major or column-major curves for preserving the locality during the linearisation. We also use a result by Angelopoulos and Schweitzer [J. ACM 2013] to select Move-To-Front as the best list update algorithm for encoding the linearised sequence. In summary, our theoretical results show that a combination of Hilbert space-filling curves and Move-To-Front encoding has advantage over other approaches. We verify this with experiments on a dataset consisting of different categories of images.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BoyarEtAl2019BinCoveringAdvice, author = {Joan Boyar and Lene M. Favrholdt and Shahin Kamali and Kim S. Larsen}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl4 = {https://imada.sdu.dk/u/kslarsen/}, title = {Online Bin Covering with Advice}, booktitle = {Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS)}, year = {2019}, pages = {225--238}, arxiv = {https://arxiv.org/abs/1905.00066}, venuekey = {WADS}, edition = {16}, abstract = {The bin covering problem asks for covering a maximum number of bins with an online sequence of $n$ items of different sizes in the range $(0,1]$; a bin is said to be covered if it receives items of total size at least 1. We study this problem in the advice setting and provide tight bounds for the size of advice required to achieve optimal solutions. Moreover, we show that any algorithm with advice of size $o(\log \log n)$ has a competitive ratio of at most 0.5. In other words, advice of size $o(\log \log n)$ is useless for improving the competitive ratio of 0.5, attainable by an online algorithm without advice. This result highlights a difference between the bin covering and the bin packing problems in the advice model: for the bin packing problem, there are several algorithms with advice of constant size that outperform online algorithms without advice. Furthermore, we show that advice of size $O(\log \log n)$ is sufficient to achieve a competitive ratio that is arbitrarily close to $0.53\bar{3}$ and hence strictly better than the best ratio $0.5$ attainable by purely online algorithms. The technicalities involved in introducing and analyzing this algorithm are quite different from the existing results for the bin packing problem and confirm the different nature of these two problems. Finally, we show that a linear number of bits of advice is necessary to achieve any competitive ratio better than 15/16 for the online bin covering problem.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BonatoKamali2019GraphBurning, author = {Anthony Bonato and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://math.ryerson.ca/~abonato/}, title = {Approximation Algorithms for Graph Burning}, booktitle = {Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC)}, year = {2019}, pages = {74--92}, arxiv = {https://arxiv.org/abs/1811.04449}, venuekey = {TAMC}, edition = {15}, abstract = {Numerous approaches study the vulnerability of networks against social contagion. Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchronous, discrete rounds. In each round, a fire breaks out at a vertex, and the fire spreads to all vertices that are adjacent to a burning vertex. The selection of vertices where fires start defines a schedule that indicates the number of rounds required to burn all vertices. Given a graph, the objective of an algorithm is to find a schedule that minimizes the number of rounds to burn graph. Finding the optimal schedule is known to be NP-hard, and the problem remains NP-hard when the graph is a tree or a set of disjoint paths. The only known algorithm is an approximation algorithm for disjoint paths, which has an approximation ratio of 1.5. We present approximation algorithms for graph burning. For general graphs, we introduce an algorithm with an approximation ratio of 3. When the graph is a tree, we present another algorithm with approximation ratio 2. Moreover, we consider a setting where the graph is a forest of disjoint paths. In this setting, when the number of paths is constant, we provide an optimal algorithm which runs in polynomial time. When the number of paths is more than a constant, we provide two approximation schemes: first, under a regularity condition where paths have asymptotically equal lengths, we show the problem admits an approximation scheme which is fully polynomial. Second, for a general setting where the regularity condition does not necessarily hold, we provide another approximation scheme which runs in time polynomial in the size of the graph.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{SantosEtAl2019MinerStrategy, author = {Saulo dos Santos and Chukwuocha Chibundo and Shahin Kamali and Ruppa K. Thulasiram}, authorurl1 = {https://sites.google.com/view/saulodossantos/home}, authorurl4 = {https://umanitoba.ca/science/directory/computer-science/ruppa-thulasiram}, title = {An Efficient Miner Strategy for Selecting Cryptocurrency Transactions}, booktitle = {Proceedings of the IEEE International Conference on Blockchain (IEEE Blockchain)}, year = {2019}, pages = {116--123}, url = {https://ieeexplore.ieee.org/abstract/document/8946174}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2019-Miner-Strategy.pdf}, venuekey = {IEEEBlockchain}, abstract = {Cryptocurrencies like Bitcoin use the blockchain technology to record transactions in a distributed and secure way. Each block contains a cryptographic hash of the previous block in addition to a set of transactions that it records. The first step for a miner to add a new block to the blockchain is to select a set of pending transactions from a mempool. The total size of selected transactions should not exceed the fixed capacity of blocks. If a miner completes the computationally-hard task of finding the cryptographic hash of the formed block, the block can be added to the blockchain in which case the transactions in that block will become complete. Transaction might have a fee that is granted to the miner upon being complete. As such, when forming a new block, miners tend to select transactions that offer the best fees. Finding a set of transactions with maximum total fee that fit into a block translates to the classic knapsack problem, which is an NP-hard problem. Meanwhile, miners are in fierce competition for mining blocks and hence cannot dedicate too much computational power for selecting the best set of transactions. Most existing solutions to tackle this problem are based on sorting the set of pending transactions by the ratio between their fee and their size. While the sorting step is not a bottleneck in normal situations, transaction can grow explosively in case of a market turbulence like that of 2017. Meanwhile, the total number of transactions increases over time. As such, it is desirable to have an efficient strategy that does not rely on sorting transactions before forming a block. In this paper, we review some of the existing strategies for miners to select transactions from the mempool. We also introduce a robust solution called Size-Density Table (SDT) for selecting transactions that does not use sorting. We perform a theoretical and experimental analysis of our solutions to compare it with other strategies. Our results indicate that our algorithm runs faster than previous approaches while the quality of its solutions (the total fees collected in its blocks) is also slightly better than the best existing strategies.}, category = {conference}, display = {yes}, cv = {yes} } @misc{DurocherKamali2018CCCGProceedings, author = {Stephane Durocher and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://home.cs.umanitoba.ca/~durocher/}, title = {Proceedings of the 30th Canadian Conference on Computational Geometry, CCCG 2018}, year = {2018}, note = {Edited proceedings; editors: Stephane Durocher and Shahin Kamali.}, pdf = {https://cccg.ca/proceedings/2018/proceedings.pdf}, abstract = {This volume contains the proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018), which took place on August 8–10, 2018, at the University of Manitoba, in Winnipeg, Manitoba, Canada. These proceedings will be made available electronically after the conclusion of the conference on the CCCG website: http://www.cccg.ca/. We are grateful to the CCCG 2018 Program Committee and external reviewers, for their time and effort carefully reviewing all submissions. Each submission was reviewed by a minimum of three program committee members. The program committee accepted 46 papers out of 65 papers submitted. We thank the authors of all submitted papers and all conference attendees. We thank the invited speakers: Dr. Matthew (Matya) Katz (Paul Erdős Memorial Lecture), Dr. Marc van Kreveld (Ferran Hurtado Memorial Lecture), and Dr. Carola Wenk. In addition, we are grateful for the tremendous efforts of the CCCG 2018 Local Organizing Committee for their assistance; in particular, we would like to acknowledge Avery Miller and Victoria Harris. We acknowledge the generous financial support from our sponsors: the Pacific Institute for the Mathematical Sciences (PIMS), Elsevier, the Fields Institute for Research in Mathematical Sciences, and the University of Manitoba.}, category = {other}, display = {yes}, cv = {yes}, editor = {Stephane Durocher and Shahin Kamali} } @article{AngelopoulosEtAl2018SmallAdvice, author = {Spyros Angelopoulos and Christoph Dürr and Shahin Kamali and Marc P. Renault and Adi Ros{\'e}n}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, authorurl2 = {https://perso.lip6.fr/Christoph.Durr/}, authorurl4 = {https://mrenault.sites.cs.wisc.edu/}, title = {Online Bin Packing with Advice of Small Size}, journal = {Theory of Computing Systems}, year = {2018}, volume = {62}, number = {8}, pages = {2006--2034}, pdf = {https://www.irif.fr/~adiro/publ/ADKRR.pdf}, venuekey = {ToCS}, abstract = {In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds of online algorithms for this problem. On the positive side, we first provide a relatively simple algorithm that achieves a competitive ratio arbitrarily close to 1.5, using constant-size advice. Our result implies that 16 bits of advice suffice to obtain a competitive ratio better than any online algorithm without advice, thus improving the previously known bound of O(log(n)) bits required to attain this performance. In addition, we introduce a more complex algorithm that still requires only constant-size advice, and has a competitive ratio arbitrarily close to 1.47012. This is the currently best performance of any online bin packing algorithm with sublinear advice. On the negative side, we extend a construction due to Boyar et al. (Algorithmica 74(1), 507-527 2016) so as to show that no online algorithm with sub-linear advice can be 7/6-competitive, improving on the lower bound of 9/8 from Boyar et al.}, category = {journal}, display = {yes}, cv = {yes} } @article{Kamali2018CliqueWidth, author = {Shahin Kamali}, title = {Compact Representation of Graphs of Small Clique-Width}, journal = {Algorithmica}, year = {2018}, volume = {80}, number = {7}, pages = {2106--2131}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2018-clique-width.pdf}, venuekey = {Algorithmica}, abstract = {The notion of clique-width for graphs is a relatively new topic that has received attention in the past decade. A graph has clique-width $k$ if it can be represented as an algebraic expression on $k$ labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs with bounded clique-width. Interestingly also, many graph families that arise in practice have bounded clique-width. In this paper, we consider the problem of preprocessing a graph of size $n$ and clique-width $k$ to build space-efficient encodings (oracles) to perform various queries efficiently. First, by way of an enumeration argument, which is of interest in its own right, we show the space requirement of such representation is $\Omega(kn)$. Then we present a navigation oracle which answers adjacency and neighborhood queries in constant time using $O(n)$ space (i.e., $O(n)$ bits), and reports the degree of each given vertex in $O(k)$ time, using $O(kn + n \log \log n)$ bits.}, category = {journal}, display = {yes}, cv = {yes} } @article{BoyarEtAl2017ListUpdateAdvice, author = {Joan Boyar and Shahin Kamali and Kim S. Larsen and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl3 = {https://imada.sdu.dk/u/kslarsen/}, authorurl4 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {On the List Update Problem with Advice}, journal = {Information and Computation}, year = {2017}, volume = {253}, pages = {411--423}, arxiv = {https://arxiv.org/abs/1311.7357}, venuekey = {InfComput}, abstract = {We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice are sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 5/3. In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms, TIMESTAMP and two members of the MTF2 family of algorithms. We also show that MTF2 algorithms are 2.5-competitive.}, category = {journal}, display = {yes}, cv = {yes} } @article{HarutyunyanKamali2017BroadcastTrees, author = {Hovhannes A. Harutyunyan and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://users.encs.concordia.ca/~haruty/}, title = {Efficient Broadcast Trees for Weighted Vertices}, journal = {Discrete Applied Mathematics}, year = {2017}, volume = {216}, pages = {598--608}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2017-DAM.pdf}, venuekey = {DAM}, abstract = {In this paper, we consider a weighted-vertex model for information dissemination in communication networks. Each node of the network (e.g., a processing machine) is assigned a weight, which represents the delay of the node after receiving data and before sending it to its neighbors. We are interested in the broadcasting problem in which the goal is to disseminate information from one node to all other nodes as quickly as possible. We introduce a simple algorithm for optimal broadcasting from a given node in weighted-vertex trees. We also study the problem of constructing efficient broadcast trees that minimize the required time for broadcasting. We investigate two variants of this problem. First, we show that, given a set of vertices with specified weights, one can construct a tree that connects all vertices and enables broadcasting from any vertex in the optimal time of $\Theta(\log n)$. Second, given a set of weighted vertices among which one vertex is specified as the originator, we introduce a polynomial algorithm that connects vertices with a tree in which broadcasting from the originator completes in minimum time.}, category = {journal}, display = {yes}, cv = {yes} } @article{GhaznaviEtAl2017ServiceChaining, author = {Milad Ghaznavi and Nashid Shahriar and Shahin Kamali and Reaz Ahmed and Raouf Boutaba}, authorurl2 = {https://www.uregina.ca/science/computer-science/directory/shahriar-nashid.html}, authorurl5 = {https://rboutaba.cs.uwaterloo.ca/}, title = {Distributed Service Function Chaining}, journal = {IEEE Journal on Selected Areas in Communications}, year = {2017}, volume = {35}, number = {11}, pages = {2479--2489}, pdf = {https://rboutaba.cs.uwaterloo.ca/Papers/Journals/2017/GhaznaviJSAC17.pdf}, venuekey = {IEEEJSAC}, abstract = {A service-function chain, or simply a chain, is an ordered sequence of service functions, e.g., firewalls and load balancers, composing a service. A chain deployment involves selecting and instantiating a number of virtual network functions (VNFs), i.e., softwarized service functions, placing VNF instances, and routing traffic through them. In the current optimization-models of a chain deployment, the instances of the same function are assumed to be identical, while typical service providers offer VNFs with heterogeneous throughput and resource configurations. The VNF instances of the same function are installed in a single physical machine, which limits a chain to the throughput of a few instances that can be installed in one physical machine. Furthermore, the selection, placement, and routing problems are solved in isolation. We present distributed service function chaining that coordinates these operations, places VNF-instances of the same function distributedly, and selects appropriate instances from typical VNF offerings. Such a deployment uses network resources more efficiently and decouples a chain's throughput from that of physical machines. We formulate this deployment as a mixed integer programming (MIP) model, prove its NP-Hardness, and develop a local search heuristic called Kariz. Extensive experiments demonstrate that Kariz achieves a competitive acceptance-ratio of 76%-100% with an extra cost of less than 24% compared with the MIP model.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{MateEtAl2017ServerConsolidation, author = {Joseph Mate and Khuzaima Daudjee and Shahin Kamali}, authorurl2 = {https://cs.uwaterloo.ca/~kdaudjee/}, title = {Robust Multi-tenant Server Consolidation in the Cloud for Data Analytics Workloads}, booktitle = {Proceedings of the 37th IEEE International Conference on Distributed Computing Systems (ICDCS)}, year = {2017}, pages = {2111--2118}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2017-ICDCS.pdf}, venuekey = {ICDCS}, edition = {37}, abstract = {Server consolidation is the hosting of multiple tenants on a server machine. Given a sequence of data analytics tenant loads defined by the amount of resources that the tenants require and a service-level agreement (SLA) between the customer and the cloud service provider, significant cost savings can be achieved by consolidating multiple tenants. Since server machines can fail causing their tenants to become unavailable, service providers can place replicas of each tenant on multiple servers and reserve capacity to ensure that tenant failover will not result in overload on any remaining server. We present the CUBEFIT algorithm for server consolidation that reduces costs by utilizing fewer servers than existing approaches for data analytics workloads. Unlike existing consolidation algorithms, CUBEFIT can tolerate multiple server failures while ensuring that no server becomes overloaded. Through theoretical analysis and experimental evaluation, we show that CUBEFIT is superior to existing algorithms and produces near-optimal tenant allocation when the number of tenants is large. Through evaluation and deployment on a cluster of 73 machines as well as through simulation studies, we experimentally demonstrate the efficacy of CUBEFIT.}, category = {conference}, display = {yes}, cv = {yes} } @article{GuptaEtAl2016KServerAdvice, author = {Sushmita Gupta and Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://sites.google.com/view/sushmitagupta/home}, authorurl3 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {On the Advice Complexity of the $k$-server Problem Under Sparse Metrics}, journal = {Theory of Computing Systems}, year = {2016}, volume = {59}, number = {3}, pages = {476--499}, arxiv = {https://arxiv.org/abs/1305.2108}, venuekey = {ToCS}, abstract = {We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce $\Theta(1)$-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size $N$ and treewidth $\alpha$, there is an online algorithm which receives $O{n (\log \alpha + \log \log N)}$ bits of advice and optimally serves a sequence of length $n$. We also show that if a graph admits a system of $\mu$ collective tree $(q,r)$-spanners, then there is a $(q+r)$-competitive algorithm which receives $O(n (\log \mu + \log \log N))$ bits of advice. Among other results, this gives a $3$-competitive algorithm for planar graphs, provided with $O(n \log \log N)$ bits of advice. On the other side, we show that advice of size $\Omega(n)$ is required to obtain a $1$-competitive algorithm for sequences of size $n$ even for the 2-server problem on a path metric of size $N \geq 5$. Through another lower bound argument, we show that at least $\frac{n}{2}(\log \alpha- 1.22)$ bits of advice is required to obtain an optimal solution for metric spaces of treewidth $\alpha$, where $4 \leq \alpha < 2k$.}, category = {journal}, display = {yes}, cv = {yes} } @article{BoyarEtAl2016BinPackingAdvice, author = {Joan Boyar and Shahin Kamali and Kim S. Larsen and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl3 = {https://imada.sdu.dk/u/kslarsen/}, authorurl4 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {Online Bin Packing with Advice}, journal = {Algorithmica}, year = {2016}, volume = {74}, number = {1}, pages = {507--527}, arxiv = {https://arxiv.org/abs/1212.4016}, venuekey = {Algorithmica}, 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 + epsilon. 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.}, category = {journal}, display = {yes}, cv = {yes} } @incollection{Kamali2016OnlineListUpdate, author = {Shahin Kamali}, title = {Online List Update}, booktitle = {Encyclopedia of Algorithms}, publisher = {Springer}, year = {2016}, pages = {1448--1451}, url = {https://link.springer.com/rwe/10.1007/978-1-4939-2864-4_266}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2016-Encyc-List-Update.pdf}, abstract = {This article reviews the list update problem, classic results on deterministic and randomized algorithms, and the impact of the locality of reference on the performance of online list update algorithms. The article concludes with a quick overview of the applications of the list update problem and open questions.}, category = {bookchapter}, display = {yes}, cv = {yes} } @inproceedings{Kamali2016CliqueWidth, author = {Shahin Kamali}, title = {Compact Navigation Oracles for Graphs with Bounded Clique-Width}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2016}, pages = {566--576}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2016-DCC.pdf}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2016-DCC.pdf}, venuekey = {DCC}, abstract = {The notion of clique-width for graphs is a relatively new topic that has received attention in the past decade. A graph has bounded clique-width if it can be represented as an algebraic expression on a constant number of labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs with bounded clique-width. Interestingly also, many graph families that arise in practice have bounded clique-width. In this paper, we present compact navigation oracles for graphs with bounded clique-width. Our oracles answer adjacency and neighborhood queries in constant time using $O(n)$ space (i.e., $O(n)$ bits) for a graph of size $n$, and report the degree of each given vertex, also in constant time, using $O(n \lg \lg n)$ bits.}, category = {conference}, display = {yes}, cv = {yes} } @article{DorrigivEtAl2015MSTNeighborhoods, author = {Reza Dorrigiv and Robert Fraser and Meng He and Shahin Kamali and Akitoshi Kawamura and Alejandro López-Ortiz and Diego Seco}, authororder = {alphabetical}, authorurl3 = {https://web.cs.dal.ca/~mhe/}, authorurl6 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, authorurl7 = {https://lbd.udc.es/ShowResearcherInformation.do?lang=en_US}, title = {On Minimum- and Maximum-weight Minimum Spanning Trees with Neighborhoods}, journal = {Theory of Computing Systems}, year = {2015}, volume = {56}, number = {1}, pages = {220--250}, pdf = {https://web.cs.dal.ca/~mhe/publications/wowa12_spanningtree.pdf}, venuekey = {ToCS}, abstract = {We study optimization problems for the Euclidean minimum spanning tree (MST) on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the minimum spanning tree with neighborhoods (MSTN) problem, and the maximum weight version (max-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the max-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{KamaliLopezOrtiz2015NearOptimalBinPacking, author = {Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl2 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {All-Around Near-Optimal Solutions for the Online Bin Packing Problem}, booktitle = {Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC)}, year = {2015}, pages = {727--739}, arxiv = {https://arxiv.org/abs/1404.4526}, venuekey = {ISAAC}, edition = {26}, abstract = {In this paper we present algorithms with optimal average-case and close-to-best known worst-case performance for the classic online bin packing problem. It has long been observed that known bin packing algorithms with optimal average-case performance are not optimal in the worst-case. In particular First Fit and Best Fit have optimal asymptotic average-case ratio of 1 but a worstcase competitive ratio of 1.7. The competitive ratio can be improved to 1.691 using the Harmonic algorithm. Further variations of this algorithm can push down the competitive ratio to 1.588. However, these algorithms have poor performance on average; in particular, Harmonic algorithm has average-case ratio of 1.27. In this paper, first we introduce a simple algorithm which we term Harmonic Match. This algorithm performs as well as Best Fit on average, i.e., it has an average-case ratio of 1. Moreover, the competitive ratio of the algorithm is as good as Harmonic, i.e., it converges to 1.691 which is an improvement over Best Fit and First Fit. We also introduce a different algorithm, termed as Refined Harmonic Match, which achieves an improved competitive ratio of 1.636 while maintaining the good average-case performance of Harmonic Match and Best Fit. Our experimental evaluations show that our proposed algorithms have comparable average-case performance with Best Fit and First Fit, and this holds also for sequences that follow distributions other than the uniform distribution.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliEtAl2015TrianglePacking, author = {Shahin Kamali and Alejandro López-Ortiz and Zahed Rahmati}, authororder = {alphabetical}, authorurl2 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {Online Packing of Equilateral Triangles}, booktitle = {Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG)}, year = {2015}, pages = {6}, pdf = {https://research.cs.queensu.ca/cccg2015/CCCG15-papers/36.pdf}, venuekey = {CCCG}, edition = {27}, abstract = {We investigate the online triangle packing problem in which a sequence of equilateral triangles with different sizes appear in an online, sequential manner. The goal is to place these triangles into a minimum number of squares of unit size. We provide upper and lower bounds for the competitive ratio of online algorithms. In particular, we introduce an algorithm that achieves a competitive ratio of at most 2.474. On the other hand, we show that no online algorithm can have a competitive ratio better than 1.509.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{PetroniEtAl2015HDRF, author = {Fabio Petroni and Leonardo Querzoni and Khuzaima Daudjee and Shahin Kamali and Giorgio Iacoboni}, authorurl1 = {https://www.fabiopetroni.com/}, authorurl2 = {https://sites.google.com/diag.uniroma1.it/querzoni/home-page}, authorurl3 = {https://cs.uwaterloo.ca/~kdaudjee/}, title = {HDRF: Stream-based Partitioning for Power-law Graphs}, booktitle = {Proceedings of the 24th ACM International Conference on Information and Knowledge Management (CIKM)}, year = {2015}, pages = {243--252}, pdf = {https://www.fabiopetroni.com/Download/petroni2015HDRF.pdf}, venuekey = {CIKM}, edition = {24}, abstract = {Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{AngelopoulosEtAl2015SmallAdvice, author = {Spyros Angelopoulos and Christoph Dürr and Shahin Kamali and Marc Renault and Adi Rosén}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, authorurl2 = {https://perso.lip6.fr/Christoph.Durr/}, authorurl4 = {https://mrenault.sites.cs.wisc.edu/}, authorurl5 = {https://www.irif.fr/~adiro/}, title = {Online Bin Packing with Advice of Small Size}, booktitle = {Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS)}, year = {2015}, pages = {40--53}, pdf = {https://www.irif.fr/~adiro/publ/ADKRR.pdf}, venuekey = {WADS}, edition = {14}, abstract = {In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds of online algorithms for this problem. On the positive side, we first provide a relatively simple algorithm that achieves a competitive ratio arbitrarily close to 1.5, using constant-size advice. Our result implies that 16 bits of advice suffice to obtain a competitive ratio better than any online algorithm without advice, thus improving the previously known bound of O(log(n)) bits required to attain this performance. In addition, we introduce a more complex algorithm that still requires only constant-size advice, and has a competitive ratio arbitrarily close to 1.47012. This is the currently best performance of any online bin packing algorithm with sublinear advice. On the negative side, we extend a construction due to Boyar et al. (Algorithmica 74(1), 507-527 2016) so as to show that no online algorithm with sub-linear advice can be 7/6-competitive, improving on the lower bound of 9/8 from Boyar et al.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliLopezOrtiz2015RentingServers, author = {Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl2 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {Efficient Online Strategies for Renting Servers in the Cloud}, booktitle = {Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)}, year = {2015}, pages = {277--288}, arxiv = {https://arxiv.org/abs/1408.4156}, venuekey = {SOFSEM}, edition = {41}, abstract = {In Cloud systems, we often deal with jobs that arrive and depart in an online manner. Upon its arrival, a job should be assigned to a server. Each job has a size which defines the amount of resources that it needs. Servers have uniform capacity and, at all times, the total size of jobs assigned to a server should not exceed the capacity. This setting is closely related to the classic bin packing problem. The difference is that, in bin packing, the objective is to minimize the total number of used servers. In the Cloud, however, the charge for each server is proportional to the length of the time interval it is rented for, and the goal is to minimize the cost involved in renting all used servers. Recently, certain bin packing strategies were considered for renting servers in the Cloud [Li et al. SPAA'14]. There, it is proved that all Any-Fit bin packing strategy has a competitive ratio of at least \mu, where \mu is the max/min interval length ratio of jobs. It is also shown that First Fit has a competitive ratio of 2\mu + 13 while Best Fit is not competitive at all. We observe that the lower bound of \mu extends to all online algorithms. We also prove that, surprisingly, Next Fit algorithm has competitive ratio of at most 2\mu + 1. We also show that a variant of Next Fit achieves a competitive ratio of K max{1,\mu/(K-1)} + 1, where K is a parameter of the algorithm. In particular, if the value of \mu is known, the algorithm has a competitive ratio of \mu + 2; this improves upon the existing upper bound of \mu + 8. Finally, we introduce a simple algorithm called Move To Front (MTF) which has a competitive ratio of at most 6\mu + 7 and also promising average-case performance. We experimentally study the average-case performance of different algorithms and observe that the typical behaviour of MTF is distinctively better than other algorithms.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{Kamali2015ResourceProvisioning, author = {Shahin Kamali}, title = {Efficient Bin Packing Algorithms for Resource Provisioning in the Cloud}, booktitle = {Proceedings of the International Conference on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)}, year = {2015}, pages = {84--98}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2015-AlgoCloud.pdf}, venuekey = {ALGOCLOUD}, abstract = {We consider the Infrastructure as a Service IaaS model for cloud service providers. This model can be abstracted as a form of online bin packing problem where bins represent physical machines and items represent virtual machines with dynamic load. The input to the problem is a sequence of operations each involving an insertion, deletion or updating the size of an item. The goal is to use live migration to achieve packings with a small number of active bins. Reducing the number of bins is critical for green computing and saving on energy costs. We introduce an algorithm, named HarmonicMix, that supports all operations and moves at most ten items per operation. The algorithm achieves a competitive ratio of 4/3, implying that the number of active bins at any stage of the algorithm is at most 4/3 times more than any offline algorithm that uses infinite migration. This is an improvement over a recent result of Song et al. (IEEE Trans. Computers, 2014) who introduced an algorithm, named VISBP, with a competitive ratio of 3/2. Our experiments indicate a considerable advantage for HarmonicMix over VISBP with respect to average-case performance. HarmonicMix is simple and runs as fast as classic bin packing algorithms such as Best Fit and First Fit; this makes the algorithm suitable for practical purposes.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{NicoaraEtAl2015Hermes, author = {Daniel Nicoara and Shahin Kamali and Khuzaima Daudjee and Lei Chen}, authorurl3 = {https://cs.uwaterloo.ca/~kdaudjee/}, title = {Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases}, booktitle = {Proceedings of the 18th International Conference on Extending Database Technology (EDBT)}, year = {2015}, pages = {25--36}, pdf = {https://uwaterloo.ca/computer-science/sites/default/files/uploads/documents/cs-2015-1.pdf}, venuekey = {EDBT}, edition = {18}, abstract = {Social networks are large graphs that require multiple graph database servers to store and manage them. Each database server hosts a graph partition with the objectives of bal-ancing server loads, reducing remote traversals (edge-cuts), and adapting the partitioning to changes in the structure of the graph in the face of changing workloads. To achieve these objectives, a dynamic repartitioning algorithm is re-quired to modify an existing partitioning to maintain good quality partitions while not imposing a significant overhead to the system. In this paper, we introduce a lightweight repartitioner, which dynamically modifies a partitioning using a small amount of resources. In contrast to the existing repartitioning algorithms, our lightweight repartitioner is efficient, making it suitable for use in a real system. We integrated our lightweight repartitioner into Hermes, which we designed as an extension of the open source Neo4j graph database system, to support workloads over partitioned graph data distributed over multiple servers. Using real-world social network data, we show that Hermes leverages the lightweight repartitioner to maintain high quality partitions and provides a 2 to 3 times performance improvement over the de-facto standard random hash-based partitioning.}, category = {conference}, display = {yes}, cv = {yes} } @phdthesis{Kamali2014PhD, author = {Shahin Kamali}, title = {Alternative Approaches for Analysis of Bin Packing and List Update Problems}, school = {David R. Cheriton School of Computer Science, University of Waterloo}, year = {2014}, url = {https://uwspace.uwaterloo.ca/items/03398c28-26db-4da4-869a-ea2a9fb97d6c}, abstract = {In this thesis, we introduce and evaluate new algorithms and models for the analysis of online bin packing and list update problems. These are two classic online problems that have been extensively studied in the literature and have many applications in the real world. The main goal of this thesis is to develop new approaches for studying online problems, and in particular bin packing and list update, to guide the development of practical algorithms performing quite well on real-world inputs. In doing so, we introduce new algorithms with good performance (not only under the competitive analysis) as well as new models which are more realistic for certain applications of the studied problems. In doing so, we introduce online bin packing algorithms which outperform Best Fit and First Fit in terms of competitive ratio while maintaining their good average-case performance. An alternative for analysis of online problems is the advice model, which has received significant attention in the past few years. Under the advice model, an online algorithm receives a number of bits of advice about the unrevealed parts of the sequence. Generally, there is a trade-off between the size of the advice and the performance of online algorithms. The advice model generalizes the existing frameworks in which an online algorithm has partial knowledge about the input sequence, e.g., the access graph model for the paging problem. We study list update and bin packing problems under the advice model and answer several relevant questions about the advice complexity of these problems. Online problems are usually studied under specific settings which are not necessarily valid for all applications of the problem. As an example, online bin packing algorithms are widely used for server consolidation to minimize the number of active servers in a data center. In some applications, e.g., tenant placement in the Cloud, often a `fault-tolerant' solution for server consolidation is required. In this setting, the problem becomes different, and the classic algorithms can no longer be used. We study a fault-tolerant model for the bin packing problem and analyze algorithms which fit this particular application of the problem. Similarly, the list update problem was initially proposed to maintain self-adjusting linked lists. However, presently, the main application of the problem is in the data compression realm. We show that the standard cost model is not suitable for compression purposes and study a compression cost model for the list update problem. Our analysis justifies the advantage of the compression schemes, which are based on the Move-To-Front algorithm and might lead to improved compression algorithms.}, category = {thesis}, display = {yes}, cv = {yes} } @article{FarzanKamali2014TreewidthOracles, author = {Arash Farzan and Shahin Kamali}, authororder = {alphabetical}, title = {Compact Navigation and Distance Oracles for Graphs with Small Treewidth}, journal = {Algorithmica}, year = {2014}, volume = {69}, number = {1}, pages = {92--116}, pdf = {https://cs.uwaterloo.ca/research/tr/2011/CS-2011-15.pdf}, venuekey = {Algorithmica}, abstract = {Given an unlabeled, unweighted, and undirected graph with $n$ vertices and small (but not necessarily constant) treewidth $k$, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is $\Omega(\log n)$ bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with $n$ vertices and treewidth $k$. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in $O(k^3\log^3 k)$ time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where $k$ is constant), the distances are reported in constant worst-case time.}, category = {journal}, display = {yes}, cv = {yes} } @inproceedings{KamaliLopezOrtiz2014SquarePacking, author = {Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl2 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {Almost Online Square Packing}, booktitle = {Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG)}, year = {2014}, pages = {1--7}, pdf = {https://www.cccg.ca/proceedings/2014/papers/paper24.pdf}, venuekey = {CCCG}, edition = {26}, abstract = {In the square packing problem, the goal is to pack squares of different sizes into the smallest number of bins (squares) of uniform size. We introduce an almostonline square packing algorithm which places squares in an online, sequential manner. In doing so, it receives advice of logarithmic size from an offline oracle which runs in linear time. Our algorithm achieve a competitive ratio of at most 1.84 which is significantly better than the best existing online algorithm which has a competitive ratio of 2.1187. In introducing the algorithm, we have been inspired by the advice model for the analyses of online problems. Our algorithm can also be regarded as a streaming algorithm which packs an input sequence of squares in two passes using a space of logarithmic size.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{DaudjeeEtAl2014FaultTolerantServer, author = {Khuzaima Daudjee and Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://cs.uwaterloo.ca/~kdaudjee/}, authorurl3 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {On the Online Fault-tolerant Server Consolidation Problem}, booktitle = {Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, year = {2014}, pages = {12--21}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2014-SPAA.pdf}, venuekey = {SPAA}, edition = {26}, abstract = {In the server consolidation problem, the goal is to minimize the number of servers needed to host a set of clients. The clients appear in an online manner and each of them has a certain load. The servers have uniform capacity and the total load of clients assigned to a server must not exceed this capacity. Additionally, to have a fault-tolerant solution, the load of each client should be distributed between at least two different servers so that failure of one server avoids service interruption by migrating the load to the other servers hosting the respective second loads. In a simple setting, upon receiving a client, an online algorithm needs to select two servers and assign half of the load of the client to each server. We analyze the problem in the framework of competitive analysis. First, we provide upper and lower bounds for the competitive ratio of two well known heuristics which are introduced in the context of tenant placement in the cloud. In particular, we show their competitive ratios are no better than 2. We then present a new algorithm called Horizontal Harmonic and show that it has an improved competitive ratio which converges to 1.59. The simplicity of this algorithm makes it a good choice for use by cloud service providers. Finally, we prove a general lower bound that shows any online algorithm for the online fault-tolerant server consolidation problem has a competitive ratio of at least 1.42.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliLopezOrtiz2014BetterCompression, author = {Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl2 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {Better Compression Through Better List Update Algorithms}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2014}, pages = {372--381}, url = {https://ieeexplore.ieee.org/document/6824445}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2014-DCC.pdf}, venuekey = {DCC}, abstract = {List update is a key step during the Burrows-Wheeler transform (BWT) compression. Previous work has shown that careful study of the list update step leads to better BWT compression. Surprisingly, the theoretical study of list update algorithms for compression has lagged behind its use in real practice. To be more precise, the standard model by Sleator and Tarjan for list update considers a 'linear cost-of-access' model while compression incurs a logarithmic cost of access, i.e. accessing item i in the list has cost Theta(i) in the standard model but Theta(log i) in compression applications. These models have been shown, in general, not to be equivalent. This paper has two contributions: (1) We give the first theoretical proof that the commonly used Move-To-Front (MTF) has good performance under the compression logarithmic cost-of-access model. This has long been known in practice but a formal proof under the logarithmic cost compression model was missing until now, (2) we further refine the online compression model to reflect its use under compression by applying the recently developed 'online algorithms with advice' model. This advice model was initially a purely theoretical construct in which the online algorithm has access to an all powerful oracle during the computation. We show that surprisingly, this seemingly unrealistic model can be used to produce better multi-pass compression algorithms. More precisely, we introduce an 'almost-online' list update algorithm, which we term BIB which results in a compression scheme which is superior to schemes using standard online algorithms, in particular those of MTF and TIMESTAMP. For example, for the files in the standard Canterbury Corpus, the compression ratio of the scheme that uses BIB is 33.66 on average, while the compression ratios for the schemes that use MTF and TIMESTAMP are respectively 34.25 and 36.30.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BoyarEtAl2014BinPackingAdvice, author = {Joan Boyar and Shahin Kamali and Kim S. Larsen and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl3 = {https://imada.sdu.dk/u/kslarsen/}, authorurl4 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {Online Bin Packing with Advice}, booktitle = {Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS)}, year = {2014}, pages = {174--186}, arxiv = {https://arxiv.org/abs/1212.4016}, venuekey = {STACS}, edition = {31}, 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 + epsilon. 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.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{BoyarEtAl2014ListUpdateAdvice, author = {Joan Boyar and Shahin Kamali and Kim S. Larsen and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl3 = {https://imada.sdu.dk/u/kslarsen/}, authorurl4 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {On the List Update Problem with Advice}, booktitle = {Proceedings of the 8th International Conference on Language, Automata Theory and Applications (LATA)}, year = {2014}, pages = {210--221}, arxiv = {https://arxiv.org/abs/1311.7357}, venuekey = {LATA}, edition = {8}, abstract = {We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice are sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 5/3. In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms, TIMESTAMP and two members of the MTF2 family of algorithms. We also show that MTF2 algorithms are 2.5-competitive.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{GuptaEtAl2013KServerAdvice, author = {Sushmita Gupta and Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl1 = {https://sites.google.com/view/sushmitagupta/home}, authorurl3 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {On Advice Complexity of the $k$-server Problem under Sparse Metrics}, booktitle = {Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO)}, year = {2013}, pages = {55--67}, arxiv = {https://arxiv.org/abs/1305.2108}, venuekey = {SIROCCO}, edition = {20}, abstract = {We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce $\Theta(1)$-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size $N$ and treewidth $\alpha$, there is an online algorithm which receives $O(n (\log \alpha + \log \log N))$ bits of advice and optimally serves a sequence of length $n$. We also show that if a graph admits a system of $\mu$ collective tree $(q,r)$-spanners, then there is a $(q+r)$-competitive algorithm which receives $O(n (\log \mu + \log \log N))$ bits of advice. Among other results, this gives a $3$-competitive algorithm for planar graphs, provided with $O(n \log \log N)$ bits of advice. On the other side, we show that advice of size $\Omega(n)$ is required to obtain a $1$-competitive algorithm for sequences of size $n$ even for the 2-server problem on a path metric of size $N \geq 5$. Through another lower bound argument, we show that at least $\frac{n}{2}(\log \alpha- 1.22)$ bits of advice is required to obtain an optimal solution for metric spaces of treewidth $\alpha$, where $4 \leq \alpha < 2k$.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{LeiEtAl2013VideoOnDemand, author = {Bairong Lei and Ivan Surya and Shahin Kamali and Khuzaima Daudjee}, authorurl4 = {https://cs.uwaterloo.ca/~kdaudjee/}, title = {Data Partitioning for Video-on-Demand Services}, booktitle = {Proceedings of the 12th IEEE International Symposium on Network Computing and Applications (NCA)}, year = {2013}, pages = {49--54}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2013-NCA.pdf}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2013-NCA.pdf}, venuekey = {NCA}, edition = {12}, abstract = {Streaming video over the Internet has become a popular service that is projected to outstrip demand over most other real-time streaming services. Thus, it is essential to provide scalable server storage and services without which video-on-demand services will not be able to provide good performance in the face of increasing demand. In this paper, we study algorithms, and propose one, for simple partitioning video-on-demand storage to distribute content and workload among servers within a master-slave architecture. We show the effectiveness of the partitioning strategies by conducting experiments on an actual system to quantify trade-offs between the algorithms.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{ClaudeEtAl2013Broadcasting, author = {Francisco Claude and Reza Dorrigiv and Shahin Kamali and Alejandro López-Ortiz and Pawel Pralat and Jazmin Romero and Alejandro Salinger and Diego Seco}, authororder = {alphabetical}, authorurl4 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, authorurl5 = {https://math.ryerson.ca/~pralat/}, authorurl7 = {https://cs.uwaterloo.ca/~ajsaling/}, authorurl8 = {https://lbd.udc.es/ShowResearcherInformation.do?lang=en_US}, title = {Broadcasting in Conflict-Aware Multi-channel Networks}, booktitle = {Proceedings of the 7th International Conference and Workshop on Algorithms and Computation (WALCOM)}, year = {2013}, pages = {158--169}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2013-WALCOM.pdf}, venuekey = {WALCOM}, edition = {7}, abstract = {The broadcasting problem asks for the fastest way of transmitting a message to all nodes of a communication network. We consider the problem in conflict-aware multi-channel networks. These networks can be modeled as undirected graphs in which each edge is labeled with a set of available channels to transmit data between its endpoints. Each node can send and receive data through any channel on its incident edges, with the restriction that it cannot successfully receive through a channel when multiple neighbors send data via that channel simultaneously. We present efficient algorithms as well as hardness results for the broadcasting problem on various network topologies. We propose polynomial time algorithms for optimal broadcasting in grids, and also for trees when there is only one channel on each edge. Nevertheless, we show that the problem is NP-hard for trees in general, as well as for complete graphs. In addition, we consider balanced complete graphs and propose a policy for assigning channels to these graphs. This policy, together with its embedded broadcasting schemes, result in fault-tolerant networks which have optimal broadcasting time.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliEtAl2013ListUpdateAlternative, author = {Shahin Kamali and Susana Ladra and Alejandro López-Ortiz and Diego Seco}, authororder = {alphabetical}, authorurl2 = {https://portalinvestigacion.udc.gal/investigadores/213604/detalle?lang=en}, authorurl3 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, authorurl4 = {https://lbd.udc.es/ShowResearcherInformation.do?lang=en_US}, title = {Context-based Algorithms for the List-update Problem under Alternative Cost Models}, booktitle = {Proceedings of the Data Compression Conference (DCC)}, year = {2013}, pages = {361--370}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2013-DCC.pdf}, venuekey = {DCC}, abstract = {The List-Update Problem is a well-studied online problem with direct applications in data compression. Although the model proposed by Sleator & Tarjan has become the standard in the field for the problem, its applicability in some domains, and in particular for compression purposes, has been questioned. In this paper, we focus on two alternative models for the problem that arguably have more practical significance than the standard model. We provide new algorithms for these models, and show that these algorithms outperform all classical algorithms under the discussed models. This is done via an empirical study of the performance of these algorithms on the reference data set for the list-update problem. The presented algorithms make use of context-based strategies for compression, which have not been considered before in the context of the list-update problem and lead to improved compression algorithms. In addition, we study the adaptability of these algorithms to different measures of locality of reference and compressibility.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliLopezOrtiz2013SurveyListUpdate, author = {Shahin Kamali and Alejandro López-Ortiz}, authororder = {alphabetical}, authorurl2 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, title = {A Survey of Algorithms and Models for List Update}, booktitle = {Proceedings of the 66th Conference on Space-Efficient Data Structures, Streams, and Algorithms -- Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday}, year = {2013}, pages = {251--266}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2013-IanFest.pdf}, venuekey = {MunroFest}, edition = {66}, abstract = {The list update problem was first studied by McCabe more than 45 years ago under distributional analysis in the context of maintaining a sequential file. In 1985, Sleator and Tarjan introduced the competitive ratio framework for the study of worst case behavior on list update algorithms. Since then, many deterministic and randomized online algorithms have been proposed and studied under this framework. The standard model as originally introduced has a peculiar cost function for the rearrangement of the list after each search operation. To address this, several variants have been introduced, chiefly the MRM model (Martinez and Roura; and Munro), the paid exchange model, and the compression model. Additionally, the list update problem has been studied under locality of reference assumptions, and several models have been proposed to capture locality of input sequences. This survey gives a brief overview of the main list update algorithms, the main alternative cost models, and the related results for list update with locality of reference. Open problems and directions for future work are included.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{DorrigivEtAl2012MSTNeighborhoods, author = {Reza Dorrigiv and Robert Fraser and Meng He and Shahin Kamali and Akitoshi Kawamura and Alejandro López-Ortiz and Diego Seco}, authororder = {alphabetical}, authorurl3 = {https://web.cs.dal.ca/~mhe/}, authorurl6 = {https://cs.uwaterloo.ca/~alopez-o/index.html}, authorurl7 = {https://lbd.udc.es/ShowResearcherInformation.do?lang=en_US}, title = {On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods}, booktitle = {Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA)}, year = {2012}, pages = {93--106}, pdf = {https://web.cs.dal.ca/~mhe/publications/wowa12_spanningtree.pdf}, venuekey = {WAOA}, edition = {10}, abstract = {We study optimization problems for the Euclidean minimum spanning tree (MST) on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the minimum spanning tree with neighborhoods (MSTN) problem, and the maximum weight version (max-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the max-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{KamaliEtAl2011DataAllocation, author = {Shahin Kamali and Pedram Ghodsnia and Khuzaima Daudjee}, authorurl3 = {https://cs.uwaterloo.ca/~kdaudjee/}, title = {Dynamic Data Allocation with Replication in Distributed Systems}, booktitle = {Proceedings of the 30th International Performance Computing and Communications Conference (IPCCC)}, year = {2011}, pages = {1--8}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2011-IPCCC.pdf}, venuekey = {IPCCC}, edition = {30}, abstract = {The goal of fragment allocation in distributed database systems is to place data fragments at sites so as to minimize the overall data transmission cost incurred to answer queries. We consider the problem of fragment allocation in lazily replicated systems and address both placement and replication issues in an integrated approach. While replication can improve performance via increased locality, excessive replication can incur extra overhead cost to maintain replicas. A comprehensive model that takes into account network topology, fragment correlation, and data access patterns is presented. Based on this model, we propose an algorithm to find near-optimal dynamic allocation solutions. Experimental results show the efficacy of the proposed solution.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{FarzanKamali2011TreewidthOracles, author = {Arash Farzan and Shahin Kamali}, authororder = {alphabetical}, title = {Compact Navigation and Distance Oracles for Graphs with Small Treewidth}, booktitle = {Proceedings of the 38th EATCS International Colloquium on Automata, Languages, and Programming (ICALP)}, year = {2011}, pages = {268--280}, pdf = {https://cs.uwaterloo.ca/research/tr/2011/CS-2011-15.pdf}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2011-ICALP.pdf}, venuekey = {ICALP}, edition = {38}, abstract = {Given an unlabeled, unweighted, and undirected graph with $n$ vertices and small (but not necessarily constant) treewidth $k$, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is $\Omega(\log n)$ bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with $n$ vertices and treewidth $k$. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in $O(k^3\log^3 k)$ time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where $k$ is constant), the distances are reported in constant worst-case time.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{HarutyunyanKamali2010OptimumBroadcasting, author = {Hovhannes Harutyunyan and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://users.encs.concordia.ca/~haruty/}, title = {Optimum Broadcasting in Complete Weighted-vertex Graphs}, booktitle = {Proceedings of the 36th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)}, year = {2010}, pages = {489--502}, doi = {10.1007/978-3-642-11266-9_41}, url = {https://doi.org/10.1007/978-3-642-11266-9_41}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2010-SOFSEM.pdf}, venuekey = {SOFSEM}, edition = {36}, abstract = {The weighted-vertex broadcast model is an extension of the original model of broadcasting to graphs with weighted vertices. A vertex of weight $w$ is supposed to wait for $w$ time rounds before sending data to its neighbors; after this delay, in each round, it can inform one of its neighbors with no additional delay. We consider the problem in complete weighted-vertex graphs, and introduce a set of properties which describe a class of optimum solutions. Based on these, we present an algorithm which gives optimum broadcast schemes in polynomial time.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{HarutyunyanEtAl2008Multicasting, author = {Hovhannes Harutyunyan and Shahin Kamali and Talin Moradian}, authororder = {alphabetical}, authorurl1 = {https://users.encs.concordia.ca/~haruty/}, title = {Multi-Shared-Trees Based Multicasting in Mesh-Connected Networks}, booktitle = {Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA)}, year = {2008}, pages = {178--182}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2008-PDPTA.pdf}, venuekey = {PDPTA}, abstract = {Performance of multicomputers is a matter of underlying network communications such as multicast. Multicasting is an efficient information dissemination for a subscribed user group on networks. We study multicasting problem in meshconnected networks. Having a group of processors distributed on the mesh, the goal is to present a routing strategy such that every member of the group can effectively transmit data to the other members. The conventional strategies to the problem are source-based and shared-tree approaches, each having drawbacks in efficiency or scalability of large networks. To compromise between these two we use multi-shared tree approach. We apply a core-selection algorithm based on taxicab geometry to create a small number of distribution trees that are almost optimum with respect to multicast time and traffic.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{HarutyunyanKamali2008WeightedVertexISPA, author = {Hovhannes Harutyunyan and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://users.encs.concordia.ca/~haruty/}, title = {Broadcasting in Weighted-vertex Graphs}, booktitle = {Proceedings of the International Symposium on Parallel and Distributed Processing with Applications (ISPA)}, year = {2008}, pages = {301--307}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2008-ISPA.pdf}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2008-ISPA.pdf}, venuekey = {ISPA}, abstract = {In this paper a new model for information dissemination in communication network is presented. The model is defined on networks in which nodes are assigned some weights representing the internal delay they should pass before sending data to their neighbors. The new model, called weighted-vertex model, comes to have real world applications in parallel computation and satellite terrestrial networks. As a generalization of the classical model, optimum broadcasting in weighted-vertex model is NP_Hard. The problem remains NP_Hard in some classes of weighed-vertex graphs. We show existence of approximation algorithms for the broadcasting problem in weighted vertex model, as well as better approximations for specific subclasses of weighted graphs.}, category = {conference}, display = {yes}, cv = {yes} } @inproceedings{HarutyunyanKamali2008WeightedNodes, author = {Hovhannes Harutyunyan and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://users.encs.concordia.ca/~haruty/}, title = {Efficient Broadcasting in Networks with Weighted Nodes}, booktitle = {Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS)}, year = {2008}, pages = {879--884}, url = {https://ieeexplore.ieee.org/document/4724411}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2008-ICPADS.pdf}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2008-ICPADS.pdf}, venuekey = {ICPADS}, edition = {14}, abstract = {In this paper the problem of broadcasting in networks with weighted nodes is considered. This model is defined on networks in which nodes are assigned some weights representing the internal process or delay that they should perform before sending data to their neighboring nodes. This model has real world applications in parallel computation and satellite terrestrial networks. The problem is shown to be NP-complete. In this paper we present three algorithms to find near optimal broadcast time of an arbitrary network with weighted nodes. We also present our simulation results to compare the performance of these algorithms.}, category = {conference}, display = {yes}, cv = {yes} } @mastersthesis{Kamali2008MSc, author = {Shahin Kamali}, title = {Broadcasting in Weighted-vertex Graphs}, school = {Department of Computer Science and Software Engineering, Concordia University}, year = {2008}, url = {https://spectrum.library.concordia.ca/id/eprint/976179/}, slides = {https://www.eecs.yorku.ca/~kamalis/slides/2008-Thesis.pdf}, abstract = {In this thesis, we present a new model for information dissemination in communication networks. The model is defined on networks in which nodes are assigned weights representing the internal delay they must pass before sending data to their neighbors. The new model, called the weighted-vertex model, has real-world applications in parallel computation and satellite-terrestrial networks. Broadcasting in weighted-vertex model is a generalized version of classical broadcasting problem, which is NP\_Complete. The problem remains NP\_Complete in some classes of weighted-vertex graphs. We show the existence of approximation algorithms for the broadcasting problem in the weighted-vertex model, as well as better approximations for specific subclasses of weighted graphs. In addition, we study broadcasting in complete weighted graphs and present an algorithm for finding the optimum solution in this case. Broadcasting in complete graphs with uniform weights is studied separately. Finally, we introduce some heuristics for the problem and compare their performance using computer simulations.}, category = {thesis}, display = {yes}, cv = {yes} } @incollection{DashtiEtAl2007Positioning, author = {Hesam T. Dashti and Shahin Kamali and Nima Aghaeepour}, authorurl3 = {https://nalab.stanford.edu/team/nima-aghaeepour/}, title = {Positioning in Robots Soccer}, booktitle = {Robotic Soccer}, year = {2007}, pages = {29--46}, url = {https://www.intechopen.com/chapters/519}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2007-Positioning.pdf}, abstract = {In this chapter, the focus is on an important issue of robots' decision-making process which is positioning. Positioning involves making the best decision for the agents who do not possess the ball regarding the team strategy and consequently finding the best target for them. We overview the importance of positioning, review the existing approaches for positioning, including strategic positioning, dynamic positioning, and positioning using machine learning. We particularly discuss a dynamic positioning approach that uses Voronoi diagrams and provide evidence for its efficiency and effectiveness.}, category = {bookchapter}, display = {yes}, cv = {yes} } @inproceedings{DashtiEtAl2005DPVC, author = {HesamAddin Torabi Dashti and Nima Aghaeepour and Sahar Asadi and Meysam Bastani and Zahra Delafkar and Fatemeh Miri Disfani and Serveh Mam Ghaderi and Shahin Kamali and Sepideh Pashami and Alireza Fotuhi Siahpirani}, authororder = {alphabetical}, authorurl2 = {https://nalab.stanford.edu/team/nima-aghaeepour/}, authorurl9 = {https://www.hh.se/english/information-english/search-staff.html?person=2CE91140-5CED-4B06-A992-0567E1AB399A}, title = {Dynamic Positioning based on Voronoi Cells (DPVC)}, booktitle = {Proceedings of the Robot Soccer World Cup (RoboCup)}, year = {2005}, pages = {219--229}, doi = {10.1007/11780519_20}, url = {https://doi.org/10.1007/11780519_20}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2005-RoboCup.pdf}, venuekey = {RoboCup}, abstract = {In this paper we are proposing an approach for flexible positioning of players in Soccer Simulation in a Multi-Agent environment. We introduce Dynamic Positioning based on Voronoi Cells (DPVC) as a new method for players' positioning which uses Voronoi Diagram for distributing agents in the field. This method also uses Attraction Vectors that indicate agents' tendency to specific objects in the field with regard to the game situation and players' roles. Finally DPVC is compared with SBSP as the conventional method of positioning.}, category = {conference}, display = {yes}, cv = {yes} } @article{BibbensEtAl2026GreenBinPackingJournal, author = {Jackson Bibbens and Cooper Sigrist and Bo Sun and Shahin Kamali and Mohammad Hajiesmaili}, authorurl3 = {https://sunbo-online.github.io/}, authorurl5 = {https://groups.cs.umass.edu/hajiesmaili/}, title = {Green Bin Packing}, journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems}, year = {2026}, volume = {10}, number = {1}, pages = {11:1--11:51}, doi = {10.1145/3788093}, arxiv = {https://arxiv.org/abs/2510.26968}, venuekey = {POMACS}, abstract = {The online bin packing problem and its variants are regularly used to model server allocation problems. Modern concerns surrounding sustainability and overcommitment in cloud computing motivate bin packing models that capture costs associated with highly utilized servers. In this work, we introduce the \textit{green bin packing} problem, an online variant with a linear cost $\beta$ for filling above a fixed level $G$. For a given instance, the goal is to minimize the sum of the number of opened bins and the linear cost. We show that when $\beta \le 1/G$, classical online bin packing algorithms such as FirstFit or Harmonic perform well, and can achieve competitive ratios lower than in the classic setting. However, when $\beta > 1/G$, new algorithmic solutions can improve both worst-case and typical performance. We introduce variants of classic online bin packing algorithms and establish theoretical bounds, as well as test their empirical performance.}, category = {journal}, display = {yes}, cv = {yes} } @article{BoyarEtAl2026IntervalSchedulingJournal, author = {Joan Boyar and Lene M. Favrholdt and Shahin Kamali and Kim S. Larsen}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl4 = {https://imada.sdu.dk/u/kslarsen/}, title = {Online Interval Scheduling with Predictions}, journal = {Journal of Computer and System Sciences (JCSS)}, year = {2026}, volume = {160}, pages = {103795}, url = {https://www.sciencedirect.com/science/article/pii/S0022000026000413}, arxiv = {https://arxiv.org/abs/2302.13701}, venuekey = {JCSS}, abstract = {In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each consisting of pairs of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. We study a setting with a potentially erroneous prediction specifying the set of requests forming the input sequence and provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.}, category = {journal}, display = {yes}, cv = {yes} } @article{BoyarEtAl2026WeightedNonCrossingJournal, author = {Joan Boyar and Shahin Kamali and Kim S. Larsen and Ali Mohammad Lavasani and Yaqiao Li and Denis Pankratov}, authororder = {alphabetical}, authorurl1 = {https://imada.sdu.dk/u/joan/}, authorurl3 = {https://imada.sdu.dk/u/kslarsen/}, authorurl5 = {https://li-ya-qiao.github.io/}, authorurl6 = {https://pankratov.ca/}, title = {On the Online Weighted Non-Crossing Matching Problem}, journal = {Information and Computation}, year = {2026}, volume = {310}, pages = {105440}, url = {https://www.sciencedirect.com/science/article/pii/S0890540126000386}, arxiv = {https://arxiv.org/abs/2603.09262}, venuekey = {InfComput}, abstract = {We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: 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 classic 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, but we give upper and lower bounds on the problem with bounded weights. In contrast to the deterministic case, we show that using randomization, a constant competitive ratio is possible for arbitrary weights. We also study other variants of the problem, including revocability and collinear points, both of which permit non-trivial online algorithms, and we give upper and lower bounds for the attainable competitive ratios. Finally, we prove an advice complexity bound for obtaining optimality, improving the best known bound.}, category = {journal}, display = {yes}, cv = {yes} } @misc{AkitayaEtAl2025OpenProblemsCCCG, author = {Hugo A. Akitaya and Shahin Kamali and Seyed-Mohammad Seyed-Javadi and Frederick Stock}, authororder = {alphabetical}, authorurl1 = {https://www.cs.uml.edu/~hakitaya/}, title = {Open Problems from CCCG 2025}, year = {2025}, pages = {371--376}, pdf = {https://www.eecs.yorku.ca/~kamalis/papers/2025-CCCG_Open_Problems.pdf}, abstract = {The following is a list of the problems presented during the open problem session at the 37th Annual Canadian Conference on Computational Geometry (CCCG), held at York University in Toronto from August 13 to 15, 2025. This year’s open problem session took place on the second day of the conference and featured lively participation from attendees. As in past years, the session served as a catalyst for spontaneous collaboration and discussion throughout the remainder of the meeting. Open problem sessions have long been a tradition at CCCG, offering a venue for researchers to share intriguing questions, conjectures, and partially explored ideas. The 2025 session continued this tradition, with problems spanning classical themes such as Minkowski-type existence results and modern geometric inequalities. To the best of our knowledge, the problems below accurately reflect the questions posed during the session. The problems are listed in the order in which they were presented at the conference. Where appropriate, references and attributions to presenters have been included.}, category = {other}, display = {yes}, cv = {yes}, howpublished = {Proceedings of the 37th Canadian Conference on Computational Geometry (CCCG)} } @misc{Kamali2025CCCGProceedings, author = {Shahin Kamali}, title = {Proceedings of the 37th Canadian Conference on Computational Geometry}, year = {2025}, note = {Editor}, url = {https://cccg.ca/proceedings/2025/CCCG2025-Proceedings.pdf}, abstract = {This volume contains the papers presented at the 37th Canadian Conference on Computational Geometry (CCCG 2025), held on August 13–15, 2025, at York University (Keele Campus) in Toronto, Canada. The conference was co-located with the Workshop on Algorithms and Data Structures (WADS 2025), which took place on August 11–13, continuing the successful tradition of co-locating CCCG and WADS that began in 2019. These proceedings will be made available electronically after the conclusion of the conference on the CCCG website: http://www.cccg.ca/. This year, CCCG received 69 submissions. After the review process, 44 papers were accepted. Each submission received at least three reviews. We thank the Program Committee for their diligent and thoughtful reviewing and discussions, which ensured a high-quality technical program. We especially thank the invited speakers for their outstanding contributions to the conference program: Dr. Piotr Indyk (MIT), who delivered the Paul Erd˝os Memorial Talk; Dr. David Mount (University of Maryland), who delivered the Godfried Toussaint Memorial Talk; and Dr. Birgit Vogtenhuber (Graz University of Technology), who delivered the Ferran Hurtado Memorial Talk. Their talks added depth and perspective to CCCG 2025, and we are grateful to them for sharing their insights with the computational geometry community. We also continued the Best PhD Dissertation Award, which was administered through a dedicated submission track with a review process similar to that of regular papers. This year, four doctoral theses were submitted, each receiving three reviews by members of the CCCG Steering Committee. The award was presented to: Da Wei (David) Zheng (University of Illinois Urbana-Champaign), supervised by Timothy Chan “From Geometry to Graphs and Back: Geometric Range Searching and Algorithms in Structured Graphs” In addition, the Best Paper Award was selected through a multi-stage process. During the review period, discussions were initiated for papers that received perfect or near-perfect scores. Following additional evaluations and discussions among Program Committee members and the Steering Committee, the award was presented to: Elizabeth Munch, Elena Xinyi Wang, and Carola Wenk “The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data” We gratefully acknowledge the generous financial support of our sponsors: the Centre for Innovation in Computing at Lassonde (IC@L), Research and Innovation at York University, the Lassonde School of Engineering at York University, and the Department of Electrical Engineering and Computer Science (EECS) at York University. We thank all authors for submitting their work, as well as the presenters for sharing their research at the conference. Our sincere appreciation goes to the members of the Program Committee and the Steering Committee for their time, care, and professionalism throughout the reviewing and decision-making processes. We also thank the student volunteers whose dedication made this conference possible.}, category = {other}, display = {no}, cv = {yes} } @misc{KamaliLeiserson2023DynamicStorage, author = {Shahin Kamali and Charles E. Leiserson}, authororder = {alphabetical}, authorurl2 = {https://people.csail.mit.edu/cel/}, title = {On Competitiveness of Online Algorithms for Dynamic Storage Allocation}, year = {2023}, category = {other}, display = {no}, cv = {yes} } @misc{AngelopoulosArsenioKamali2023OptimalContract, author = {Spyros Angelopoulos and Diogo Arsénio and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://perso.lip6.fr/Spyros.Angelopoulos/}, title = {Optimal Contract Scheduling with Query-Based Predictions}, year = {2023}, category = {other}, display = {no}, cv = {yes} } @article{DurocherKamali2020CCCGSpecialIssue, author = {Stephane Durocher and Shahin Kamali}, authororder = {alphabetical}, authorurl1 = {https://home.cs.umanitoba.ca/~durocher/}, title = {Special Issue for Selected Articles from the 30th Canadian Conference on Computational Geometry}, year = {2020}, volume = {90}, url = {https://www.sciencedirect.com/science/article/pii/S0925772120300468}, category = {journal}, display = {no}, cv = {yes} } @misc{KamaliCCCG25, author = {Shahin Kamali}, title = {Proceedings of the 37th Canadian Conference on Computational Geometry, CCCG 2025}, year = {2025}, note = {Edited proceedings; editor: Shahin Kamali.}, pdf = {https://cccg.ca/proceedings/2025/CCCG2025-Proceedings.pdf}, abstract = {This volume contains the papers presented at the 37th Canadian Conference on Computational Geometry (CCCG 2025), held on August 13–15, 2025, at York University (Keele Campus) in Toronto, Canada. The conference was co-located with the Workshop on Algorithms and Data Structures (WADS 2025), which took place on August 11–13, continuing the successful tradition of co-locating CCCG and WADS that began in 2019. These proceedings will be made available electronically after the conclusion of the conference on the CCCG website: http://www.cccg.ca/. This year, CCCG received 69 submissions. After the review process, 44 papers were accepted. Each submission received at least three reviews. We thank the Program Committee for their diligent and thoughtful reviewing and discussions, which ensured a high-quality technical program. We especially thank the invited speakers for their outstanding contributions to the conference program: Dr. Piotr Indyk (MIT), who delivered the Paul Erd˝os Memorial Talk; Dr. David Mount (University of Maryland), who delivered the Godfried Toussaint Memorial Talk; and Dr. Birgit Vogtenhuber (Graz University of Technology), who delivered the Ferran Hurtado Memorial Talk. Their talks added depth and perspective to CCCG 2025, and we are grateful to them for sharing their insights with the computational geometry community. We also continued the Best PhD Dissertation Award, which was administered through a dedicated submission track with a review process similar to that of regular papers. This year, four doctoral theses were submitted, each receiving three reviews by members of the CCCG Steering Committee. The award was presented to: Da Wei (David) Zheng (University of Illinois Urbana-Champaign), supervised by Timothy Chan “From Geometry to Graphs and Back: Geometric Range Searching and Algorithms in Structured Graphs” In addition, the Best Paper Award was selected through a multi-stage process. During the review period, discussions were initiated for papers that received perfect or near-perfect scores. Following additional evaluations and discussions among Program Committee members and the Steering Committee, the award was presented to: Elizabeth Munch, Elena Xinyi Wang, and Carola Wenk “The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data” We gratefully acknowledge the generous financial support of our sponsors: the Centre for Innovation in Computing at Lassonde (IC@L), Research and Innovation at York University, the Lassonde School of Engineering at York University, and the Department of Electrical Engineering and Computer Science (EECS) at York University. We thank all authors for submitting their work, as well as the presenters for sharing their research at the conference. Our sincere appreciation goes to the members of the Program Committee and the Steering Committee for their time, care, and professionalism throughout the reviewing and decision-making processes. We also thank the student volunteers whose dedication made this conference possible.}, category = {other}, display = {yes}, cv = {yes} }