Publications

This is a selected list of recent publications by our group. More publications can be found on dblp or here.

  • Fabrizio Grandoni, Thomas Rothvoß: Pricing on Paths: A PTAS for the Highway Problem. SIAM J. Comput. 45(2): 216-231, 2016
  • Marek Adamczyk, Fabrizio Grandoni, Joydeep Mukherjee: Improved Approximation Algorithms for Stochastic Matching. ESA 2015: 1-12
  • Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, Guido Proietti: Improved Purely Additive Fault-Tolerant Spanners. ESA 2015: 167-178
  • Parinya Chalermsook, Fabrizio Grandoni, and Bundit Laekhanukit. On Survivable Set Connectivity. SODA 2015: 25-36.
  • Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams: Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. SODA 2015: 1681-1697
  • Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli: A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem. ESA 2015: 853-864
  • Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli: On the Hardest Problem Formulations for the 0/1 0 / 1 Lasserre Hierarchy. ICALP (1) 2015: 872-885
  • Fabrizio Grandoni, R. Ravi, Mohit Singh, Rico Zenklusen:
    New approaches to multi-objective optimization. Math. Program. 146(1-2): 525-554 (2014)
  • Fabrizio Grandoni, Piotr Krysta, Stefano Leonardi, Carmine Ventre: Utilitarian Mechanism Design for Multiobjective Optimization. SIAM J. Comput. 43(4): 1263-1290 (2014)
  • Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Andreas Wiese: A Mazing 2+∊ Approximation for Unsplittable Flow on a Path. SODA 2014: 26-41
  • Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità: Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM 60(1): 6 (2013)
  • Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh: Set Covering with Our Eyes Closed. SIAM J. Comput. 42(3): 808-830 (2013)
  • Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
    Tight Kernel Bounds for Problems on Graphs with Small Degeneracy – (Extended Abstract). ESA 2013: 361-372
  • Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Andreas Wiese: Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path. IPCO 2013: 25-36
  • Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli:
    How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013: 342-351
  • F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankoswki, and M. Singh. SIAM Journal on Computing 42(3): 808-830, 2013.
  • M. Cygan, F. Grandoni and M. Mastrolilli. How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013.
  • M. Cygan, M. Pilipczuk and M. Pilipczuk. Known algorithms for Edge Clique Cover are probably optimal. SODA 2013.
  • P. Chalermsook, B. Laekhanukit and D. Nanongkai. Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension, and More. SODA 2013.
  • Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha:
    On Pairwise Spanners. STACS 2013: 209-220
  • Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski: A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. ESA 2012: 349-360
  • Fabrizio Grandoni: On Min-Power Steiner Tree. ESA 2012: 527-538
  • Fabrizio Grandoni, Virginia Vassilevska Williams:
    Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. FOCS 2012: 748-757
  • Bundit Laekhanukit, Adrian Vetta, Gordon T. Wilfong:
    Routing Regardless of Network Stability. ESA 2012: 719-730
  • Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh:
    A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. ICALP (1) 2012: 606-616
  • Marek Cygan, Guy Kortsarz, Zeev Nutov: Steiner Forest Orientation Problems. ESA 2012: 361-372
  • Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller:
    LP Rounding for k-Centers with Non-uniform Hard Capacities. FOCS 2012: 273-282
  • Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk: Designing FPT Algorithms for Cut Problems Using Randomized Contractions. FOCS 2012: 460-469
  • Marek Cygan, Harold N. Gabow, Piotr Sankowski:
    Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter and Matchings. FOCS 2012: 531-540

  • Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2012: 230-241
  • Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström: Clique Cover and Graph Separation: New Incompressibility Results. ICALP (1) 2012: 254-265
  • Marek Cygan: Deterministic Parameterized Connected Vertex Cover. SWAT 2012: 95-106. Best student paper award.
  • Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
    On Group Feedback Vertex Set Parameterized by the Size of the Cutset. WG 2012: 194-205. Best student paper award.
  • Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, Arash Rafiey: Approximation of Minimum Cost Homomorphisms. ESA 2012: 587-598