131 citations · 159 across the 17 of their papers we have counts for
16 papers · 1 filter
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…
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…
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…
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…
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…
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…