Source author record

Julián Mestre

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory Discrete Mathematics

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Nested Active-Time Scheduling

The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to $g$ jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. In this way, the active time models parallel scheduling when there is a fixed cost for turning the machine on at each discrete step. This paper presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case.

preprint2016arXiv

A 4-approximation for scheduling on a single machine with general cost function

We consider a single machine scheduling problem that seeks to minimize a generalized cost function: given a subset of jobs we must order them so as to minimize $\sum f_j(C_j)$ , where $C_j$ is the completion time of job $j$ and $f_j$ is a job-dependent cost function. This problem has received a considerably amount of attention lately, partly because it generalizes a large number of sequencing problems while still allowing constant approximation guarantees. In a recent paper, Cheung and Shmoys provided a primal-dual algorithm for the problem and claimed that is a 2-approximation. In this paper we show that their analysis cannot yield an approximation guarantee better than $4$ . We then cast their algorithm as a local ratio algorithm and show that in fact it has an approximation ratio of $4$ . Additionally, we consider a more general problem where jobs has release dates and can be preempted. For this version we give a $4κ$ -approximation algorithm where $κ$ is the number of distinct release dates.

preprint2016arXiv

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_{j}$ : we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$ , and there is a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost of finishing $j$ at time $C_{j}$ ; the objective is to minimize $\sum_{j=1}^n f_j(C_j)$ . Bansal \& Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the LP is less than 4. Finally, we show how the technique can be adapted to yield, for any $ε>0$ , a $(4+ε)$ -approximation algorithm for this problem.

preprint2014arXiv

How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions

Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, and one seeks to schedule the jobs to minimize the total sum of these costs. The framework captures many important scheduling objectives such as weighted flow time or weighted tardiness. Still, the general case as well as the mentioned special cases are far from being very well understood yet, even for only one machine. Aiming for better general understanding of this problem, in this paper we focus on the case of uniform job release dates on one machine for which the state of the art is a 4-approximation algorithm. This is true even for a special case that is equivalent to the covering version of the well-studied and prominent unsplittable flow on a path problem, which is interesting in its own right. For that covering problem, we present a quasi-polynomial time $(1+ε)$ -approximation algorithm that yields an $(e+ε)$ -approximation for the above scheduling problem. Moreover, for the latter we devise the best possible resource augmentation result regarding speed: a polynomial time algorithm which computes a solution with \emph{optimal }cost at $1+ε$ speedup. Finally, we present an elegant QPTAS for the special case where the cost functions of the jobs fall into at most $\log n$ many classes. This algorithm allows the jobs even to have up to $\log n$ many distinct release dates.

preprint2014arXiv

Parametrized Algorithms for Random Serial Dictatorship

Voting and assignment are two of the most fundamental settings in social choice theory. For both settings, random serial dictatorship (RSD) is a well-known rule that satisfies anonymity, ex post efficiency, and strategyproofness. Recently, it was shown that computing the resulting probabilities is #P-complete both in the voting and assignment setting. In this paper, we study RSD from a parametrized complexity perspective. More specifically, we present efficient algorithms to compute the RSD probabilities under the condition that the number of agent types, alternatives, or objects is bounded.

preprint2010arXiv

Improved bounds for stochastic matching

This results in this paper have been merged with the result in arXiv:1003.0167. The authors would like to withdraw this version. Please see arXiv:1008.5356 for the merged version.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.