Homepage

Vincenzo Bonifaci

Please notice that I moved to IASI-CNR, Rome, Italy.

Research Interests

I am interested in algorithms and complexity, and particularly in the following areas.

Approximation and online algorithms
Routing and scheduling problems
Algorithmic game theory

Publications

Recent

Physarum Can Compute Shortest Paths
with K. Mehlhorn, G. Varma
SODA 2012 (talk)
Faster Algorithms for Rounding Fractional Spanning Trees
with J. Mestre
Submitted

Journal Publications

Scheduling Real-Time Mixed-Criticality Jobs
with S. Baruah, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, L. Stougie
IEEE Transactions on Computers, accepted for publication
Preliminary version in MFCS 2010
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
with A. Marchetti-Spaccamela
Algorithmica, accepted for publication
Preliminary version in ESA 2010
Co-winner of the ESA Best Paper Award
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
with A. Marchetti-Spaccamela, S. Stiller
Algorithmica, 62(3-4):1034-1049, 2012
Preliminary version in ESA 2008
Minimizing Flow Time in the Wireless Gathering Problem
with P. Korteweg, A. Marchetti-Spaccamela, L. Stougie
ACM Transactions on Algorithms, 7(3):33
Preliminary version in STACS 2008, ALGOSENSORS 2008
The Distributed Wireless Gathering Problem
with P. Korteweg, A. Marchetti-Spaccamela, L. Stougie
Theoretical Computer Science, 412(8-10):633-641, 2011
Improved Multiprocessor Global Schedulability Analysis
with S.K. Baruah, A. Marchetti-Spaccamela, S. Stiller
Real-Time Systems, 46(1):3--24, 2010
Budgeted Matching and Budgeted Matroid Intersection via the Gasoline Puzzle
with A. Berger, F. Grandoni, G. Schäfer
Mathematical Programming, 128(1--2):355--372, 2011
Preliminary version in IPCO 2008
Stackelberg Routing in Arbitrary Networks
with T. Harks, G. Schäfer
Mathematics of Operations Research, 35(2):1--17, 2010
Preliminary version in WINE 2008
An Approximation Algorithm for the Wireless Gathering Problem
with P. Korteweg, A. Marchetti-Spaccamela, L. Stougie
Operations Research Letters, 36(5):605--608, 2008
Preliminary version in SWAT 2006
The Complexity of Uniform Nash Equilibria and Related Regular Subgraph Problems
with U. Di Iorio, L. Laura
Theoretical Computer Science, 401(1--3):144--152, 2008
Preliminary version in WINE 2005
The Online Prize-Collecting Traveling Salesman Problem
with G. Ausiello, L. Laura
Information Processing Letters, 107(6):199--204, 2008
On the Power of Lookahead in Online Server Routing Problems
with L. Allulli, G. Ausiello, L. Laura
Theoretical Computer Science, 408(2--3):116--128, 2008
Online k-Server Routing Problems
with L. Stougie
Theory of Computing Systems, 45(3):470--485, 2009
Preliminary version in WAOA 2006
The Online Asymmetric Traveling Salesman Problem
with G. Ausiello, L. Laura
Journal of Discrete Algorithms, 6(2):290--298, 2008
Preliminary version in WADS 2005
An Adversarial Queueing Model for Online Server Routing
Theoretical Computer Science, 381(1--3):280--287, 2007
A Java-Based System for Building Animated Presentations over the Web
with C. Demetrescu, I. Finocchi, L. Laura
Science of Computer Programming, 53(1):37--49, 2004

In Refereed Proceedings (excluding those subsumed by journal publications above)

On the Efficiency of Restricted Tolls in Network Routing Games
with M. Salek, G. Schäfer
SAGT 2011
Mixed-Criticality Scheduling of Sporadic Task Systems
with S. Baruah, G. D'Angelo, A. Marchetti-Spaccamela, S. van der Ster, L. Stougie
ESA 2011
Algorithms and Complexity for Periodic Real-Time Scheduling
with H.-L. Chan, A. Marchetti-Spaccamela, N. Megow
SODA 2010

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

Teaching

Summer Semester 2010:
Algorithmic Game Theory (with Khaled Elbassioni and Angelina Vidali)

Recent Positions

November 2007 - September 2009:
Postdoc at University of L'Aquila and Sapienza University of Rome, Italy in the Algorithm Engineering group
January 2007 - October 2007:
Postdoc at TU Berlin in the Combinatorial Optimization and Graph Algorithms group

Education

November 2003 - January 2007:
Ph.D. student at Sapienza University of Rome, Italy and Technical University of Eindhoven, the Netherlands
November 1997 - March 2003:
Studies in Computer Engineering (Ingegneria Informatica) at Sapienza University of Rome