A well-known problem in scheduling and approximation algorithms is the Santa Claus
problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among …

We revisit the problem max-min degree arborescence, which was introduced by Bateni et
al.[STOC'09] as a central special case of the general Santa Claus problem, which constitutes …

This paper is devoted to the study of the MaxMinDegree Arborescence (MMDA) problem in
layered directed graphs of depth ℓ≤ O (log n/log log n), which is an important special case …

In the restricted assignment problem, the input consists of a set of machines and a set of jobs
each with a processing time and a subset of eligible machines. The goal is to find an …

We consider scheduling on identical and unrelated parallel machines with job assignment
restrictions. These problems are NP-hard and they do not admit polynomial time …

We study truthful mechanisms for allocation problems in graphs, both for the minimization
(ie, scheduling) and maximization (ie, auctions) setting. The minimization problem is a …

In this paper, we introduce a novel star partitioning problem for simple connected graphs
G=(V, E). The goal is to find a partition of the edges into stars that minimizes the maximum …

Unrelated machines are an abstraction of many scheduling environments appearing in
practical applications, where every job may be processed at a different speed on every …

A fundamental problem in scheduling is makespan minimization on unrelated parallel
machines (R|| C max). Let there be a set J of jobs and a set M of parallel machines, where …

In this thesis, we will have discussions on two main topics, max-min allocation and
scheduling jobs with precedent constraints on machines with communication delays. New …