Publications
Latest
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 ]
Journal Publications
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 ]
Refereed Conference Publications
(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 ]
Book Chapters
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 ]
Ph.D. Thesis
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
What is now proved was once only imagin’d / Quello che oggi è dimostrato fu un tempo solo immaginato.
Proverbs of Hell / Proverbi infernali