Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Euiwoong Lee and Pasin Manurangsi. Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lee_et_al:LIPIcs.ITCS.2024.71, author = {Lee, Euiwoong and Manurangsi, Pasin}, title = {{Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {71:1--71:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.71}, URN = {urn:nbn:de:0030-drops-195996}, doi = {10.4230/LIPIcs.ITCS.2024.71}, annote = {Keywords: Hardness of Approximation, Bounded Degree, Constraint Satisfaction Problems, Independent Set} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, and Grigory Reznikov. Minimum Common String Partition: Exact Algorithms. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cygan_et_al:LIPIcs.ESA.2021.35, author = {Cygan, Marek and Kulikov, Alexander S. and Mihajlin, Ivan and Nikolaev, Maksim and Reznikov, Grigory}, title = {{Minimum Common String Partition: Exact Algorithms}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {35:1--35:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.35}, URN = {urn:nbn:de:0030-drops-146167}, doi = {10.4230/LIPIcs.ESA.2021.35}, annote = {Keywords: similarity measure, string distance, exact algorithms, upper bounds, lower bounds} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{axiotis_et_al:LIPIcs.ICALP.2019.19, author = {Axiotis, Kyriakos and Tzamos, Christos}, title = {{Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.19}, URN = {urn:nbn:de:0030-drops-105952}, doi = {10.4230/LIPIcs.ICALP.2019.19}, annote = {Keywords: Knapsack, Fine-Grained Complexity, Dynamic Programming} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online Facility Location with Deletions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cygan_et_al:LIPIcs.ESA.2018.21, author = {Cygan, Marek and Czumaj, Artur and Mucha, Marcin and Sankowski, Piotr}, title = {{Online Facility Location with Deletions}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {21:1--21:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.21}, URN = {urn:nbn:de:0030-drops-94843}, doi = {10.4230/LIPIcs.ESA.2018.21}, annote = {Keywords: online algorithms, facility location, fully-dynamic online algorithms} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP Tours Using Dynamic Programming over Tree Decompositions. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{cygan_et_al:LIPIcs.ESA.2017.30, author = {Cygan, Marek and Kowalik, Lukasz and Socala, Arkadiusz}, title = {{Improving TSP Tours Using Dynamic Programming over Tree Decompositions}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.30}, URN = {urn:nbn:de:0030-drops-78539}, doi = {10.4230/LIPIcs.ESA.2017.30}, annote = {Keywords: TSP, treewidth, local search, XP algorithm, hardness in P} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (min,+)-Convolution. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{cygan_et_al:LIPIcs.ICALP.2017.22, author = {Cygan, Marek and Mucha, Marcin and Wegrzycki, Karol and Wlodarczyk, Michal}, title = {{On Problems Equivalent to (min,+)-Convolution}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.22}, URN = {urn:nbn:de:0030-drops-74216}, doi = {10.4230/LIPIcs.ICALP.2017.22}, annote = {Keywords: fine-grained complexity, knapsack, conditional lower bounds, (min,+)-convolution, subquadratic equivalence} }
Published in: Dagstuhl Reports, Volume 7, Issue 1 (2017)
Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlström. Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). In Dagstuhl Reports, Volume 7, Issue 1, pp. 103-128, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{cygan_et_al:DagRep.7.1.103, author = {Cygan, Marek and Fomin, Fedor V. and Hermelin, Danny and Wahlstr\"{o}m, Magnus}, title = {{Randomization in Parameterized Complexity (Dagstuhl Seminar 17041)}}, pages = {103--128}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {1}, editor = {Cygan, Marek and Fomin, Fedor V. and Hermelin, Danny and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.1.103}, URN = {urn:nbn:de:0030-drops-72479}, doi = {10.4230/DagRep.7.1.103}, annote = {Keywords: fixed-parameter tractability, intractability, parameterized complexity, randomness} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bliznets_et_al:LIPIcs.APPROX-RANDOM.2016.3, author = {Bliznets, Ivan and Cygan, Marek and Komosa, Pawel and Pilipczuk, Michal}, title = {{Hardness of Approximation for H-Free Edge Modification Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {3:1--3:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.3}, URN = {urn:nbn:de:0030-drops-66260}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.3}, annote = {Keywords: hardness of approximation, parameterized complexity, kernelization, edge modification problems} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Lower Bounds for Approximation Schemes for Closest String. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 12:1-12:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{cygan_et_al:LIPIcs.SWAT.2016.12, author = {Cygan, Marek and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket}, title = {{Lower Bounds for Approximation Schemes for Closest String}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {12:1--12:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.12}, URN = {urn:nbn:de:0030-drops-60232}, doi = {10.4230/LIPIcs.SWAT.2016.12}, annote = {Keywords: closest string, PTAS, efficient PTAS} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Marek Cygan and Tomasz Kociumaka. Approximating Upper Degree-Constrained Partial Orientations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 212-224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{cygan_et_al:LIPIcs.APPROX-RANDOM.2015.212, author = {Cygan, Marek and Kociumaka, Tomasz}, title = {{Approximating Upper Degree-Constrained Partial Orientations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {212--224}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.212}, URN = {urn:nbn:de:0030-drops-53040}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.212}, annote = {Keywords: graph orientations, degree-constrained orientations, approximation algorithm, local search} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Marek Cygan and Tomasz Kociumaka. Constant Factor Approximation for Capacitated k-Center with Outliers. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 251-262, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{cygan_et_al:LIPIcs.STACS.2014.251, author = {Cygan, Marek and Kociumaka, Tomasz}, title = {{Constant Factor Approximation for Capacitated k-Center with Outliers}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {251--262}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.251}, URN = {urn:nbn:de:0030-drops-44625}, doi = {10.4230/LIPIcs.STACS.2014.251}, annote = {Keywords: approximation algorithms, k-center, capacities, outliers, LP rounding} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha. On Pairwise Spanners. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 209-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{cygan_et_al:LIPIcs.STACS.2013.209, author = {Cygan, Marek and Grandoni, Fabrizio and Kavitha, Telikepalli}, title = {{On Pairwise Spanners}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {209--220}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.209}, URN = {urn:nbn:de:0030-drops-39353}, doi = {10.4230/LIPIcs.STACS.2013.209}, annote = {Keywords: Undirected graphs, shortest paths, additive spanners, distance preservers} }
Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, and Piotr Sankowski. Approximation Algorithms for Union and Intersection Covering Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 28-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{cygan_et_al:LIPIcs.FSTTCS.2011.28, author = {Cygan, Marek and Grandoni, Fabrizio and Leonardi, Stefano and Mucha, Marcin and Pilipczuk, Marcin and Sankowski, Piotr}, title = {{Approximation Algorithms for Union and Intersection Covering Problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {28--40}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.28}, URN = {urn:nbn:de:0030-drops-33213}, doi = {10.4230/LIPIcs.FSTTCS.2011.28}, annote = {Keywords: Approximation algorithms, Partial covering problems} }
Feedback for Dagstuhl Publishing