Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2024.27, author = {Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai}, title = {{Baby PIH: Parameterized Inapproximability of Min CSP}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.27}, URN = {urn:nbn:de:0030-drops-204237}, doi = {10.4230/LIPIcs.CCC.2024.27}, annote = {Keywords: Parameterized Inapproximability Hypothesis, Constraint Satisfaction Problems} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Jakub Komárek and Martin Koutecký. Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{komarek_et_al:LIPIcs.SEA.2024.18, author = {Kom\'{a}rek, Jakub and Kouteck\'{y}, Martin}, title = {{Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {18:1--18:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.18}, URN = {urn:nbn:de:0030-drops-203832}, doi = {10.4230/LIPIcs.SEA.2024.18}, annote = {Keywords: Linear programming, scaling, circuit imbalance measure} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Elie Abboud and Noga Ron-Zewi. Finer-Grained Reductions in Fine-Grained Hardness of Approximation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2024.7, author = {Abboud, Elie and Ron-Zewi, Noga}, title = {{Finer-Grained Reductions in Fine-Grained Hardness of Approximation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.7}, URN = {urn:nbn:de:0030-drops-201507}, doi = {10.4230/LIPIcs.ICALP.2024.7}, annote = {Keywords: Fine-grained complexity, conditional lower bound, fine-grained reduction, Approximation algorithms, Analysis of algorithms, Computational geometry, Computational and structural complexity theory} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Andreas Emil Feldmann and Michael Lampis. Parameterized Algorithms for Steiner Forest in Bounded Width Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{feldmann_et_al:LIPIcs.ICALP.2024.61, author = {Feldmann, Andreas Emil and Lampis, Michael}, title = {{Parameterized Algorithms for Steiner Forest in Bounded Width Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {61:1--61:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.61}, URN = {urn:nbn:de:0030-drops-202048}, doi = {10.4230/LIPIcs.ICALP.2024.61}, annote = {Keywords: Steiner Forest, Approximation Algorithms, FPT algorithms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67, author = {Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani}, title = {{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {67:1--67:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.67}, URN = {urn:nbn:de:0030-drops-202104}, doi = {10.4230/LIPIcs.ICALP.2024.67}, annote = {Keywords: Directed Steiner Network, Sub-exponential algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 88:1-88:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88, author = {Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya}, title = {{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {88:1--88:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.88}, URN = {urn:nbn:de:0030-drops-202318}, doi = {10.4230/LIPIcs.ICALP.2024.88}, annote = {Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Matej Lieskovský, Jiří Sgall, and Andreas Emil Feldmann. Approximation Algorithms and Lower Bounds for Graph Burning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lieskovsky_et_al:LIPIcs.APPROX/RANDOM.2023.9, author = {Lieskovsk\'{y}, Matej and Sgall, Ji\v{r}{\'\i} and Feldmann, Andreas Emil}, title = {{Approximation Algorithms and Lower Bounds for Graph Burning}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.9}, URN = {urn:nbn:de:0030-drops-188345}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.9}, annote = {Keywords: Graph Algorithms, approximation Algorithms, randomized Algorithms} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, and Anna Zych-Pawlewicz. On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{blum_et_al:LIPIcs.IPEC.2022.5, author = {Blum, Johannes and Disser, Yann and Feldmann, Andreas Emil and Gupta, Siddharth and Zych-Pawlewicz, Anna}, title = {{On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {5:1--5:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.5}, URN = {urn:nbn:de:0030-drops-173612}, doi = {10.4230/LIPIcs.IPEC.2022.5}, annote = {Keywords: sparse hitting set, fair vertex cover, highway dimension} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Andreas Emil Feldmann and Ashutosh Rai. On Extended Formulations For Parameterized Steiner Trees. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{feldmann_et_al:LIPIcs.IPEC.2021.18, author = {Feldmann, Andreas Emil and Rai, Ashutosh}, title = {{On Extended Formulations For Parameterized Steiner Trees}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.18}, URN = {urn:nbn:de:0030-drops-154010}, doi = {10.4230/LIPIcs.IPEC.2021.18}, annote = {Keywords: Steiner trees, integral linear program, extension complexity, fixed-parameter tractability} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Andreas Emil Feldmann, Davis Issac, and Ashutosh Rai. Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{feldmann_et_al:LIPIcs.IPEC.2020.17, author = {Feldmann, Andreas Emil and Issac, Davis and Rai, Ashutosh}, title = {{Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {17:1--17:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.17}, URN = {urn:nbn:de:0030-drops-133206}, doi = {10.4230/LIPIcs.IPEC.2020.17}, annote = {Keywords: Edge Clique Partition, fixed-parameter tractability, kernelization} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Andreas Emil Feldmann and David Saulpic. Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 46:1-46:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{feldmann_et_al:LIPIcs.ESA.2020.46, author = {Feldmann, Andreas Emil and Saulpic, David}, title = {{Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {46:1--46:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.46}, URN = {urn:nbn:de:0030-drops-129129}, doi = {10.4230/LIPIcs.ESA.2020.46}, annote = {Keywords: Approximation Scheme, Clustering, Highway Dimension} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz. Recoloring Interval Graphs with Limited Recourse Budget. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bosek_et_al:LIPIcs.SWAT.2020.17, author = {Bosek, Bart{\l}omiej and Disser, Yann and Feldmann, Andreas Emil and Pawlewicz, Jakub and Zych-Pawlewicz, Anna}, title = {{Recoloring Interval Graphs with Limited Recourse Budget}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {17:1--17:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.17}, URN = {urn:nbn:de:0030-drops-122649}, doi = {10.4230/LIPIcs.SWAT.2020.17}, annote = {Keywords: Colouring, Dynamic Algorithms, Recourse Budget, Interval Graphs} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Johannes Blum. Hierarchy of Transportation Network Parameters and Hardness Results. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blum:LIPIcs.IPEC.2019.4, author = {Blum, Johannes}, title = {{Hierarchy of Transportation Network Parameters and Hardness Results}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.4}, URN = {urn:nbn:de:0030-drops-114656}, doi = {10.4230/LIPIcs.IPEC.2019.4}, annote = {Keywords: Graph Parameters, Skeleton Dimension, Highway Dimension, k-Center} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Rajesh Chitnis and Andreas Emil Feldmann. FPT Inapproximability of Directed Cut and Connectivity Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chitnis_et_al:LIPIcs.IPEC.2019.8, author = {Chitnis, Rajesh and Feldmann, Andreas Emil}, title = {{FPT Inapproximability of Directed Cut and Connectivity Problems}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.8}, URN = {urn:nbn:de:0030-drops-114692}, doi = {10.4230/LIPIcs.IPEC.2019.8}, annote = {Keywords: Directed graphs, cuts, connectivity, Steiner problems, FPT inapproximability} }