Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Zachary Friggstad and Ramin Mousavi. A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{friggstad_et_al:LIPIcs.APPROX/RANDOM.2023.13, author = {Friggstad, Zachary and Mousavi, Ramin}, title = {{A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {13:1--13:18}, 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.13}, URN = {urn:nbn:de:0030-drops-188389}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.13}, annote = {Keywords: Directed Steiner tree, Combinatorial optimization, approximation algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Zachary Friggstad and Ramin Mousavi. An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{friggstad_et_al:LIPIcs.ICALP.2023.63, author = {Friggstad, Zachary and Mousavi, Ramin}, title = {{An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {63:1--63:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.63}, URN = {urn:nbn:de:0030-drops-181156}, doi = {10.4230/LIPIcs.ICALP.2023.63}, annote = {Keywords: Directed Steiner tree, Combinatorial optimization, approximation algorithms} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Zachary Friggstad and Ramin Mousavi. Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{friggstad_et_al:LIPIcs.ISAAC.2022.8, author = {Friggstad, Zachary and Mousavi, Ramin}, title = {{Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.8}, URN = {urn:nbn:de:0030-drops-172932}, doi = {10.4230/LIPIcs.ISAAC.2022.8}, annote = {Keywords: Linear programming, approximation algorithms, combinatorial optimization} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Zachary Friggstad and Mahya Jamshidian. Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{friggstad_et_al:LIPIcs.ESA.2022.56, author = {Friggstad, Zachary and Jamshidian, Mahya}, title = {{Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.56}, URN = {urn:nbn:de:0030-drops-169946}, doi = {10.4230/LIPIcs.ESA.2022.56}, annote = {Keywords: Approximation Algorithms, Clustering, Linear Programming} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Zachary Friggstad and Chaitanya Swamy. Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 67:1-67:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{friggstad_et_al:LIPIcs.ICALP.2021.67, author = {Friggstad, Zachary and Swamy, Chaitanya}, title = {{Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {67:1--67:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.67}, URN = {urn:nbn:de:0030-drops-141369}, doi = {10.4230/LIPIcs.ICALP.2021.67}, annote = {Keywords: Approximation algorithms, Vehicle routing problems, Deadline TSP, Orienteering} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Haozhou Pang and Mohammad R. Salavatipour. Approximation Algorithms for Generalized Path Scheduling. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{pang_et_al:LIPIcs.ISAAC.2020.10, author = {Pang, Haozhou and Salavatipour, Mohammad R.}, title = {{Approximation Algorithms for Generalized Path Scheduling}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.10}, URN = {urn:nbn:de:0030-drops-133547}, doi = {10.4230/LIPIcs.ISAAC.2020.10}, annote = {Keywords: Approximation Algorithms, Path Scheduling, Flow shop, Job Shop} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Zachary Friggstad and Chaitanya Swamy. A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{friggstad_et_al:LIPIcs.ESA.2020.52, author = {Friggstad, Zachary and Swamy, Chaitanya}, title = {{A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {52:1--52:20}, 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.52}, URN = {urn:nbn:de:0030-drops-129183}, doi = {10.4230/LIPIcs.ESA.2020.52}, annote = {Keywords: Approximation Algorithms, Directed Latency, TSP} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang. Scheduling Problems over Network of Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{friggstad_et_al:LIPIcs.APPROX-RANDOM.2017.5, author = {Friggstad, Zachary and Golestanian, Arnoosh and Khodamoradi, Kamyar and Martin, Christopher and Rahgoshay, Mirmahdi and Rezapour, Mohsen and Salavatipour, Mohammad R. and Zhang, Yifeng}, title = {{Scheduling Problems over Network of Machines}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {5:1--5:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.5}, URN = {urn:nbn:de:0030-drops-75547}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.5}, annote = {Keywords: approximation algorithms, job-shop scheduling, min-sum edge coloring, minimum latency} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Sara Ahmadian and Zachary Friggstad. Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ahmadian_et_al:LIPIcs.ICALP.2017.55, author = {Ahmadian, Sara and Friggstad, Zachary}, title = {{Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {55:1--55:13}, 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.55}, URN = {urn:nbn:de:0030-drops-74600}, doi = {10.4230/LIPIcs.ICALP.2017.55}, annote = {Keywords: Approximation Algorithms, Column-Restricted Packing, Demand Matching, Matroids, Planar Graphs} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Zachary Friggstad and Yifeng Zhang. Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{friggstad_et_al:LIPIcs.ICALP.2016.75, author = {Friggstad, Zachary and Zhang, Yifeng}, title = {{Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {75:1--75:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.75}, URN = {urn:nbn:de:0030-drops-62094}, doi = {10.4230/LIPIcs.ICALP.2016.75}, annote = {Keywords: Approximation Algorithms, Local search, Red-Blue Meidan} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{friggstad_et_al:LIPIcs.SWAT.2016.1, author = {Friggstad, Zachary and Rezapour, Mohsen and Salavatipour, Mohammad R.}, title = {{Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {1:1--1:14}, 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.1}, URN = {urn:nbn:de:0030-drops-60302}, doi = {10.4230/LIPIcs.SWAT.2016.1}, annote = {Keywords: Facility Location, Approximation Algorithm, LP Rounding} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Zachary Friggstad, Jochen Könemann, and Mohammad Shadravan. A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{friggstad_et_al:LIPIcs.SWAT.2016.3, author = {Friggstad, Zachary and K\"{o}nemann, Jochen and Shadravan, Mohammad}, title = {{A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {3:1--3:11}, 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.3}, URN = {urn:nbn:de:0030-drops-60323}, doi = {10.4230/LIPIcs.SWAT.2016.3}, annote = {Keywords: Approximation algorithm, Primal-Dual algorithm, Directed Steiner tree} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Zachary Friggstad and Zhihan Gao. On Linear Programming Relaxations for Unsplittable Flow in Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 265-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{friggstad_et_al:LIPIcs.APPROX-RANDOM.2015.265, author = {Friggstad, Zachary and Gao, Zhihan}, title = {{On Linear Programming Relaxations for Unsplittable Flow in Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {265--283}, 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.265}, URN = {urn:nbn:de:0030-drops-53073}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.265}, annote = {Keywords: Unsplittable flow, Linear programming relaxation, Approximation algorithm} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy. Approximation Algorithms for Minimum-Load k-Facility Location. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 17-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{ahmadian_et_al:LIPIcs.APPROX-RANDOM.2014.17, author = {Ahmadian, Sara and Behsaz, Babak and Friggstad, Zachary and Jorati, Amin and Salavatipour, Mohammad R. and Swamy, Chaitanya}, title = {{Approximation Algorithms for Minimum-Load k-Facility Location}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {17--33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.17}, URN = {urn:nbn:de:0030-drops-47154}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.17}, annote = {Keywords: approximation algorithms, min-max star cover, facility location, line metrics} }
Feedback for Dagstuhl Publishing