# 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