11 papers
Approximating Directed Telephone Multicast
Shahin Kamali, Seyed-Mohammad Seyed-Javadi
In the telephone model a message starts at a source vertex, and in every round each informed vertex may call one neighbour. Telephone multicast asks for a schedule that informs a g…
Geometric Burning Under and Metrics, and Beyond
Shahin Kamali, Saba Yazdani
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…
Fairness in the k-Server Problem
Mohammadreza Daneshvaramoli, Helia Karisani, Mohammad Hajiesmaili +2
We initiate a formal study of fairness for the -server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably am…
Green Bin Packing
Jackson Bibbens, Cooper Sigrist, Bo Sun +2
The online bin packing problem and its variants are regularly used to model server allocation problems. Modern concerns surrounding sustainability and overcommitment in cloud compu…
On Hardness and Approximation of Broadcasting in Structured Graphs
Jeffrey Bringolf, Hovhannes A. Harutyunyan, Shahin Kamali +1
We study the Telephone Broadcasting problem in graphs with restricted structure. Given a designated source in an undirected graph, the goal is to disseminate a message to all verti…
On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi +1
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, wher…
Reconfiguration of Multisets with Applications to Bin Packing
Jeffrey Kam, Shahin Kamali, Avery Miller +1
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 fil…
Robust Learning-Augmented Dictionaries
Ali Zeynali, Shahin Kamali, Mohammad Hajiesmaili
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 aug…
Online Bin Covering with Frequency Predictions
Magnus Berg, Shahin Kamali
We study the discrete bin covering problem where a multiset of items from a fixed set must be split into disjoint subsets while maximizing the number of subsets…
Space-Efficient Data Structures for Polyominoes and Bar Graphs
Magnus Berg, Shahin Kamali, Katherine Ling +1
We provide a compact data structure for representing polyominoes that supports neighborhood and visibility queries. Neighborhood queries concern reporting adjacent cells to a given…
Cops and Robbers on 1-Planar Graphs
Stephane Durocher, Shahin Kamali, Myroslav Kryven +6
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…