Search

Your search keyword '"A. Marchetti Spaccamela"' showing total 1,334 results
Start Over Author "A. Marchetti Spaccamela"

Refine your results

more »

more »

more »

more »
1,334 results on '"A. Marchetti Spaccamela"'

52. Total completion time scheduling under scenarios

Author

Bosman, T. (Thomas), Ee, M. (Martijn) van, Ergen, E. (Ekin), Imreh, C. (Csanád), Marchetti Spaccamela, A. (Alberto), Skutella, M. (Martin), Stougie, L. (Leen), Bosman, T. (Thomas), Ee, M. (Martijn) van, Ergen, E. (Ekin), Imreh, C. (Csanád), Marchetti Spaccamela, A. (Alberto), Skutella, M. (Martin), and Stougie, L. (Leen)

Abstract

Scheduling jobs with given processing times on identical parallel machines so as to minimize their total completion time is one of the most basic scheduling problems. We study interesting generalizations of this classical problem involving scenarios. In our model, a scenario is defined as a subset of a predefined and fully specified set of jobs. The aim is to find an assignment of the whole set of jobs to identical parallel machines such that the schedule, obtained for the given scenarios by simply skipping the jobs not in the scenario, optimizes a function of the total completion times over all scenarios. While the underlying scheduling problem without scenarios can be solved efficiently by a simple greedy procedure (SPT rule), scenarios, in general, make the problem NP-hard. We paint an almost complete picture of the evolving complexity landscape, drawing the line between easy and hard. One of our main algorithmic contributions relies on a deep structural result on the maximum imbalance of an optimal schedule, based on a subtle connection to Hilbert bases of a related convex cone.

Published
2023
Full Text
View/download PDF

58. Performance Improvements for Search Systems Using an Integrated Cache of Lists+Intersections

Author

Tolosa, Gabriel, Becchetti, Luca, Feuerstein, Esteban, Marchetti-Spaccamela, Alberto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Moura, Edleno, editor, and Crochemore, Maxime, editor

Published
2014
Full Text
View/download PDF

59. Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

Author

Correa, José R., Marchetti-Spaccamela, Alberto, Matuschke, Jannik, Stougie, Leen, Svensson, Ola, Verdugo, Víctor, Verschae, José, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Lee, Jon, editor, and Vygen, Jens, editor

Published
2014
Full Text
View/download PDF

66. Assigning Sporadic Tasks to Unrelated Parallel Machines

Author

Marchetti-Spaccamela, Alberto, Rutten, Cyriel, van der Ster, Suzanne, Wiese, Andreas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Czumaj, Artur, editor, Mehlhorn, Kurt, editor, Pitts, Andrew, editor, and Wattenhofer, Roger, editor

Published
2012
Full Text
View/download PDF

67. The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems

Author

Agrawal, Kunal, Baruah, Sanjoy, Bender, Michael A., and Marchetti-Spaccamela, Alberto

Subjects
Algorithms using predictions, on-line scheduling, Software and its engineering → Scheduling, classification, energy minimization, Computer systems organization → Real-time systems, robust scheduling
Abstract

The algorithm-design paradigm of algorithms using predictions is explored as a means of incorporating the computations of lower-assurance components (such as machine-learning based ones) into safety-critical systems that must have their correctness validated to very high levels of assurance. The paradigm is applied to two simple example applications that are relevant to the real-time systems community: energy-aware scheduling, and classification using ML-based classifiers in conjunction with more reliable but slower deterministic classifiers. It is shown how algorithms using predictions achieve much-improved performance when the low-assurance computations are correct, at a cost of no more than a slight performance degradation even when they turn out to be completely wrong., LIPIcs, Vol. 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023), pages 3:1-3:19

Published
2023
Full Text
View/download PDF

71. Structures and Hyperstructures in Metabolic Networks

Author

Marchetti-Spaccamela, Alberto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kolman, Petr, editor, and Kratochvíl, Jan, editor

Published
2011
Full Text
View/download PDF

72. Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks

Author

Díaz, Josep, Marchetti-Spaccamela, Alberto, Mitsche, Dieter, Santi, Paolo, Stefa, Julinda, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Demetrescu, Camil, editor, and Halldórsson, Magnús M., editor

Published
2011
Full Text
View/download PDF

73. Mixed-Criticality Scheduling of Sporadic Task Systems

Author

Baruah, Sanjoy K., Bonifaci, Vincenzo, D’Angelo, Gianlorenzo, Marchetti-Spaccamela, Alberto, van der Ster, Suzanne, Stougie, Leen, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Demetrescu, Camil, editor, and Halldórsson, Magnús M., editor

Published
2011
Full Text
View/download PDF

80. Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms

Author

Milreu, Paulo Vieira, Acuña, Vicente, Birmelé, Etienne, Crescenzi, Pierluigi, Marchetti-Spaccamela, Alberto, Sagot, Marie-France, Stougie, Leen, Lacroix, Vincent, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Moulton, Vincent, editor, and Singh, Mona, editor

Published
2010
Full Text
View/download PDF

81. Scheduling Real-Time Mixed-Criticality Jobs

Author

Baruah, Sanjoy K., Bonifaci, Vincenzo, D’Angelo, Gianlorenzo, Li, Haohan, Marchetti-Spaccamela, Alberto, Megow, Nicole, Stougie, Leen, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hliněný, Petr, editor, and Kučera, Antonín, editor

Published
2010
Full Text
View/download PDF

82. Universal Sequencing on a Single Machine

Author

Epstein, Leah, Levin, Asaf, Marchetti-Spaccamela, Alberto, Megow, Nicole, Mestre, Julián, Skutella, Martin, Stougie, Leen, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Eisenbrand, Friedrich, editor, and Shepherd, F. Bruce, editor

Published
2010
Full Text
View/download PDF

86. Approximation Preserving Reductions

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

87. Approximation through Randomization

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

88. Probabilistic analysis of approximation algorithms

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

89. The PCP theorem

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

90. Input-Dependent and Asymptotic Approximation

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

91. NP, PCP and Non-approximability Results

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

92. Approximation Classes

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

93. Heuristic methods

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

94. Design Techniques for Approximation Algorithms

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

95. The Complexity of Optimization Problems

Author

Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, Kann, Viggo, Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Crescenzi, Pierluigi, Gambosi, Giorgio, Protasi, Marco, and Kann, Viggo

Published
1999
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results