4 citations · 8 across the 10 of their papers we have counts for
12 papers
Online Fair Division under Eligibility Constraints
Joes Biburger, Nicole Megow, Golnoosh Shahkarami
We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assig…
Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling
Sander Borst, Golnoosh Shahkarami, Rohit Vaish
We study interval scheduling from the perspective of fair allocation. There are identical machines and a set of intervals, each specified by a start time, an end time, and a no…
A Switching Framework for Online Interval Scheduling with Predictions
Antonios Antoniadis, Ali Shahheidar, Golnoosh Shahkarami +1
We study online interval scheduling in the irrevocable setting, where each interval must be immediately accepted or rejected upon arrival. The objective is to maximize the total le…
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin +1
We consider the problem of guaranteeing maximin-share (MMS) when allocating a set of indivisible items to a set of agents with fractionally subadditive (XOS) valuations. For XOS va…
Learning-Augmented Online TSP on Rings, Trees, Flowers and (almost) Everywhere Else
Evripidis Bampis, Bruno Escoffier, Themis Gouleakis +4
We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric sp…
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either or $p/q…
Learning-Augmented Algorithms for Online TSP on the Line
Themis Gouleakis, Konstantinos Lakis, Golnoosh Shahkarami
We study the online Traveling Salesman Problem (TSP) on the line augmented with machine-learned predictions. In the classical problem, there is a stream of requests released over t…
A Novel Prediction Setup for Online Speed-Scaling
Antonios Antoniadis, Peyman Jabbarzade Ganje, Golnoosh Shahkarami
Given the rapid rise in energy demand by data centers and computing systems in general, it is fundamental to incorporate energy considerations when designing (scheduling) algorithm…
Maximizing Nash Social Welfare in 2-Value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We consider the problem of maximizing the Nash social welfare when allocating a set of indivisible goods to a set of agents. We study instances, in whic…
Nash Social Welfare for 2-value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Kurt Mehlhorn +2
This paper is merged with arXiv:2107.08965v2. We refer the reader to the full and updated version. We study the problem of allocating a set of indivisible goods among agents with 2…
Physarum-Inspired Multi-Commodity Flow Dynamics
Vincenzo Bonifaci, Enrico Facca, Frederic Folz +6
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path pr…
Complexity of Computing the Anti-Ramsey Numbers for Paths
Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani +3
The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd\" os, Simonovits and S\' os. For given graphs and the \emph{anti-Ramsey number}…