Papers by topic: [mechanism design] [online algorithms] [wireless networks] [parallel computation] [complexity and approximation] [graph drawing] [IP lookup] [knowledge representation]

Mechanism Design:

Pseudonyms in cost-sharing games.
Paolo Penna, Florian Schoppmann, Riccardo Silvestri, and Peter Widmayer.
WINE 2009.
Documents: slides ppt meta bibtex.
Private capacities in mechanism design.
Vincenzo Auletta, Paolo Penna, and Giuseppe Persiano.
MFCS 2009.
Documents: slides ppt meta bibtex.
Optimal collusion-resistant mechanisms with verification.
Paolo Penna and Carmine Ventre.
EC 2009.
Documents: slides ppt meta bibtex.
Alternatives to Truthfulness are Hard to Recognize.
Vincenzo Auletta, Paolo Penna, Giuseppe Persiano, and Carmine Ventre.
SAGT 2008.
Documents: meta bibtex.
Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions.
Paolo Penna and Carmine Ventre.
ESA 2008.
Documents: meta bibtex.
Strongly Polynomial-Time Truthful Mechanisms in One Shot.
Paolo Penna, Guido Proietti, and Peter Widmayer.
WINE 2006.
Documents: slides ppt meta bibtex.
Routing Selfish Unsplittable Traffic.
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano.
ACM Transactions on Algorithms, Number 3, Volume 4, 2007.
Journal version expanding the results in the spaa04 conference paper.
Documents: meta bibtex.
New Constructions of Mechanisms with Verification.
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano, and Carmine Ventre.
ICALP 2006.
Documents: slides ppt meta bibtex.
The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms.
Paolo Penna and Carmine Ventre.
STACS 2006.
Documents: slides ppt (by Carmine Ventre) meta bibtex.
Free-riders in Steiner tree cost-sharing games.
Paolo Penna and Carmine Ventre.
SIROCCO 2005.
Documents: slides ppt meta bibtex.
On Designing Truthful Mechanisms for Online Scheduling.
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano.
SIROCCO 2005.
Documents: slides ppt an errata to the conference version meta bibtex.
More Powerful and Simpler Cost-Sharing Methods.
Paolo Penna and Carmine Ventre.
WAOA 2004.
Documents: slides ppt (by Carmine Ventre) meta bibtex.
Truthful mechanisms for generalized utilitarian problems.
Giovanna Melideo, Paolo Penna, Guido Proietti, Roger Wattenhofer, and Peter Widmayer.
IFIP-TCS 2004.
Documents: slides pdf meta bibtex.
The Power of Verification for One-Parameter Agents.
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano.
Journal of Computer and System Sciences, 75(3):190-211, 2009.
Documents: meta bibtex.
Sharing the Cost of Multicast Transmissions in Wireless Networks.
Paolo Penna and Carmine Ventre.
SIROCCO 2004.
Documents: slides ppt (by Carmine Ventre) full version pdf meta bibtex.
How to Route and Tax Selfish Unsplittable Traffic.
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano.
SPAA 2004.
Documents: full version pdf meta bibtex.
Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines.
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano.
STACS 2004.
Documents: slides pdf meta bibtex.
On the approximability of the range assignment problem on radio networks in presence of selfish agents.
Christoph Ambuehl, Andrea Clementi, Paolo Penna, Gianluca Rossi, and Riccardo Silvestri.
Theoretical Computer Science 343: 27 - 41, 2005.
Documents: meta bibtex.

Online Algorithms:

An Equivalent Version of the Caccetta-Haeggkvist Conjecture in an Online Load Balancing Problem.
Angelo Monti, Paolo Penna, and Riccardo Silvestri.
WG 2007.
Documents: slides ppt meta bibtex.
On-line load balancing made simple: Greedy strikes back.
Pilu Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, and Walter Unger.
Journal of Discrete Algorithms 5:162-175, 2007.
Documents: slides pdf meta bibtex.
Online train disposition: to wait or not to wait?
Luzi Anderegg, Paolo Penna, and Peter Widmayer.
ATMOS 2002.
Documents: meta bibtex.
Online Algorithms for the Channel Assignment Problem in Cellular Networks.
P. Crescenzi, G. Gambosi, and P. Penna.
Discrete Applied Mathematics 137: 237 - 266, 2004.
Documents: meta bibtex.

Wireless Networks:

Interference Games in Wireless Networks.
Vincenzo Auletta, Luca Moscardelli, Paolo Penna, and Giuseppe Persiano.
WINE 2008.
Documents: meta bibtex.
Equilibria for Broadcast Range Assignment Games in Ad-Hoc Networks.
Pilu Crescenzi, Alessandro Lazzoni, Miriam Di Ianni, Paolo Penna, Gianluca Rossi, and Paola Vocca.
AD-HOC-NOW 2005.
Documents: slides pdf (by Pilu Crescenzi) meta bibtex.
Energy-Efficient Broadcasting in Ad-Hoc Networks: Combining MSTs with Shortest-Path Trees.
Paolo Penna and Carmine Ventre.
PE-WASUN 2004.
Documents: slides ppt and java applet (both by Carmine Ventre) meta bibtex.
On the Power Assignment Problem in Radio Networks.
Andrea Clementi, Paolo Penna, and Riccardo Silvestri.
Mobile Networks and Applications, 9(2): 125-140, 2004.
Journal version combining the results in APPROX 1999 and STACS 2000 papers.
Documents: paper pdf meta bibtex.
The Minimum Range Assignment Problem on Linear Radio Networks.
Andrea Clementi, Afonso Ferreira, Paolo Penna, Stephane Perennes, and Riccardo Silvestri.
Algorithmica 35(2):95-110, 2003.
Documents: slides pdf meta bibtex.
On the Approximation Ratio of the MST-based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks.
Andrea E.F. Clementi, Gurvan Huiban, Paolo Penna, Gianluca Rossi, and Yann C. Verhoeven.
WMAN 2003.
Documents: meta bibtex.
Some Recent Theoretical Advances and Open Questions on Energy Consumption in Ad-Hoc Wireless Networks.
Andrea E.F. Clementi, Gurvan Huiban, Paolo Penna, Gianluca Rossi, and Yann C. Verhoeven.
ARACNE 2003.
Documents: meta bibtex.
Topological design, routing and hand-over in satellite networks.
Afonso Ferreira, Jerome Galtier, and Paolo Penna.
Chapter in Handbook of Wireless Networks and Mobile Computing, Wiley-Interscience, 2002.
Documents: meta bibtex.
Complexity Links Between Matrix Multiplication, Klee's Measure and Call Access Control for Satellite Constellations.
Jerome Galtier and Paolo Penna.
Technical Report INRIA number 4166, 2001.
Documents: meta bibtex.
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs.
Andrea Clementi, Pilu Crescenzi, Paolo Penna, Gianluca Rossi, and Paola Vocca.
STACS 2001.
Documents: paper pdf full version pdf meta bibtex.

Parallel Computation:

Parallel Read Operations Without Memory Contention.
Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose D. P. Rolim.
ECCC TR00-053, July 2000.
Full version combining the results in the two papers below.
Documents: meta bibtex.
A Note on Parallel Read Operations on Large Public Databases.
Andrea Clementi, Giancarlo Bongiovanni, and Paolo Penna.
ARACNE 2000.
Documents: meta bibtex.
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines.
Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose D. P. Rolim.
STACS 1999.
Documents: meta bibtex.

Complexity and Approximation

Improving Customer Proximity to Railway Stations.
Evangelos Kranakis, Paolo Penna, Konrad Schlude, David S. Taylor, and Peter Widmayer.
CIAC 2003.
Documents: meta bibtex.
Partial Digest is hard to solve for erroneous input data.
Mark Cieliebak, Stephan Eidenbenz, and Paolo Penna.
Theoretical Computer Science 349(3): 361-381, 2005.
Documents: meta bibtex.
Server Placements, Roman Domination and other Dominating Set Variants.
Aris Pagourtzis, Paolo Penna, Konrad Schlude, Kathleen Steinhöfel, David Scot Taylor, Peter Widmayer.
IFIP-TCS 2002.
Documents: meta bibtex.
On the Complexity of Train Assignment Problems.
Thomas Erlebach, Martin Gantenbein, Daniel Hürlimann, Gabriele Neyer, Aris Pagourtzis, Paolo Penna, Konrad Schlude, Kathleen Steinhöfel, David Scot Taylor, and Peter Widmayer.
ISAAC 2001.
Documents: meta bibtex.
On Computing Ad-Hoc Selective Families.
Andrea Clementi, Pilu Crescenzi, Angelo Monti, Paolo Penna, and Riccardo Silvestri.
RANDOM 2001.
Documents: meta bibtex.

Graph Drawing:

Proximity Drawings in Polynomial Area and Volume.
Paolo Penna and Paola Vocca.
Computational Geometry: Theory and Applications, 9(2): 91-116, 2004.
Journal version combining the results in CCCG 1998 and GD 1998 papers.
Documents: meta bibtex.
On the Approximability of Two Tree Drawing Conventions.
Paolo Penna.
Information Processing Letters, 82(5): 237-242, 2002.
Documents: meta bibtex.
Strictly-upward drawings of ordered search trees.
Pierluigi Crescenzi and Paolo Penna.
Theoretical Computer Science, 203(1): 51-67, 1998.
Documents: meta bibtex.
Linear Area Upward Drawings of AVL Trees.
Pierluigi Crescenzi, Paolo Penna, and Adolfo Piperno.
Computational Geometry: Theory and Applications, 9(1-2): 25-42, 1998.
Documents: meta bibtex.
Minimum-Area h-v Drawings of Complete Binary Trees.
Pierluigi Crescenzi and Paolo Penna.
GD 1997.
Documents: meta bibtex.

IP Lookup:

XOR-based schemes for fast parallel IP lookups.
Giancarlo Bongiovanni and Paolo Penna.
Theory of Computing Systems 38(4): 481-501, 2005.
Documents: meta bibtex.

Knowledge Representation:

Succinct Representations of Model Based Belief Revision.
Paolo Penna.
STACS 2000.
Documents: meta bibtex.