Alberto Marchetti-Spaccamela
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
Research Subjects
Alberto Marchetti-Spaccamela has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
- Vincenzo Bonifaci
Institute for the Analysis of Systems and Informatics National Research Council of Italy (IASI-CNR) Rome Italy
7 shared publications - Leen Stougie
Vrije Universiteit Amsterdam The Netherlands
4 shared publications - Daniele Frigioni
University of L'Aquila
3 shared publications - Umberto Nanni
Department of Computer, Control and Management Engineering "Antonio Ruberti", "Sapienza" University, Rome, Italy
3 shared publications - Kirk Pruhs
University of Pittsburgh, Pittsburgh, PA, USA
2 shared publications - Lap-Kei Lee
School of Science and Technology, Hong Kong Metropolitan University, Hong Kong SAR, China
2 shared publications
Latest Publications
- Open Access
Approximation Algorithms for Replenishment Problems with Fixed Turnover Times
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 AccessApproximation Algorithms for Replenishment Problems with Fixed Turnover Times
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
- 19 September 2016
- Published by Springer Nature in Algorithms for Molecular Biology
- Vol. 11 (1) , 1-15
Enumeration of minimal stoichiometric precursor sets in metabolic networks
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/ .
- 19 September 2016
- Published by Springer Nature in Algorithms for Molecular Biology
- Vol. 11 (1) , 1-15
Open AccessEnumeration of minimal stoichiometric precursor sets in metabolic networks
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/ .
- 24 October 2014
- Published by Springer Nature in Mathematical Programming
- Vol. 154 (1-2) , 305-328
Strong LP formulations for scheduling splittable jobs on unrelated machines
- 24 October 2014
- Published by Springer Nature in Mathematical Programming
- Vol. 154 (1-2) , 305-328
Strong LP formulations for scheduling splittable jobs on unrelated machines
- 14 May 2014
- Published by Springer Nature in Mathematical Programming
- Vol. 152 (1-2) , 247-274
Assigning sporadic tasks to unrelated machines
- 14 May 2014
- Published by Springer Nature in Mathematical Programming
- Vol. 152 (1-2) , 247-274
Assigning sporadic tasks to unrelated machines
- Open Access
Scheduling over Scenarios on Two Machines
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.
Open AccessScheduling over Scenarios on Two Machines
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.
- 1 October 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 457, 1-9
Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets
- 1 October 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 457, 1-9
Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets
- Open Access
Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks
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.
Open AccessSocial-Aware Forwarding Improves Routing Performance in Pocket Switched Networks
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.
- 27 May 2011
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (24) , 2563
Preface
- Open Access
- 18 March 2011
- Published by Springer Nature in Algorithmica
- Vol. 63 (4) , 763-780
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
- 18 March 2011
- Published by Springer Nature in Algorithmica
- Vol. 63 (4) , 763-780
Open AccessFeasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
- 4 March 2011
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (8-10) , 633-641
The distributed wireless gathering problem
- 4 March 2011
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (8-10) , 633-641
The distributed wireless gathering problem