Selected Publications


Marek Cygan, Fabrizio Grandoni and Monaldo Mastrolilli. How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013

Marek Cygan, Marcin Pilipczuk and Michal 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

Non-Redistributive Second Welfare Theorems, B. Laekhanukit, G. Naves and A. Vetta WINE 2012

B. Laekhanukit, A. Vetta and G. Wilfong
Routing Regardless of Network Stability, ESA 2012.

B. Laekhanukit, S. Oveis Gharan and M. Singh
A Rounding by sampling approach to the minimum size k-arc connected subgraph problem, ICALP 2012.


Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, and Daniel Marx. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. In ICALP, 230-241, 2012.

Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michał Pilipzuk. Designing FPT algorithms for cut problems using randomized contractions. To appear in FOCS 2012.

Marek Cygan. Deterministic parameterized connected vertex cover. In SWAT, 95-106, 2012. Best student paper award.

Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of Baur-Strassen's theorem. To appear in FOCS 2012.

Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, and Piotr Sakowski. A path-decomposition theorem with applications to pricing and covering on trees. To appear in ESA 2012.

Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. To appear in FOCS 2012.

Marek Cygan, Guy Kortsarz, and Zeev Nutov. Steiner forest orientation problems. To appear in ESA 2012.

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlstrom. Clique cover and graph separation: New incompressibility results. In ICALP, 254-265, 2012.

Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk. On group feedback vertex set parameterized by the size of the cutset. To appear in WG 2012. Best student paper award.

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub O. Wojtaszczyk. Sitting closer to friends than enemies, revised. To appear in MFCS 2012.

Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. To appear in FOCS 2012.

Fabrizio Grandoni. On min-power Steiner tree. To appear in ESA 2012.

Approximation of Minimum Cost Homomorphisms. (Coauthors: P. Hell, M. Nevisi and A. Rafiey), in Proceedings of the 20th Annual European Symposium on Algorithms (ESA), 2012.

Competitive Ratio Approximation Schemes for Makespan Scheduling Problems. (Coauthors: A. Kurpisz, G. Stamoulis), in Proceedings of the 10th Workshop on Approximation and Online Algorithms, WAOA 2012.

Restricted Max-Min Fair Allocations with Inclusion-free Intervals. (Coauthor: G. Stamoulis), Proceedings of COCOON 2012.

The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem, Proceedings of LATIN'12, Latin American Symposium on Theoretical Informatics, 2012.

Constrained Matching Problems in Bipartite Graphs (Coauthor: G. Stamoulis), Proceedings of the International Symposium on Combinatorial Optimization, ISCO 2012.

Single Machine Scheduling with Scenarios (Coauthors: N. Mutsanas, and O. Svensson), accepted by Theoretical Computer Science, 2012.

Vertex Cover in Graphs with Locally Few Colors (Coauthor: F. Kuhn), to appear in Information and Computation (invited paper, special issue dedicated to the best papers of ICALP 2011), 2012.

On the approximation of minimum cost homomorphism to bipartite graphs (Coauthor: A. Rafiey), to appear in Discrete Applied Mathematics, 2012.

Vertex Cover in Graphs with Locally Few Colors (Coauthor: F. Kuhn), Proceedings of ICALP (1) 2011, pp. 498-509. Invited to the Special issue of Information and Computation.

Pavol Hell, Arash Rafiey: The Dichotomy of List Homomorphisms for Digraphs. SODA 2011: 1703-1713

Hardness of Approximating Flow and Job Shop Scheduling Problems (Coauthor: O. Svensson), Journal of the ACM 58(5): 20, 2011.

On the Approximability of Single Machine Scheduling with Precedence Constraints (Coauthors: C. Ambuehl, N. Mutsanas, and O. Svensson), Mathematics of Operations Research, November 2011, vol. 36, no. 4, 653-669 .

Inapproximability results for Maximum Edge Biclique, Optimal Linear Arrangement and Sparsest Cut (Coauthors: C. Ambuehl and O. Svensson), in SIAM Journal on Computing, 40(2): 567-596, 2011.

Minimizing the sum of weighted completion times in a concurrent open shop (Coauthors: M. Queyranne, A. S. Schulz, O. Svensson, N. A. Uhan), Operations Research Letters 38(5): 390-395, 2010.

Improved Bounds for Flow Shop Scheduling (Coauthor: O. Svensson), Proceedings of ICALP (1) 2009, pp. 677-688.

Mastrolilli and O. Svensson, (Acyclic) Job Shops are Hard to Approximate, Proceedings of the 49th AnnualI EEE Symposium on Foundations of ComputerScience (FOCS), pp. 583-592, 2008. [Full version]

M. Mastrolilli, N. Mutsanas and O. Svensson, Approximating Single Machine Scheduling with Scenarios. In: Ashish Goel, editor, 11th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX 2008, LNCS 5171, pp. 153-164. Springer-Verlag, 2008.

Christoph Ambühl, Monaldo Mastrolilli, and Ola Svensson. Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constraint scheduling. In Proceedings of FOCS 2007, 2007. [ bib | .html | .ps ]

Christoph Ambühl, Monaldo Mastrolilli, Nikos Mutsanas, and Ola Svensson. Scheduling with precedence constraints of low fractional dimension. In Proceedings of IPCO 2007, volume LNCS 4168, pages 28-39. Springer, 2007. [ bib | .pdf ]

Christoph Ambühl, Monaldo Mastrolilli, and Ola Svensson. Approximating precedence-constrained single machine scheduling by coloring. In Proceedings of the APPROX + RANDOM, volume LNCS 4110, pages 15-26. Springer, 2006. [ bib ]

Christoph Ambühl and Monaldo Mastrolilli. Single machine precedence constrained scheduling is a vertex cover problem. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), volume 4168 of 28-39. Springer, 2006.

Christoph Ambühl: An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. ICALP 2005: 1139-1150

Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko: A Linear Time Approximation Scheme for the Job Shop Scheduling Problem. RANDOM-APPROX 1999: 177-188

Klaus Jansen, Lorant Porkolab: Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks. SODA 1999: 490-498

Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko: Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. STOC 1999: 394-399

Klaus Jansen, Lorant Porkolab: Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. STOC 1999: 408-417