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 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kent Quanrud. Adaptive Sparsification for Matroid Intersection. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{quanrud:LIPIcs.ICALP.2024.118, author = {Quanrud, Kent}, title = {{Adaptive Sparsification for Matroid Intersection}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {118:1--118: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.118}, URN = {urn:nbn:de:0030-drops-202614}, doi = {10.4230/LIPIcs.ICALP.2024.118}, annote = {Keywords: Matroid intersection, adaptive sparsification, multiplicative-weight udpates, primal-dual} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
François Sellier. Parameterized Matroid-Constrained Maximum Coverage. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 94:1-94:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{sellier:LIPIcs.ESA.2023.94, author = {Sellier, Fran\c{c}ois}, title = {{Parameterized Matroid-Constrained Maximum Coverage}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {94:1--94:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.94}, URN = {urn:nbn:de:0030-drops-187475}, doi = {10.4230/LIPIcs.ESA.2023.94}, annote = {Keywords: Matroids, approximate kernel, maximum coverage} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Chien-Chung Huang and François Sellier. Maximum Weight b-Matchings in Random-Order Streams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{huang_et_al:LIPIcs.ESA.2022.68, author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois}, title = {{Maximum Weight b-Matchings in Random-Order Streams}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {68:1--68: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.68}, URN = {urn:nbn:de:0030-drops-170062}, doi = {10.4230/LIPIcs.ESA.2022.68}, annote = {Keywords: Maximum weight matching, b-matching, streaming, random order} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Chien-Chung Huang and François Sellier. Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{huang_et_al:LIPIcs.SWAT.2022.27, author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois}, title = {{Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.27}, URN = {urn:nbn:de:0030-drops-161874}, doi = {10.4230/LIPIcs.SWAT.2022.27}, annote = {Keywords: Maximum vertex cover, matroid, approximate kernel, streaming} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Chien-Chung Huang and François Sellier. Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2021.14, author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois}, title = {{Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.14}, URN = {urn:nbn:de:0030-drops-147072}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.14}, annote = {Keywords: Maximum Weight Matching, Submodular Function Maximization, Streaming, Matroid} }