Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Alberto Marchetti-Spaccamela has a total of 57 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Approximation Algorithms for Replenishment Problems with Fixed Turnover Times

    by Thomas Bosman, Martijn van Ee, Yang Jiao, Alberto Marchetti-Spaccamela, R. Ravi, Leen Stougie

    We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

  • Open Access

    Enumeration of minimal stoichiometric precursor sets in metabolic networks

    by Ricardo Andrade, Martin Wannagat, Cecilia C. Klein, Vicente Acuña, Alberto Marchetti-Spaccamela, Paulo V. Milreu, Leen Stougie, Marie-France Sagot

    What an organism needs at least from its environment to produce a set of metabolites, e.g. target(s) of interest and/or biomass, has been called a minimal precursor set. Early approaches to enumerate all minimal precursor sets took into account only the topology of the metabolic network (topological precursor sets). Due to cycles and the stoichiometric values of the reactions, it is often not possible to produce the target(s) from a topological precursor set in the sense that there is no feasible flux. Although considering the stoichiometry makes the problem harder, it enables to obtain biologically reasonable precursor sets that we call stoichiometric. Recently a method to enumerate all minimal stoichiometric precursor sets was proposed in the literature. The relationship between topological and stoichiometric precursor sets had however not yet been studied. Such relationship between topological and stoichiometric precursor sets is highlighted. We also present two algorithms that enumerate all minimal stoichiometric precursor sets. The first one is of theoretical interest only and is based on the above mentioned relationship. The second approach solves a series of mixed integer linear programming problems. We compared the computed minimal precursor sets to experimentally obtained growth media of several Escherichia coli strains using genome-scale metabolic networks. The results show that the second approach efficiently enumerates minimal precursor sets taking stoichiometry into account, and allows for broad in silico studies of strains or species interactions that may help to understand e.g. pathotype and niche-specific metabolic capabilities. sasita is written in Java, uses cplex as LP solver and can be downloaded together with all networks and input files used in this paper at http://sasita.gforge.inria.fr/ .


  • Strong LP formulations for scheduling splittable jobs on unrelated machines

    by José Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Leen Stougie, Ola Svensson, Víctor Verdugo, José Verschae


  • Assigning sporadic tasks to unrelated machines

    by Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster, Andreas Wiese


  • Open Access

    Scheduling over Scenarios on Two Machines

    by Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie, Anke van Zuylen

    We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scenario is a subset of jobs that must be executed in that scenario and all scenarios are given explicitly. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. With this research into optimization problems over scenarios, we have opened a new and rich field of interesting problems.

  • Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

    by Vicente Acuña, Etienne Birmelé, Ludovic Cottret, Pierluigi Crescenzi, Fabien Jourdan, Vincent Lacroix, Alberto Marchetti-Spaccamela, Andrea Marino, Paulo Vieira Milreu, Marie-France Sagot, et al.


  • Open Access

    Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks

    by Josep Diaz, Alberto Marchetti-Spaccamela, Dieter Mitsche, Paolo Santi, Julinda Stefa

    Several social-aware forwarding strategies have been recently introduced in opportunistic networks, and proved effective in considerably in- creasing routing performance through extensive simulation studies based on real-world data. However, this performance improvement comes at the expense of storing a considerable amount of state information (e.g, history of past encounters) at the nodes. Hence, whether the benefits on routing performance comes directly from the social-aware forwarding mechanism, or indirectly by the fact state information is exploited is not clear. Thus, the question of whether social-aware forwarding by itself is effective in improving opportunistic network routing performance remained unaddressed so far. In this paper, we give a first, positive answer to the above question, by investigating the expected message delivery time as the size of the net- work grows larger.

  • Preface

    by Susanne Albers, Alberto Marchetti-Spaccamela

  • Open Access

    Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems

    by Vincenzo Bonifaci, Alberto Marchetti-Spaccamela


  • The distributed wireless gathering problem

    by Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie