131 citations · 159 across the 17 of their papers we have counts for
23 papers
On the Online Weighted Non-Crossing Matching Problem
Joan Boyar, Shahin Kamali, Kim S. Larsen +3
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…
Time Fairness in Online Knapsack Problems
Adam Lechowicz, Rik Sengupta, Bo Sun +2
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 int…
Online Interval Scheduling with Predictions
Joan Boyar, Lene M. Favrholdt, Shahin Kamali +1
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 p…
Rényi-Ulam Games and Online Computation with Imperfect Advice
Spyros Angelopoulos, Shahin Kamali
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 a possibly erroneous b…
Online Search With Best-Price and Query-Based Predictions
Spyros Angelopoulos, Shahin Kamali, Dehou Zhang
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 e…
Competitive Sequencing with Noisy Advice
Spyros Angelopoulos, Diogo Arsénio, Shahin Kamali
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…
An improved bound on the burning number of graphs
Anthony Bonato, Shahin Kamali
The burning number conjecture states that the burning number of a connected graph is at most While the conjecture is unresolved, Land and Lu proved that t…
Improved pyrotechnics : Closer to the burning graph conjecture
Paul Bastide, Marthe Bonamy, Anthony Bonato +4
The Burning Number Conjecture claims that for every connected graph of order its burning number satisfies While the conjecture remains o…
On the Fault-Tolerant Online Bin Packing Problem
Shahin Kamali, Pooya Nikbakht
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 int…
Online Bin Packing with Predictions
Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami
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 pr…
Contract Scheduling With Predictions
Spyros Angelopoulos, Shahin Kamali
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 o…
Beyond Worst-case Analysis of Multicore Caching Strategies
Shahin Kamali, Helen Xu
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 onli…
Randomized Two-Valued Bounded Delay Online Buffer Management
Christoph Dürr, Shahin Kamali
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…
Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs
Shahin Kamali, Avery Miller, Kenny Zhang
Graph burning is a simple 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 netwo…
Online Computation with Untrusted Advice
Spyros Angelopoulos, Christoph Dürr, Shendan Jin +2
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 un…
Online Bin Covering with Advice
Joan Boyar, Lene M. Favrholdt, Shahin Kamali +1
The bin covering problem asks for covering a maximum number of bins with an online sequence of items of different sizes in the range ; a bin is said to be covered if it…
Approximation Algorithms for Graph Burning
Anthony Bonato, Shahin Kamali
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 bur…
Service Function Chaining Simplified
Milad Ghaznavi, Nashid Shahriar, Reaz Ahmed +1
Middleboxes have become a vital part of modern networks by providing service functions such as content filtering, load balancing and optimization of network traffic. An ordered seq…
Efficient Online Strategies for Renting Servers in the Cloud
Shahin Kamali, Alejandro López-Ortiz
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…
An All-Around Near-Optimal Solution for the Classic Bin Packing Problem
Shahin Kamali, Alejandro López-Ortiz
In this paper we present the first algorithm with optimal average-case and close-to-best known worst-case performance for the classic on-line problem of bin packing. It has long be…
On the List Update Problem with Advice
Joan Boyar, Shahin Kamali, Kim S. Larsen +1
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 inp…
On Advice Complexity of the k-server Problem under Sparse Metrics
Sushmita Gupta, Shahin Kamali, Alejandro López-Ortiz
We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we show that an advice of size Ω(n) is required to o…
Online Bin Packing with Advice
Joan Boyar, Shahin Kamali, Kim S. Larsen +1
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…