5 papers
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…
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 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…