Arrow Research search

Author name cluster

Alberto Marchetti-Spaccamela

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

29 papers
2 author rows

Possible papers

29

TCS Journal 2026 Journal Article

Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity

  • Georgios Amanatidis
  • Federico Fusco
  • Philip Lazos
  • Stefano Leonardi
  • Alberto Marchetti-Spaccamela
  • Rebecca Reiffenhäuser

Submodular maximization is a classic algorithmic problem with multiple applications in data mining and machine learning; there, the growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the adaptive complexity, which captures the number of sequential rounds of parallel computation needed by an algorithm to terminate. In this work, we obtain the first constant factor approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with near-optimal O(log n) adaptive complexity. Low adaptivity by itself, however, is not enough: a crucial feature to account for is represented by the total number of function evaluations (or value queries). Our algorithm asks O ˜ ( n 2 ) value queries but can be modified to run with only O ˜ ( n ), while retaining a low adaptive complexity of O(log2 n). Besides the above improvement in adaptivity, this is also the first combinatorial approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives.

Details DOI

TCS Journal 2025 Journal Article

Feasibility analysis of recurrent DAG tasks is PSPACE-hard

  • Vincenzo Bonifaci
  • Alberto Marchetti-Spaccamela

We study a popular task model for scheduling parallel real-time tasks, where the internal parallelism of each task is modeled by a directed acyclic graph (DAG). We show that deciding the feasibility of a set of sporadically recurrent DAG tasks is hard for the complexity class PSPACE, thus ruling out approaches to this problem that rely on Integer Linear Programming or Satisfiability solvers (assuming NP ≠ PSPACE ).

Details DOI

NeurIPS Conference 2022 Conference Paper

A Universal Error Measure for Input Predictions Applied to Online Graph Problems

  • Giulia Bernardini
  • Alexander Lindermayr
  • Alberto Marchetti-Spaccamela
  • Nicole Megow
  • Leen Stougie
  • Michelle Sweering

We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the online traveling salesperson problem and the online dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality.

PDF Details

ICML Conference 2021 Conference Paper

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity

  • Georgios Amanatidis
  • Federico Fusco 0001
  • Philip Lazos
  • Stefano Leonardi 0001
  • Alberto Marchetti-Spaccamela
  • Rebecca Reiffenhäuser

The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the \emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first \emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with \emph{near-optimal} $O(\log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $\tilde{O}(n^2)$ value queries, but can be modified to run with only $\tilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(\log^2n)$. Besides the above improvement in adaptivity, this is also the first \emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms’ applicability on real-world datasets.

Details

TCS Journal 2013 Journal Article

Preface

  • Camil Demetrescu
  • Stefano Leonardi
  • Alberto Marchetti-Spaccamela
Details DOI

TCS Journal 2012 Journal Article

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

  • Vicente Acuña
  • Etienne Birmelé
  • Ludovic Cottret
  • Pierluigi Crescenzi
  • Fabien Jourdan
  • Vincent Lacroix
  • Alberto Marchetti-Spaccamela
  • Andrea Marino

We present a constrained version of the problem of enumerating all maximal directed acyclic subgraphs (DAG) of a graph G. In this version, we enumerate maximal DAGs whose sources and targets belong to a predefined subset of the nodes. We call such DAGs stories. We first show how to compute one story in polynomial-time, and then describe two different algorithms to “tell” all possible stories.

Details DOI

TCS Journal 2011 Journal Article

The distributed wireless gathering problem

  • Vincenzo Bonifaci
  • Peter Korteweg
  • Alberto Marchetti-Spaccamela
  • Leen Stougie

We address the problem of data gathering in a wireless network using multi-hop communication; our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performance of distributed algorithms, which do not use any form of local coordination, and we focus on the objective of minimizing average flow times of data packets. We prove a lower bound of Ω ( n ) on the expected competitive ratio of any acknowledgment-based distributed algorithm minimizing the maximum flow time, where n is the number of nodes of the network. Next, we consider a distributed algorithm which sends packets over shortest paths, and we use resource augmentation to analyze its performance when the objective is to minimize the average flow time. If interferences are modeled as in Bar-Yehuda et al. [R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and Systems Sciences 45 (1) (1992) 104–126] we prove that the algorithm is ( 1 + ϵ ) -competitive, when the algorithm sends packets a factor O ( log ( δ / ϵ ) log Δ ) faster than the optimal off-line solution; here δ is the radius of the network and Δ the maximum degree. We finally extend this result to a more complex interference model.

Details DOI

MFCS Conference 2010 Conference Paper

Scheduling Real-Time Mixed-Criticality Jobs

  • Sanjoy K. Baruah
  • Vincenzo Bonifaci
  • Gianlorenzo D'Angelo
  • Haohan Li
  • Alberto Marchetti-Spaccamela
  • Nicole Megow
  • Leen Stougie

Abstract Many safety-critical embedded systems are subject to certification requirements; some systems may be required to meet multiple sets of certification requirements, from different certification authorities. Certification requirements in such “mixed-criticality” systems give rise to interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In this paper, we study a formal model for representing such mixed-criticality workloads. We demonstrate first the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements, even for systems subject to two sets of certification requirements. Then we quantify, via the metric of processor speedup factor, the effectiveness of two techniques, reservation-based scheduling and priority-based scheduling, that are widely used in scheduling such mixed-criticality systems, showing that the latter of the two is superior to the former. We also show that the speedup factors are tight for these two techniques.

Details

TCS Journal 2009 Journal Article

Data aggregation in sensor networks: Balancing communication and delay costs

  • Peter Korteweg
  • Alberto Marchetti-Spaccamela
  • Leen Stougie
  • Andrea Vitaletti

In a sensor network the sensors, or nodes, obtain data and have to communicate these data to a central node. Because sensors are battery powered they are highly energy constrained. Data aggregation can be used to combine data of several sensors into a single message, thus reducing sensor communication costs at the expense of message delays. Thus, the main problem of data aggregation is to balance the communication and delay costs. In this paper we study the data aggregation problem as a bicriteria optimization problem; the objectives we consider are to minimize maximum energy consumption of a sensor and a function of the maximum latency costs of a message. We consider distributed algorithms under a synchronous time model, under an asynchronous time model, and under an almost synchronous time model, where sensor clocks are synchronized up to a small drift. We use competitive analysis to assess the quality of the algorithms.

Details DOI

TCS Journal 2004 Journal Article

Semi-clairvoyant scheduling

  • Luca Becchetti
  • Stefano Leonardi
  • Alberto Marchetti-Spaccamela
  • Kirk Pruhs

In (Symp. Discrete Algorithms 2002, p. 762) it was shown that the obvious semi-clairvoyant generalization of the Shortest Processing Time is O(1)-competitive with respect to average stretch on a single machine. In (Symp. Discrete Algorithms 2002, p. 762) it was left as an open question whether it was possible for a semi-clairvoyant algorithm to be O(1)-competitive with respect to average flow time on a single machine. Here we settle this open question by giving a semi-clairvoyant algorithm that is O(1)-competitive with respect to average flow time on a single machine. We also show a semi-clairvoyant algorithm on parallel machines that achieves up to constant factors the best known competitive ratio for clairvoyant on-line algorithms. In some sense one might conclude from this that the QoS achievable by semi-clairvoyant algorithms is competitive with clairvoyant algorithms. We finally show that, in contrast to the clairvoyant case, no semi-clairvoyant algorithm can be simultaneously O(1)-competitive with respect to average stretch and O(1)-competitive with respect to average flow time.

Details DOI

FOCS Conference 2003 Conference Paper

Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm

  • Luca Becchetti
  • Stefano Leonardi 0001
  • Alberto Marchetti-Spaccamela
  • Guido Schäfer
  • Tjark Vredeveld

In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng (2001) to explain the behavior of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2/sup K/] We use a partial bit randomization model, where the initial processing times are smoothened by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2/sup k///spl sigma/)/sup 3/ + (2/sup k///spl sigma/)/sup 2/2/sup K-k/), where /spl sigma/ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of O(2/sup K-k/) if /spl sigma/ = /spl Theta/(2/sup k/). We also prove an /spl Omega/(2/sup K-k/) lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, we give a higher lower bound of /spl Omega/(2/sup K/). A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.

Details

TCS Journal 2002 Journal Article

Approximation algorithms for routing and call scheduling in all-optical chains and rings

  • Luca Becchetti
  • Miriam Di Ianni
  • Alberto Marchetti-Spaccamela

We study the problem of routing and scheduling requests of limited durations in an all-optical network. The task is servicing the requests, assigning each of them a starting time and a wavelength, with restrictions on the number of available wavelengths. The goal is minimizing the overall time needed to serve all requests. We propose constant approximation algorithms for both ring and chain networks. In doing this, we also propose a polynomial-time approximation scheme for the problem of routing weighted calls on a directed ring with minimum load.

Details DOI

TCS Journal 2001 Journal Article

Dynamic algorithms for classes of constraint satisfaction problems

  • Daniele Frigioni
  • Alberto Marchetti-Spaccamela
  • Umberto Nanni

Many fundamental tasks in artificial intelligence and in combinatorial optimization can be formulated as a Constraint Satisfaction Problem (CSP). It is the problem of finding an assignment of values for a set of variables, each defined on a finite domain of feasible values, subject to a given collection of constraints. Each constraint is defined over a set of variables and specifies the allowed combinations of values as a collection of tuples. In general, the problem of finding a solution to a CSP is NP-complete, but in some cases it has shown to be polynomially solvable. We consider the dynamic version of some polynomially solvable constraint satisfaction problems, and present solutions that are better than recomputing everything from scratch after each update. The updates we consider are either restrictions, i. e. , deletions of values from existing constraints and introduction of new constraints, or relaxations, i. e. , insertions of values or deletions of constraints.

Details DOI

TCS Journal 1999 Journal Article

Foreword

  • Pierpaolo Degano
  • Roberto Gorrieri
  • Alberto Marchetti-Spaccamela
Details DOI

MFCS Conference 1995 Invited Paper

The Complexity of Interval Routing on Random Graphs

  • Michele Flammini
  • Jan van Leeuwen
  • Alberto Marchetti-Spaccamela

Abstract Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k -interval routing schemes ( k -IRS), nodes assign up to k intervals to each incident link. A message is routed over a link if its destination belongs to one of the intervals of the link. We give some results for the necessary value of k in order to achieve shortest path routing. Even though for very structured networks low values of k suffice, we show that for ‘general graphs’ interval routing cannot significantly reduce the space-requirements for shortest path routing. In particular, for any δ >0, there exist classes of random graphs G n, p for all n sufficiently large such that with high probability an optimal k -IRS for a graph G ∈ G n, p requires k = Ω ( n 1−δ ).

Details

TCS Journal 1993 Journal Article

Dynamic algorithms for shortest paths in planar graphs

  • Esteban Feuerstein
  • Alberto Marchetti-Spaccamela

We propose data structures for maintaining shortest paths in planar graphs in which the weight of an edge is modified. Our data structures allow us to compute, after an update, the shortest-path tree rooted at an arbitrary query node in time O(nlog logn) and to perform an update in O((logn)3). Our data structure can be applied also to the problem of maintaining the maximum flow problem in an s–t planar network. As far as the all-pairs shortest-path problem is concerned, we are interested in computing the shortest distances between q pairs of nodes. We show how to obtain an o(n 2) algorithm for computing the shortest path between q pairs of nodes whenever q = o(n 2). We also consider the dynamic version of the problem in which we allow the modification of the weight of an edge.

Details DOI

TCS Journal 1993 Journal Article

The weighted list update problem and the lazy adversary

  • Fabrizio d'Amore
  • Alberto Marchetti-Spaccamela
  • Umberto Nanni

The list update problem consists in maintaining a dictionary as an unsorted linear list. Any request specifies an item to be found by sequential scanning through the list. After an item has been found, the list may be rearranged in order to reduce the cost of processing a sequence of requests. Several kinds of adversaries can be considered to analyze the behavior of heuristics for this problem. The move-to-front (MTF) heuristic is 2-competitive against a strong adversary, matching the deterministic lower bound for this problem [Sleator and Tarjan (1985)]. But, for this problem, moving elements does not help the adversary. A lazy adversary has the limitation that he can use only a static arrangement of the list to process (off-line) the sequence of requests: still, no algorithm can be better than 2-competitive against the lazy adversary [Bentley and McGeogh (1985)]. In this paper we consider the weighted list update problem (WLUP), where the cost of accessing an item depends on the item itself. It is shown that MTF is not competitive by any constant factor for this problem against a lazy adversary. Two heuristics, based on the MTF strategy, are presented for WLUP: random move-to-front is randomized and uses biased coins; counting move-to-front is deterministic, and replaces coins by counters. Both are shown to be 2-competitive against a lazy adversary. This is optimal for the deterministic case. We apply this approach for searching items in a tree, proving that any c-competitive heuristic for the weighted list update problem provides a c-competitive heuristic for the tree update problem.

Details DOI

STOC Conference 1984 Conference Paper

On Finding the Exact Solution of a Zero-One Knapsack Problem

  • Andrew V. Goldberg
  • Alberto Marchetti-Spaccamela

Given a 0-1 knapsack problem with input drawn from a certain probability distribution, we show that for every ε > 0, there is a self-checking polynomial-time algorithm that finds an optimal solution with probability at least 1 -ε. We also prove some upper and lower bounds on random variables related to the problem.

Details

TCS Journal 1983 Journal Article

The largest tree in a random graph

  • Alberto Marchetti-Spaccamela
  • Marco Protasi

In this paper we study the problem of finding the largest tree in a random graph. First of all, we estimate the size of the largest tree almost surely. Then we propose two approximate greedy algorithms. Both algorithms achieve a solution whose value is one half of the value of the optimal solution, with high probability.

Details DOI
v2026.09.13