Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Yu Chen, Sanjeev Khanna, and Zihan Tan. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 37:1-37:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.37, author = {Chen, Yu and Khanna, Sanjeev and Tan, Zihan}, title = {{Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {37:1--37:16}, 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.37}, URN = {urn:nbn:de:0030-drops-180892}, doi = {10.4230/LIPIcs.ICALP.2023.37}, annote = {Keywords: Minimum spanning tree, travelling salesman problem, streaming algorithms} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan. A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 38:1-38:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chuzhoy_et_al:LIPIcs.ITCS.2023.38, author = {Chuzhoy, Julia and Dalirrooyfard, Mina and Grinberg, Vadim and Tan, Zihan}, title = {{A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {38:1--38:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.38}, URN = {urn:nbn:de:0030-drops-175411}, doi = {10.4230/LIPIcs.ITCS.2023.38}, annote = {Keywords: Hardness of Approximation, Densest k-Subgraph} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Julia Chuzhoy, Merav Parter, and Zihan Tan. On Packing Low-Diameter Spanning Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chuzhoy_et_al:LIPIcs.ICALP.2020.33, author = {Chuzhoy, Julia and Parter, Merav and Tan, Zihan}, title = {{On Packing Low-Diameter Spanning Trees}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {33:1--33:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.33}, URN = {urn:nbn:de:0030-drops-124405}, doi = {10.4230/LIPIcs.ICALP.2020.33}, annote = {Keywords: Spanning tree, packing, edge-connectivity} }
Feedback for Dagstuhl Publishing