Publications

Egalitarian roommate allocations: Complexity and stability
V. Bonifaci and H. Rivera Dallorto
Theoretical Computer Science, 1026:115009, 2025
[ doi ]

On a voter model with context-dependent opinion adoption
L. Becchetti, V. Bonifaci, E. Cruciani, and F. Pasquale
IJCAI 2023
[ doi ]

Physarum-inspired multi-commodity flow dynamics
V. Bonifaci, E. Facca, F. Folz, A. Karrenbauer, P. Kolev, K. Mehlhorn, G. Morigi, G. Shahkarami, and Q. Vermande
Theoretical Computer Science, 920:1—​20, 2022
[ doi ]

An entropic gradient structure in the network dynamics of a slime mold
V. Bonifaci
Symmetry, 13(8), 2021
[ doi ]

A Laplacian approach to L1-norm minimization
V. Bonifaci
Computational Optimization and Applications, 79:441—​469, 2021
[ doi ]

Algorithms for hierarchical and semi-partitioned parallel scheduling
V. Bonifaci, G. D’Angelo, and A. Marchetti-Spaccamela
Journal of Computer and System Sciences, 120:116—​136, 2021
Preliminary version in IPDPS 2017
[ doi ]

On the convergence time of a natural dynamics for linear programming
V. Bonifaci
Algorithmica, 82(2):300—​315, 2019
[ doi ]

A generalized parallel task model for recurrent real-time processes
V. Bonifaci, A. Wiese, S.K. Baruah, A. Marchetti-Spaccamela, S. Stiller, and L. Stougie
ACM Transactions on Parallel Computing, 6(1):3:1—​3:40, 2019
Preliminary version in RTSS 2012, ECRTS 2013, ECRTS 2015
[ doi ]

Two results on slime mold computations
R. Becker, V. Bonifaci, A. Karrenbauer, P. Kolev, and K. Mehlhorn
Theoretical Computer Science, 773:79—​106, 2019
[ doi ]

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors
S.K. Baruah, V. Bonifaci, R. Bruni, and A. Marchetti-Spaccamela
Journal of Scheduling, 22(2):195—​209, 2019
Preliminary version in ECRTS 2016
[ doi ]

A revised model of fluid transport optimization in Physarum polycephalum
V. Bonifaci
Journal of Mathematical Biology, 74:567—​581, 2017
[ doi ]

Exact response time analysis for fixed priority memory-processor co-scheduling
A. Melani, M. Bertogna, R.I. Davis, V. Bonifaci, A. Marchetti-Spaccamela, and G. Buttazzo
IEEE Transactions on Computers, 66(4):631—​646, 2017
Preliminary version in RTNS 2015
[ doi ]

Schedulability analysis of conditional parallel task graphs in multicore systems
A. Melani, M. Bertogna, V. Bonifaci, A. Marchetti-Spaccamela, and G. Buttazzo
IEEE Transactions on Computers, 66(2):339—​353, 2017
Preliminary version in ECRTS 2015
[ doi ]

Preemptive uniprocessor scheduling of mixed-criticality sporadic task systems
S.K. Baruah, V. Bonifaci, G. D’Angelo, H. Li, A. Marchetti-Spaccamela, S. van der Ster, and L. Stougie
J. ACM, 62(2):14, 2015
Preliminary version in ECRTS 2012, ESA 2011
[ doi ]

Physarum can compute shortest paths: A short proof
V. Bonifaci
Information Processing Letters, 113(1—​2):4—​7, 2013
[ doi ]

Partitioned EDF scheduling on a few types of unrelated multiprocessors
A. Wiese, V. Bonifaci, and S. Baruah
Real-Time Systems, 49(2):219—​238, 2013
[ doi ]

Physarum can compute shortest paths
V. Bonifaci, K. Mehlhorn, and G. Varma
Journal of Theoretical Biology, 309:121—​133, 2012
Preliminary version in SODA 2012
[ doi ]

Algorithms and complexity for periodic real-time scheduling
V. Bonifaci, H.-L. Chan, A. Marchetti-Spaccamela, and N. Megow
ACM Transactions on Algorithms, 9(1):6, 2012
Preliminary version in SODA 2010
[ doi ]

Scheduling real-time mixed-criticality jobs
S.K. Baruah, V. Bonifaci, G. D’Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, and L. Stougie
IEEE Transactions on Computers, 61(8):1140—​1152, 2011
Preliminary version in MFCS 2010
[ doi ]

Feasibility analysis of sporadic real-time multiprocessor task systems
V. Bonifaci and A. Marchetti-Spaccamela
Algorithmica, 63(4):763—​780, 2012
Preliminary version in ESA 2010
Co-winner of the ESA Best Paper Award
[ doi ]

A constant-approximate feasibility test for multiprocessor real-time scheduling
V. Bonifaci, A. Marchetti-Spaccamela, and S. Stiller
Algorithmica, 62(3—​4):1034—​1049, 2012
Preliminary version in ESA 2008
[ doi ]

Minimizing flow time in the wireless gathering problem
V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie
ACM Transactions on Algorithms, 7(3):33, 2011
Preliminary version in STACS 2008, ALGOSENSORS 2008
[ doi ]

The distributed wireless gathering problem
V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie
Theoretical Computer Science, 412(8-10):633—​641, 2011
Preliminary version in AAIM 2008
[ doi ]

Improved multiprocessor global schedulability analysis
S.K. Baruah, V. Bonifaci, A. Marchetti-Spaccamela, and S. Stiller
Real-Time Systems, 46(1):3—​24, 2010
Preliminary version in ECRTS 2009
[ doi ]

Budgeted matching and budgeted matroid intersection via the gasoline puzzle
A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer
Mathematical Programming, 128(1-2):355—​372, 2011
Preliminary version in IPCO 2008
[ doi ]

Stackelberg routing in arbitrary networks
V. Bonifaci, T. Harks, and G. Schäfer
Mathematics of Operations Research, 35(2):1—​17, 2010
Preliminary version in WINE 2008
[ doi ]

An approximation algorithm for the wireless gathering problem
V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie
Operations Research Letters, 36(5):605—​608, 2008
Preliminary version in SWAT 2006
[ doi ]

The complexity of uniform Nash equilibria and related regular subgraph problems
V. Bonifaci, U. Di Iorio, and L. Laura
Theoretical Computer Science, 401(1—​3):144—​152, 2008
Preliminary version in WINE 2005, FCT 2005
[ doi ]

The on-line prize-collecting traveling salesman problem
G. Ausiello, V. Bonifaci, and L. Laura
Information Processing Letters, 107(6):199—​204, 2008
[ doi ]

On the power of lookahead in on-line server routing problems
L. Allulli, G. Ausiello, V. Bonifaci, and L. Laura
Theoretical Computer Science, 408(2—​3):116—​128, 2008
[ doi ]

Online k-server routing problems
V. Bonifaci and L. Stougie
Theory of Computing Systems, 45(3):470—​485, 2009
Preliminary version in WAOA 2006
[ doi ]

The on-line asymmetric traveling salesman problem
G. Ausiello, V. Bonifaci, and L. Laura
Journal of Discrete Algorithms, 6(2):290—​298, 2008
Preliminary version in WADS 2005
[ doi ]

An adversarial queueing model for online server routing
V. Bonifaci
Theoretical Computer Science, 381(1—​3):280—​287, 2007
[ doi ]

A Java-based system for building animated presentations over the Web
V. Bonifaci, C. Demetrescu, I. Finocchi, and L. Laura
Science of Computer Programming, 53(1):37—​49, 2004
[ doi ]

(note: conference publications that were later subsumed by journal publications are omitted)

Pooling or sampling: Collective dynamics for electrical flow estimation
L. Becchetti, V. Bonifaci, and E. Natale
AAMAS 2018

A scheduling model inspired by control theory
S. Baruah, V. Bonifaci, A. Marchetti-Spaccamela, and V. Verdugo
RTNS 2017
[ doi ]

Multiprocessor real-time scheduling with hierarchical processor affinities
V. Bonifaci, B. Brandenburg, G. D’Angelo, and A. Marchetti-Spaccamela
ECRTS 2016
[ doi ]

Polynomial-time exact schedulability tests for harmonic real-time tasks
V. Bonifaci, A. Marchetti-Spaccamela, N. Megow, and A. Wiese
IEEE RTSS 2013
[ doi ]

Physarum can compute shortest paths: Convergence proofs and complexity bounds
L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, and K. Mehlhorn
ICALP 2013
[ doi ]

On the efficiency of restricted tolls in network routing games
V. Bonifaci, M. Salek, and G. Schäfer
SAGT 2011
[ doi ]

Algorithms for auctions and games
V. Bonifaci and S. Leonardi
In G. Ausiello and R. Petreschi, editors, The Power of Algorithms, chapter 9, pages 207—​234. Springer, 2013
[ doi ]

Complexity and approximation in reoptimization
G. Ausiello, V. Bonifaci, and B. Escoffier
In S.B. Cooper and A. Sorbi, editors, Computability in Context: Computation and Logic in the Real World, chapter 4, pages 101—​129. World Scientific, 2011
[ doi ]

Data gathering in wireless networks
V. Bonifaci, R. Klasing, P. Korteweg, L. Stougie, and A. Marchetti-Spaccamela
In A. Koster and X. Muñoz, editors, Graphs and Algorithms in Communication Networks, chapter 14, pages 357—​377. Springer, 2009
[ doi ]

Prize-collecting traveling salesman and related problems
G. Ausiello, V. Bonifaci, S. Leonardi, and A. Marchetti-Spaccamela
In T.F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, chapter 40. CRC Press, 2007
[ doi ]

Models and Algorithms for Online Server Routing
Sapienza Università di Roma & Technische Universiteit Eindhoven, 2007
Co-winner of the 2007 Italian Chapter EATCS Award for best Ph.D. thesis in Theoretical Computer Science