D1
Algorithms & Complexity

Current Year

[1]
A. Abboud, K. Bringmann, S. Khoury, and O. Zamir, “Hardness of Approximation in p via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond,” in STOC ’22, Fifty Fourth Annual ACM Symposium on Theory of Computing, Rome, Italy, 2022.
Export
BibTeX
@inproceedings{AbboudSTOC22, TITLE = {Hardness of Approximation in p via Short Cycle Removal: {C}ycle Detection, Distance Oracles, and Beyond}, AUTHOR = {Abboud, Amir and Bringmann, Karl and Khoury, Seri and Zamir, Or}, LANGUAGE = {eng}, ISBN = {978-1-4503-9264-8}, DOI = {10.1145/3519935.3520066}, PUBLISHER = {ACM}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {STOC '22, Fifty Fourth Annual ACM Symposium on Theory of Computing}, EDITOR = {Leonardi, Stefano and Gupta, Anupam}, PAGES = {1487--1500}, ADDRESS = {Rome, Italy}, }
Endnote
%0 Conference Proceedings %A Abboud, Amir %A Bringmann, Karl %A Khoury, Seri %A Zamir, Or %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Hardness of Approximation in p via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond : %G eng %U http://hdl.handle.net/21.11116/0000-000B-4797-B %R 10.1145/3519935.3520066 %D 2022 %B Fifty Fourth Annual ACM Symposium on Theory of Computing %Z date of event: 2022-06-20 - 2022-06-24 %C Rome, Italy %B STOC '22 %E Leonardi, Stefano; Gupta, Anupam %P 1487 - 1500 %I ACM %@ 978-1-4503-9264-8
[2]
A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay, “Scheduling Lower Bounds via AND Subset Sum,” Journal of Computer and System Sciences, vol. 127, 2022.
Export
BibTeX
@article{Abboud22, TITLE = {Scheduling Lower Bounds via {AND} Subset Sum}, AUTHOR = {Abboud, Amir and Bringmann, Karl and Hermelin, Danny and Shabtay, Dvir}, LANGUAGE = {eng}, ISSN = {0022-0000}, DOI = {10.1016/j.jcss.2022.01.005}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {127}, PAGES = {29--40}, }
Endnote
%0 Journal Article %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Scheduling Lower Bounds via AND Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-000B-153C-B %R 10.1016/j.jcss.2022.01.005 %7 2022 %D 2022 %J Journal of Computer and System Sciences %V 127 %& 29 %P 29 - 40 %I Elsevier %C Amsterdam %@ false
[3]
A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay, “SETH-Based Lower Bounds for Subset Sum and Bicriteria Path,” ACM Transactions on Algorithms, vol. 18, no. 1, 2022.
Export
BibTeX
@article{Abboud22a, TITLE = {{SETH}-Based Lower Bounds for Subset Sum and Bicriteria Path}, AUTHOR = {Abboud, Amir and Bringmann, Karl and Hermelin, Danny and Shabtay, Dvir}, LANGUAGE = {eng}, ISSN = {1549-6325}, DOI = {10.1145/3450524}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = {18}, NUMBER = {1}, PAGES = {1--22}, EID = {6}, }
Endnote
%0 Journal Article %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T SETH-Based Lower Bounds for Subset Sum and Bicriteria Path : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1543-2 %R 10.1145/3450524 %7 2022 %D 2022 %J ACM Transactions on Algorithms %V 18 %N 1 %& 1 %P 1 - 22 %Z sequence number: 6 %I ACM %C New York, NY %@ false
[4]
A. Agrawal, D. Lokshtanov, P. Misra, S. Saurabh, and M. Zehavi, “Erdős–Pósa Property of Obstructions to Interval Graphs,” Journal of Graph Theory, vol. Early View, 2022.
Export
BibTeX
@article{Agrawal2022, TITLE = {Erd{\H o}s--P{\'o}sa Property of Obstructions to Interval Graphs}, AUTHOR = {Agrawal, Akanksha and Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Zehavi, Meirav}, LANGUAGE = {eng}, ISSN = {0364-9024}, DOI = {10.1002/jgt.22895}, PUBLISHER = {John Wiley \& Sons.}, ADDRESS = {New York}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Graph Theory}, VOLUME = {Early View}, }
Endnote
%0 Journal Article %A Agrawal, Akanksha %A Lokshtanov, Daniel %A Misra, Pranabendu %A Saurabh, Saket %A Zehavi, Meirav %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Erdős–Pósa Property of Obstructions to Interval Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000B-589A-5 %R 10.1002/jgt.22895 %7 2022 %D 2022 %J Journal of Graph Theory %V Early View %I John Wiley & Sons. %C New York %@ false
[5]
G. Amanatidis and P. Kleer, “Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices,” SIAM Journal on Discrete Mathematics, vol. 36, no. 1, 2022.
Export
BibTeX
@article{Amanatidis2022, TITLE = {Rapid Mixing of the Switch {M}arkov Chain for 2-Class Joint Degree Matrices}, AUTHOR = {Amanatidis, Georgios and Kleer, Pieter}, LANGUAGE = {eng}, ISSN = {0895-4801}, DOI = {10.1137/20M1352697}, PUBLISHER = {The Society}, ADDRESS = {Philadelphia, Pa.}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {36}, NUMBER = {1}, PAGES = {118--146}, }
Endnote
%0 Journal Article %A Amanatidis, Georgios %A Kleer, Pieter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-000A-567A-D %R 10.1137/20M1352697 %7 2022 %D 2022 %J SIAM Journal on Discrete Mathematics %V 36 %N 1 %& 118 %P 118 - 146 %I The Society %C Philadelphia, Pa. %@ false
[6]
S. A. Amiri and B. Wiederhake, “Distributed Distance-r Dominating Set on Sparse High-Girth Graphs,” Theoretical Computer Science, vol. 906, 2022.
Export
BibTeX
@article{Amiri22, TITLE = {Distributed Distance-$r$ Dominating Set on Sparse High-Girth Graphs}, AUTHOR = {Amiri, Saeed Akhoondian and Wiederhake, Ben}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2022.01.001}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Theoretical Computer Science}, VOLUME = {906}, PAGES = {18--31}, }
Endnote
%0 Journal Article %A Amiri, Saeed Akhoondian %A Wiederhake, Ben %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Distributed Distance-r Dominating Set on Sparse High-Girth Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000A-9DFE-8 %R 10.1016/j.tcs.2022.01.001 %7 2022 %D 2022 %J Theoretical Computer Science %V 906 %& 18 %P 18 - 31 %I Elsevier %C Amsterdam %@ false
[7]
B. Banyassady, M. de Berg, K. Bringmann, K. Buchin, H. Fernau, D. Halperin, I. Kostitsyna, Y. Okamoto, and S. Slot, “Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
Export
BibTeX
@inproceedings{Banyassady_SoCG2022, TITLE = {Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds}, AUTHOR = {Banyassady, Bahareh and de Berg, Mark and Bringmann, Karl and Buchin, Kevin and Fernau, Henning and Halperin, Dan and Kostitsyna, Irina and Okamoto, Yoshio and Slot, Stijn}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-227-3}, URL = {urn:nbn:de:0030-drops-160203}, DOI = {10.4230/LIPIcs.SoCG.2022.12}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {38th International Symposium on Computational Geometry (SoCG 2022)}, EDITOR = {Goaoc, Xavier and Kerber, Michael}, PAGES = {1--16}, EID = {12}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {224}, ADDRESS = {Berlin, Germany}, }
Endnote
%0 Conference Proceedings %A Banyassady, Bahareh %A de Berg, Mark %A Bringmann, Karl %A Buchin, Kevin %A Fernau, Henning %A Halperin, Dan %A Kostitsyna, Irina %A Okamoto, Yoshio %A Slot, Stijn %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations %T Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1553-0 %R 10.4230/LIPIcs.SoCG.2022.12 %U urn:nbn:de:0030-drops-160203 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 16 %Z sequence number: 12 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false
[8]
R. Beier, H. Röglin, C. Rösner, and B. Vöcking, “The Smoothed Number of Pareto-optimal Solutions in Bicriteria Integer Optimization,” Mathematical Programming / A, vol. Early Access, 2022.
Export
BibTeX
@article{Beier2022, TITLE = {The smoothed number of {P}areto-optimal solutions in bicriteria integer optimization}, AUTHOR = {Beier, Ren{\'e} and R{\"o}glin, Heiko and R{\"o}sner, Clemens and V{\"o}cking, Berthold}, LANGUAGE = {eng}, ISSN = {0025-5610}, DOI = {10.1007/s10107-022-01885-6}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, JOURNAL = {Mathematical Programming / A}, VOLUME = {Early Access}, }
Endnote
%0 Journal Article %A Beier, René %A Röglin, Heiko %A Rösner, Clemens %A Vöcking, Berthold %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T The Smoothed Number of Pareto-optimal Solutions in Bicriteria Integer Optimization : %G eng %U http://hdl.handle.net/21.11116/0000-000B-58A2-B %R 10.1007/s10107-022-01885-6 %7 2022 %D 2022 %J Mathematical Programming / A %V Early Access %I Springer %C Heidelberg %@ false
[9]
V. Bonifaci, E. Facca, F. Folz, A. Karrenbauer, P. Kolev, K. Mehlhorn, G. Morigi, G. Shahkarami, and Q. Vermande, “Physarum-inspired Multi-commodity Flow Dynamics,” Theoretical Computer Science, vol. 920, 2022.
Export
BibTeX
@article{Bonifaci2022, TITLE = {Physarum-inspired Multi-commodity Flow Dynamics}, AUTHOR = {Bonifaci, Vincenzo and Facca, Enrico and Folz, Frederic and Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt and Morigi, Giovanna and Shahkarami, Golnoosh and Vermande, Quentin}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2022.02.001}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, JOURNAL = {Theoretical Computer Science}, VOLUME = {920}, PAGES = {1--20}, }
Endnote
%0 Journal Article %A Bonifaci, Vincenzo %A Facca, Enrico %A Folz, Frederic %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %A Morigi, Giovanna %A Shahkarami, Golnoosh %A Vermande, Quentin %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Physarum-inspired Multi-commodity Flow Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-000A-28A1-3 %R 10.1016/j.tcs.2022.02.001 %7 2022 %D 2022 %J Theoretical Computer Science %V 920 %& 1 %P 1 - 20 %I Elsevier %C Amsterdam %@ false
[10]
K. Bringmann, A. Cassis, N. Fischer, and V. Nakos, “Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime,” in STOC ’22, Fifty Fourth Annual ACM Symposium on Theory of Computing, Rome, Italy, 2022.
Export
BibTeX
@inproceedings{BringmannSTOC22, TITLE = {Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime}, AUTHOR = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and Nakos, Vasileios}, LANGUAGE = {eng}, ISBN = {978-1-4503-9264-8}, DOI = {10.1145/3519935.3519990}, PUBLISHER = {ACM}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {STOC '22, Fifty Fourth Annual ACM Symposium on Theory of Computing}, EDITOR = {Leonardi, Stefano and Gupta, Anupam}, PAGES = {1102--1115}, ADDRESS = {Rome, Italy}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime : %G eng %U http://hdl.handle.net/21.11116/0000-000B-588D-4 %R 10.1145/3519935.3519990 %D 2022 %B Fifty Fourth Annual ACM Symposium on Theory of Computing %Z date of event: 2022-06-20 - 2022-06-24 %C Rome, Italy %B STOC '22 %E Leonardi, Stefano; Gupta, Anupam %P 1102 - 1115 %I ACM %@ 978-1-4503-9264-8
[11]
K. Bringmann, R. Keusch, J. Lengler, Y. Maus, and A. R. Molla, “Greedy Routing and the Algorithmic Small-World Phenomenon,” Journal of Computer and System Sciences, vol. 125, 2022.
Export
BibTeX
@article{Bringmann22, TITLE = {Greedy Routing and the Algorithmic Small-World Phenomenon}, AUTHOR = {Bringmann, Karl and Keusch, Ralph and Lengler, Johannes and Maus, Yannic and Molla, Anisur Rahaman}, LANGUAGE = {eng}, ISSN = {0022-0000}, DOI = {10.1016/j.jcss.2021.11.003}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {125}, PAGES = {59--105}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A Keusch, Ralph %A Lengler, Johannes %A Maus, Yannic %A Molla, Anisur Rahaman %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Greedy Routing and the Algorithmic Small-World Phenomenon : %G eng %U http://hdl.handle.net/21.11116/0000-000A-9DD0-A %R 10.1016/j.jcss.2021.11.003 %7 2022 %D 2022 %J Journal of Computer and System Sciences %V 125 %& 59 %P 59 - 105 %I Elsevier %C Amsterdam %@ false
[12]
K. Bringmann, N. Fischer, D. Hermelin, D. Shabtay, and P. Wellnitz, “Faster Minimization of Tardy Processing Time on a Single Machine,” Algorithmica, 2022.
Export
BibTeX
@article{Bringmann2022, TITLE = {Faster Minimization of Tardy Processing Time on a Single Machine}, AUTHOR = {Bringmann, Karl and Fischer, Nick and Hermelin, Danny and Shabtay, Dvir and Wellnitz, Philip}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-022-00928-w}, PUBLISHER = {Springer}, ADDRESS = {New York}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Algorithmica}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A Fischer, Nick %A Hermelin, Danny %A Shabtay, Dvir %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Minimization of Tardy Processing Time on a Single Machine : %G eng %U http://hdl.handle.net/21.11116/0000-0009-FAD4-E %R 10.1007/s00453-022-00928-w %7 2022 %D 2022 %J Algorithmica %I Springer %C New York %@ false %U https://rdcu.be/cG2A9
[13]
K. Bringmann, S. Kisfaludi-Bak, M. Künnemann, D. Marx, and A. Nusser, “Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
Export
BibTeX
@inproceedings{Bringmann_SoCG2022, TITLE = {Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves}, AUTHOR = {Bringmann, Karl and Kisfaludi-Bak, S{\'a}ndor and K{\"u}nnemann, Marvin and Marx, D{\'a}niel and Nusser, Andr{\'e}}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-227-3}, URL = {urn:nbn:de:0030-drops-160287}, DOI = {10.4230/LIPIcs.SoCG.2022.20}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {38th International Symposium on Computational Geometry (SoCG 2022)}, EDITOR = {Goaoc, Xavier and Kerber, Michael}, PAGES = {1--17}, EID = {20}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {224}, ADDRESS = {Berlin, Germany}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Kisfaludi-Bak, Sándor %A Künnemann, Marvin %A Marx, Dániel %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1560-1 %R 10.4230/LIPIcs.SoCG.2022.20 %U urn:nbn:de:0030-drops-160287 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 17 %Z sequence number: 20 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false
[14]
K. Bringmann, S. Kisfaludi-Bak, M. Künnemann, A. Nusser, and Z. Parsaeian, “Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
Export
BibTeX
@inproceedings{Bringmann_SoCG2022b, TITLE = {Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs}, AUTHOR = {Bringmann, Karl and Kisfaludi-Bak, S{\'a}ndor and K{\"u}nnemann, Marvin and Nusser, Andr{\'e} and Parsaeian, Zahra}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-227-3}, URL = {urn:nbn:de:0030-drops-160294}, DOI = {10.4230/LIPIcs.SoCG.2022.21}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {38th International Symposium on Computational Geometry (SoCG 2022)}, EDITOR = {Goaoc, Xavier and Kerber, Michael}, PAGES = {1--16}, EID = {21}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {224}, ADDRESS = {Berlin, Germany}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Kisfaludi-Bak, Sándor %A Künnemann, Marvin %A Nusser, André %A Parsaeian, Zahra %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1572-D %R 10.4230/LIPIcs.SoCG.2022.21 %U urn:nbn:de:0030-drops-160294 %D 2022 %B 38th International Symposium on Computational Geometry %Z date of event: 2022-06-07 - 2022-06-10 %C Berlin, Germany %B 38th International Symposium on Computational Geometry %E Goaoc, Xavier; Kerber, Michael %P 1 - 16 %Z sequence number: 21 %I Schloss Dagstuhl %@ 978-3-95977-227-3 %B Leibniz International Proceedings in Informatics %N 224 %@ false
[15]
K. Bringmann, A. Cassis, N. Fischer, and M. Künnemann, “A Structural Investigation of the Approximability of Polynomial-Time Problems,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
Export
BibTeX
@inproceedings{Bringmann_ICALP22, TITLE = {A Structural Investigation of the Approximability of Polynomial-Time Problems}, AUTHOR = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and K{\"u}nnemann, Marvin}, LANGUAGE = {eng}, ISBN = {978-3-95977-235-8{\textbraceright}}, URL = {urn:nbn:de:0030-drops-163713}, DOI = {10.4230/LIPIcs.ICALP.2022.30}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022)}, EDITOR = {Boja{\'n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, PAGES = {1--20}, EID = {30}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {229}, ADDRESS = {Paris, France}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A Künnemann, Marvin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Structural Investigation of the Approximability of Polynomial-Time Problems : %G eng %U http://hdl.handle.net/21.11116/0000-000B-15B5-1 %R 10.4230/LIPIcs.ICALP.2022.30 %U urn:nbn:de:0030-drops-163713 %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Bojańczyk, Mikołaj; Merelli, Emanuela; Woodruff, David P. %P 1 - 20 %Z sequence number: 30 %I Schloss Dagstuhl %@ 978-3-95977-235-8} %B Leibniz International Proceedings in Informatics %N 229
[16]
K. Bringmann, A. Cassis, N. Fischer, and V. Nakos, “Improved Sublinear-Time Edit Distance for Preprocessed Strings,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
Export
BibTeX
@inproceedings{Bringmann_ICALP22c, TITLE = {Improved Sublinear-Time Edit Distance for Preprocessed Strings}, AUTHOR = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and Nakos, Vasileios}, LANGUAGE = {eng}, ISBN = {978-3-95977-235-8{\textbraceright}}, URL = {urn:nbn:de:0030-drops-163734}, DOI = {10.4230/LIPIcs.ICALP.2022.32}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022)}, EDITOR = {Boja{\'n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, PAGES = {1--20}, EID = {32}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {229}, ADDRESS = {Paris, France}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Improved Sublinear-Time Edit Distance for Preprocessed Strings : %G eng %U http://hdl.handle.net/21.11116/0000-000B-163A-C %R 10.4230/LIPIcs.ICALP.2022.32 %U urn:nbn:de:0030-drops-163734 %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Bojańczyk, Mikołaj; Merelli, Emanuela; Woodruff, David P. %P 1 - 20 %Z sequence number: 32 %I Schloss Dagstuhl %@ 978-3-95977-235-8} %B Leibniz International Proceedings in Informatics %N 229
[17]
K. Bringmann and A. Cassis, “Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
Export
BibTeX
@inproceedings{Bringmann_ICALP22b, TITLE = {Faster {K}napsack Algorithms via Bounded Monotone Min-Plus-Convolution}, AUTHOR = {Bringmann, Karl and Cassis, Alejandro}, LANGUAGE = {eng}, ISBN = {978-3-95977-235-8{\textbraceright}}, URL = {urn:nbn:de:0030-drops-163727}, DOI = {10.4230/LIPIcs.ICALP.2022.31}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022)}, EDITOR = {Boja{\'n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, PAGES = {1--21}, EID = {31}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {229}, ADDRESS = {Paris, France}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Cassis, Alejandro %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-000B-1622-6 %R 10.4230/LIPIcs.ICALP.2022.31 %U urn:nbn:de:0030-drops-163727 %D 2022 %B 49th International Colloquium on Automata, Languages, and Programming %Z date of event: 2022-07-04 - 2022-07-08 %C Paris, France %B 49th EATCS International Conference on Automata, Languages, and Programming %E Bojańczyk, Mikołaj; Merelli, Emanuela; Woodruff, David P. %P 1 - 21 %Z sequence number: 31 %I Schloss Dagstuhl %@ 978-3-95977-235-8} %B Leibniz International Proceedings in Informatics %N 229
[18]
K. Bringmann, N. Carmeli, and S. Mengel, “Tight Fine-Grained Bounds for Direct Access on Join Queries,” in PODS ’22, 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Philadelphia, PA, USA, 2022.
Export
BibTeX
@inproceedings{Bringmann_PODS22, TITLE = {Tight Fine-Grained Bounds for Direct Access on Join Queries}, AUTHOR = {Bringmann, Karl and Carmeli, Nofar and Mengel, Stefan}, LANGUAGE = {eng}, ISBN = {978-1-4503-9260-0}, DOI = {10.1145/3517804.3526234}, PUBLISHER = {ACM}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {PODS '22, 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems}, EDITOR = {Libkin, Leonid and Barcel{\'o}, Pablo and Grez, Alejandro}, PAGES = {427--436}, ADDRESS = {Philadelphia, PA, USA}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Carmeli, Nofar %A Mengel, Stefan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Tight Fine-Grained Bounds for Direct Access on Join Queries : %G eng %U http://hdl.handle.net/21.11116/0000-000B-2037-3 %R 10.1145/3517804.3526234 %D 2022 %B 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems %Z date of event: 2022-06-12 - 2022-06-17 %C Philadelphia, PA, USA %B PODS '22 %E Libkin, Leonid; Barceló, Pablo; Grez, Alejandro %P 427 - 436 %I ACM %@ 978-1-4503-9260-0
[19]
C. Coupette, D. Hartung, J. Beckedorf, M. Bother, and D. M. Katz, “Law Smells - Defining and Detecting Problematic Patterns in Legal Drafting,” Artificial Intelligence and Law, 2022.
Export
BibTeX
@article{Coupette22, TITLE = {Law Smells -- Defining and Detecting Problematic Patterns in Legal Drafting}, AUTHOR = {Coupette, Corinna and Hartung, Dirk and Beckedorf, Janis and Bother, Maximilian and Katz, Daniel Martin}, LANGUAGE = {eng}, ISSN = {0924-8463}, DOI = {10.1007/s10506-022-09315-w}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Artificial Intelligence and Law}, }
Endnote
%0 Journal Article %A Coupette, Corinna %A Hartung, Dirk %A Beckedorf, Janis %A Bother, Maximilian %A Katz, Daniel Martin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Law Smells - Defining and Detecting Problematic Patterns in Legal Drafting : %G eng %U http://hdl.handle.net/21.11116/0000-000A-CD04-B %R 10.1007/s10506-022-09315-w %7 2022 %D 2022 %J Artificial Intelligence and Law %I Springer %C New York, NY %@ false
[20]
C. Croitoru and M. Croitoru, “Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation,” Annals of Mathematics and Artificial Intelligence, 2022.
Export
BibTeX
@article{Croitoru2022, TITLE = {Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation}, AUTHOR = {Croitoru, Cosmina and Croitoru, Madalina}, LANGUAGE = {eng}, ISSN = {1012-2443}, DOI = {10.1007/s10472-022-09785-3}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Annals of Mathematics and Artificial Intelligence}, }
Endnote
%0 Journal Article %A Croitoru, Cosmina %A Croitoru, Madalina %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation : %G eng %U http://hdl.handle.net/21.11116/0000-000A-5D72-E %R 10.1007/s10472-022-09785-3 %7 2022 %D 2022 %J Annals of Mathematics and Artificial Intelligence %I Springer %C New York, NY %@ false
[21]
Á. Cseh, Y. Faenza, T. Kavitha, and V. Powers, “Understanding Popular Matchings via Stable Matchings,” SIAM Journal on Discrete Mathematics, vol. 36, no. 1, 2022.
Export
BibTeX
@article{Cseh2022, TITLE = {Understanding Popular Matchings via Stable Matchings}, AUTHOR = {Cseh, {\'A}gnes and Faenza, Yuri and Kavitha, Telikepalli and Powers, Vladlena}, LANGUAGE = {eng}, ISSN = {0895-4801}, DOI = {10.1137/19M124770X}, PUBLISHER = {The Society}, ADDRESS = {Philadelphia, Pa.}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {36}, NUMBER = {1}, PAGES = {188--213}, }
Endnote
%0 Journal Article %A Cseh, Ágnes %A Faenza, Yuri %A Kavitha, Telikepalli %A Powers, Vladlena %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Understanding Popular Matchings via Stable Matchings : %G eng %U http://hdl.handle.net/21.11116/0000-000A-57C3-8 %R 10.1137/19M124770X %7 2022 %D 2022 %J SIAM Journal on Discrete Mathematics %V 36 %N 1 %& 188 %P 188 - 213 %I The Society %C Philadelphia, Pa. %@ false
[22]
M. Függer, A. Kinali, C. Lenzen, and B. Wiederhake, “Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 8, 2022.
Export
BibTeX
@article{Fuegger2021, TITLE = {Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance}, AUTHOR = {F{\"u}gger, Matthias and Kinali, Attila and Lenzen, Christoph and Wiederhake, Ben}, LANGUAGE = {eng}, ISSN = {0278-0070}, DOI = {10.1109/TCAD.2021.3097599}, PUBLISHER = {IEEE}, ADDRESS = {Piscataway, NJ}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, JOURNAL = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems}, VOLUME = {41}, NUMBER = {8}, PAGES = {2518--2531}, }
Endnote
%0 Journal Article %A Függer, Matthias %A Kinali, Attila %A Lenzen, Christoph %A Wiederhake, Ben %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance : %G eng %U http://hdl.handle.net/21.11116/0000-0009-201C-4 %R 10.1109/TCAD.2021.3097599 %7 2021 %D 2022 %J IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems %V 41 %N 8 %& 2518 %P 2518 - 2531 %I IEEE %C Piscataway, NJ %@ false
[23]
E. Galby, D. Marx, S. Philipp, R. Sharma, and P. Tale, “Parameterized Complexity of Weighted Multicut in Trees,” in Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany, 2022.
Export
BibTeX
@inproceedings{GalbyWG22, TITLE = {Parameterized Complexity of Weighted Multicut in Trees}, AUTHOR = {Galby, Esther and Marx, D{\'a}niel and Philipp, Schepper and Sharma, Roohani and Tale, Prafullkumar}, LANGUAGE = {eng}, ISBN = {978-3-031-15913-8}, DOI = {10.1007/978-3-031-15914-5_19}, PUBLISHER = {Springer}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, BOOKTITLE = {Graph-Theoretic Concepts in Computer Science (WG 2022)}, EDITOR = {Bekos, Michael A. and Kaufmann, Michael}, PAGES = {257--270}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {13453}, ADDRESS = {T{\"u}bingen, Germany}, }
Endnote
%0 Conference Proceedings %A Galby, Esther %A Marx, Dániel %A Philipp, Schepper %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Parameterized Complexity of Weighted Multicut in Trees : %G eng %U http://hdl.handle.net/21.11116/0000-000B-5925-8 %R 10.1007/978-3-031-15914-5_19 %D 2022 %B 48th International Workshop on Graph-Theoretic Concepts in Computer Science %Z date of event: 2022-06-22 - 2022-06-24 %C Tübingen, Germany %B Graph-Theoretic Concepts in Computer Science %E Bekos, Michael A.; Kaufmann, Michael %P 257 - 270 %I Springer %@ 978-3-031-15913-8 %B Lecture Notes in Computer Science %N 13453
[24]
D. Halperin, S. Har-Peled, K. Mehlhorn, E. Oh, and M. Sharir, “The Maximum-Level Vertex in an Arrangement of Lines,” Discrete & Computational Geometry, vol. 67, 2022.
Export
BibTeX
@article{Halperin2022, TITLE = {The Maximum-Level Vertex in an Arrangement of Lines}, AUTHOR = {Halperin, Dan and Har-Peled, Sariel and Mehlhorn, Kurt and Oh, Eunjin and Sharir, Micha}, LANGUAGE = {eng}, ISSN = {0179-5376}, DOI = {10.1007/s00454-021-00338-9}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Discrete \& Computational Geometry}, VOLUME = {67}, PAGES = {439--461}, }
Endnote
%0 Journal Article %A Halperin, Dan %A Har-Peled, Sariel %A Mehlhorn, Kurt %A Oh, Eunjin %A Sharir, Micha %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Maximum-Level Vertex in an Arrangement of Lines : %G eng %U http://hdl.handle.net/21.11116/0000-0009-D020-7 %R 10.1007/s00454-021-00338-9 %7 2022 %D 2022 %J Discrete & Computational Geometry %V 67 %& 439 %P 439 - 461 %I Springer %C New York, NY %@ false %U https://rdcu.be/cFlQF
[25]
A. Kinali-Dogan, “On Time, Time Synchronization and Noise in Time Measurement Systems,” Universität des Saarlandes, Saarbrücken, 2022.
Export
BibTeX
@phdthesis{Attilaphd2022, TITLE = {On Time, Time Synchronization and Noise in Time Measurement Systems}, AUTHOR = {Kinali-Dogan, Attila}, LANGUAGE = {eng}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, }
Endnote
%0 Thesis %A Kinali-Dogan, Attila %Y Lenzen, Christoph %A referee: Mehlhorn, Kurt %A referee: Vernotte, Francoise %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Time, Time Synchronization and Noise in Time Measurement Systems : %G eng %U http://hdl.handle.net/21.11116/0000-000B-5436-A %I Universität des Saarlandes %C Saarbrücken %D 2022 %P 140 p. %V phd %9 phd
[26]
S. Kisfaludi-Bak, J. Nederlof, and K. Wegrzycki, “A Gap-ETH-Tight Approximation Scheme for Euclidean TSP,” in FOCS 2021, IEEE 62nd Annual Symposium on Foundations of Computer Science, Denver, CO, USA (Virtual Conference), 2022.
Export
BibTeX
@inproceedings{Kisfaludi-Bak_FOCS21, TITLE = {A {G}ap-{ETH}-Tight Approximation Scheme for {E}uclidean {TSP}}, AUTHOR = {Kisfaludi-Bak, S{\'a}ndor and Nederlof, Jesper and Wegrzycki, Karol}, LANGUAGE = {eng}, ISBN = {978-1-6654-2055-6}, DOI = {10.1109/FOCS52979.2021.00043}, PUBLISHER = {IEEE}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {FOCS 2021, IEEE 62nd Annual Symposium on Foundations of Computer Science}, PAGES = {351--362}, ADDRESS = {Denver, CO, USA (Virtual Conference)}, }
Endnote
%0 Conference Proceedings %A Kisfaludi-Bak, Sándor %A Nederlof, Jesper %A Wegrzycki, Karol %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Gap-ETH-Tight Approximation Scheme for Euclidean TSP : %G eng %U http://hdl.handle.net/21.11116/0000-000A-C557-6 %R 10.1109/FOCS52979.2021.00043 %D 2022 %B IEEE 62nd Annual Symposium on Foundations of Computer Science %Z date of event: 2022-02-07 - 2022-02-10 %C Denver, CO, USA (Virtual Conference) %B FOCS 2021 %P 351 - 362 %I IEEE %@ 978-1-6654-2055-6
[27]
R. Krithika, R. Sharma, and P. Tale, “The Complexity of Contracting Bipartite Graphs into Small Cycles,” in Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany, 2022.
Export
BibTeX
@inproceedings{KrithikaWG22, TITLE = {The Complexity of Contracting Bipartite Graphs into Small Cycles}, AUTHOR = {Krithika, R. and Sharma, Roohani and Tale, Prafullkumar}, LANGUAGE = {eng}, ISBN = {978-3-031-15913-8}, DOI = {10.1007/978-3-031-15914-5_26}, PUBLISHER = {Springer}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, BOOKTITLE = {Graph-Theoretic Concepts in Computer Science (WG 2022)}, EDITOR = {Bekos, Michael A. and Kaufmann, Michael}, PAGES = {356--369}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {13453}, ADDRESS = {T{\"u}bingen, Germany}, }
Endnote
%0 Conference Proceedings %A Krithika, R. %A Sharma, Roohani %A Tale, Prafullkumar %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Complexity of Contracting Bipartite Graphs into Small Cycles : %G eng %U http://hdl.handle.net/21.11116/0000-000B-5928-5 %R 10.1007/978-3-031-15914-5_26 %D 2022 %B 48th International Workshop on Graph-Theoretic Concepts in Computer Science %Z date of event: 2022-06-22 - 2022-06-24 %C Tübingen, Germany %B Graph-Theoretic Concepts in Computer Science %E Bekos, Michael A.; Kaufmann, Michael %P 356 - 369 %I Springer %@ 978-3-031-15913-8 %B Lecture Notes in Computer Science %N 13453
[28]
B. Ray Chaudhury, Y. K. Cheung, J. Garg, N. Garg, M. Hoefer, and K. Mehlhorn, “Fair Division of Indivisible Goods for a Class of Concave Valuations,” Journal of Artificial Intelligence Research, vol. 74, 2022.
Export
BibTeX
@article{RayChaudhury22, TITLE = {Fair Division of Indivisible Goods for a Class of Concave Valuations}, AUTHOR = {Ray Chaudhury, Bhaskar and Cheung, Yun Kuen and Garg, Jugal and Garg, Naveen and Hoefer, Martin and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISSN = {1076-9757}, DOI = {10.1613/jair.1.12911}, PUBLISHER = {AI Access Foundation}, ADDRESS = {S.l.}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Artificial Intelligence Research}, VOLUME = {74}, PAGES = {111--142}, }
Endnote
%0 Journal Article %A Ray Chaudhury, Bhaskar %A Cheung, Yun Kuen %A Garg, Jugal %A Garg, Naveen %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fair Division of Indivisible Goods for a Class of Concave Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-000A-9DB8-6 %R 10.1613/jair.1.12911 %7 2022 %D 2022 %J Journal of Artificial Intelligence Research %V 74 %& 111 %P 111 - 142 %I AI Access Foundation %C S.l. %@ false
[29]
B. Wiederhake, “Pulse Propagation, Graph Cover, and Packet Forwarding,” Universität des Saarlandes, Saarbrücken, 2022.
Abstract
We study distributed systems, with a particular focus on graph problems and fault<br>tolerance.<br>Fault-tolerance in a microprocessor or even System-on-Chip can be improved by using<br>a fault-tolerant pulse propagation design. The existing design TRIX achieves this goal<br>by being a distributed system consisting of very simple nodes. We show that even in<br>the typical mode of operation without faults, TRIX performs significantly better than a<br>regular wire or clock tree: Statistical evaluation of our simulated experiments show that<br>we achieve a skew with standard deviation of O(log log H), where H is the height of the<br>TRIX grid.<br>The distance-r generalization of classic graph problems can give us insights on how<br>distance affects hardness of a problem. For the distance-r dominating set problem, we<br>present both an algorithmic upper and unconditional lower bound for any graph class<br>with certain high-girth and sparseness criteria. In particular, our algorithm achieves a<br>O(r · f(r))-approximation in time O(r), where f is the expansion function, which correlates<br>with density. For constant r, this implies a constant approximation factor, in constant<br>time. We also show that no algorithm can achieve a (2r + 1 − δ)-approximation for any<br>δ > 0 in time O(r), not even on the class of cycles of girth at least 5r. Furthermore, we<br>extend the algorithm to related graph cover problems and even to a different execution<br>model.<br>Furthermore, we investigate the problem of packet forwarding, which addresses the<br>question of how and when best to forward packets in a distributed system. These packets<br>are injected by an adversary. We build on the existing algorithm OED to handle more<br>than a single destination. In particular, we show that buffers of size O(log n) are sufficient<br>for this algorithm, in contrast to O(n) for the naive approach.
Export
BibTeX
@phdthesis{Wiederhakephd2021, TITLE = {Pulse Propagation, Graph Cover, and Packet Forwarding}, AUTHOR = {Wiederhake, Ben}, LANGUAGE = {eng}, URL = {nbn:de:bsz:291--ds-366085}, DOI = {10.22028/D291-36608}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2022}, MARGINALMARK = {$\bullet$}, DATE = {2022}, ABSTRACT = {We study distributed systems, with a particular focus on graph problems and fault<br>tolerance.<br>Fault-tolerance in a microprocessor or even System-on-Chip can be improved by using<br>a fault-tolerant pulse propagation design. The existing design TRIX achieves this goal<br>by being a distributed system consisting of very simple nodes. We show that even in<br>the typical mode of operation without faults, TRIX performs significantly better than a<br>regular wire or clock tree: Statistical evaluation of our simulated experiments show that<br>we achieve a skew with standard deviation of O(log log H), where H is the height of the<br>TRIX grid.<br>The distance-r generalization of classic graph problems can give us insights on how<br>distance affects hardness of a problem. For the distance-r dominating set problem, we<br>present both an algorithmic upper and unconditional lower bound for any graph class<br>with certain high-girth and sparseness criteria. In particular, our algorithm achieves a<br>O(r &#183; f(r))-approximation in time O(r), where f is the expansion function, which correlates<br>with density. For constant r, this implies a constant approximation factor, in constant<br>time. We also show that no algorithm can achieve a (2r + 1 {\textminus} $\delta$)-approximation for any<br>$\delta$ > 0 in time O(r), not even on the class of cycles of girth at least 5r. Furthermore, we<br>extend the algorithm to related graph cover problems and even to a different execution<br>model.<br>Furthermore, we investigate the problem of packet forwarding, which addresses the<br>question of how and when best to forward packets in a distributed system. These packets<br>are injected by an adversary. We build on the existing algorithm OED to handle more<br>than a single destination. In particular, we show that buffers of size O(log n) are sufficient<br>for this algorithm, in contrast to O(n) for the naive approach.}, }
Endnote
%0 Thesis %A Wiederhake, Ben %Y Lenzen, Christoph %A referee: Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Pulse Propagation, Graph Cover, and Packet Forwarding : %G eng %U http://hdl.handle.net/21.11116/0000-000A-CEBE-9 %R 10.22028/D291-36608 %U nbn:de:bsz:291--ds-366085 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2022 %P 83 p. %V phd %9 phd %X We study distributed systems, with a particular focus on graph problems and fault<br>tolerance.<br>Fault-tolerance in a microprocessor or even System-on-Chip can be improved by using<br>a fault-tolerant pulse propagation design. The existing design TRIX achieves this goal<br>by being a distributed system consisting of very simple nodes. We show that even in<br>the typical mode of operation without faults, TRIX performs significantly better than a<br>regular wire or clock tree: Statistical evaluation of our simulated experiments show that<br>we achieve a skew with standard deviation of O(log log H), where H is the height of the<br>TRIX grid.<br>The distance-r generalization of classic graph problems can give us insights on how<br>distance affects hardness of a problem. For the distance-r dominating set problem, we<br>present both an algorithmic upper and unconditional lower bound for any graph class<br>with certain high-girth and sparseness criteria. In particular, our algorithm achieves a<br>O(r &#183; f(r))-approximation in time O(r), where f is the expansion function, which correlates<br>with density. For constant r, this implies a constant approximation factor, in constant<br>time. We also show that no algorithm can achieve a (2r + 1 &#8722; &#948;)-approximation for any<br>&#948; > 0 in time O(r), not even on the class of cycles of girth at least 5r. Furthermore, we<br>extend the algorithm to related graph cover problems and even to a different execution<br>model.<br>Furthermore, we investigate the problem of packet forwarding, which addresses the<br>question of how and when best to forward packets in a distributed system. These packets<br>are injected by an adversary. We build on the existing algorithm OED to handle more<br>than a single destination. In particular, we show that buffers of size O(log n) are sufficient<br>for this algorithm, in contrast to O(n) for the naive approach. %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33316