Current Year

[1]
A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay, “SETH-Based Lower Bounds for Subset Sum and Bicriteria Path,” 2017. [Online]. Available: http://arxiv.org/abs/1704.04546. (arXiv: 1704.04546)
Abstract
Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. One of the most intriguing open problems in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial $O^{*}(T)$-time algorithm for Subset-Sum on $n$ numbers and target $T$ cannot be improved to time $T^{1-\varepsilon}\cdot 2^{o(n)}$ for any $\varepsilon>0$, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of $N$ given instances of Subset-Sum is a YES instance requires time $(N T)^{1-o(1)}$. As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: On graphs with $m$ edges and edge lengths bounded by $L$, we show that the $O(Lm)$ pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to $\tilde{O}(L+m)$, in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).
Export
BibTeX
@online{DBLP:journals/corr/AbboudBHS17, 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}, URL = {http://arxiv.org/abs/1704.04546}, EPRINT = {1704.04546}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. One of the most intriguing open problems in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial $O^{*}(T)$-time algorithm for Subset-Sum on $n$ numbers and target $T$ cannot be improved to time $T^{1-\varepsilon}\cdot 2^{o(n)}$ for any $\varepsilon>0$, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of $N$ given instances of Subset-Sum is a YES instance requires time $(N T)^{1-o(1)}$. As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: On graphs with $m$ edges and edge lengths bounded by $L$, we show that the $O(Lm)$ pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to $\tilde{O}(L+m)$, in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).}, }
Endnote
%0 Report %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/11858/00-001M-0000-002D-89E5-3 %U http://arxiv.org/abs/1704.04546 %D 2017 %X Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. One of the most intriguing open problems in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial $O^{*}(T)$-time algorithm for Subset-Sum on $n$ numbers and target $T$ cannot be improved to time $T^{1-\varepsilon}\cdot 2^{o(n)}$ for any $\varepsilon>0$, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of $N$ given instances of Subset-Sum is a YES instance requires time $(N T)^{1-o(1)}$. As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: On graphs with $m$ edges and edge lengths bounded by $L$, we show that the $O(Lm)$ pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to $\tilde{O}(L+m)$, in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017). %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC
[2]
I. Abraham, S. Chechik, and S. Krinninger, “Fully dynamic all-pairs shortest paths with worst-case update-time,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{AbrahamCK17, TITLE = {Fully dynamic all-pairs shortest paths with worst-case update-time}, AUTHOR = {Abraham, Ittai and Chechik, Shiri and Krinninger, Sebastian}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.28}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {440--452}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Abraham, Ittai %A Chechik, Shiri %A Krinninger, Sebastian %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fully dynamic all-pairs shortest paths with worst-case update-time : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-52D0-1 %R 10.1137/1.9781611974782.28 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 440 - 452 %I SIAM %@ 978-1-61197-478-2
[3]
S. Anand, K. Bringmann, T. Friedrich, N. Garg, and A. Kumar, “Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines,” Algorithmica, vol. 77, no. 2, 2017.
Export
BibTeX
@article{DBLP:journals/algorithmica/0002B0G017, TITLE = {Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines}, AUTHOR = {Anand, S. and Bringmann, Karl and Friedrich, Tobias and Garg, Naveen and Kumar, Amit}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-015-0082-y}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Algorithmica}, VOLUME = {77}, NUMBER = {2}, PAGES = {515--536}, }
Endnote
%0 Journal Article %A Anand, S. %A Bringmann, Karl %A Friedrich, Tobias %A Garg, Naveen %A Kumar, Amit %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Discrete Optimization, MPI for Informatics, Max Planck Society 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 Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5527-9 %R 10.1007/s00453-015-0082-y %7 2015 %D 2017 %J Algorithmica %V 77 %N 2 %& 515 %P 515 - 536 %I Springer-Verlag %C New York, NY %@ false
[4]
A. Antoniadis, P. Kling, S. Ott, and S. Riechers, “Continuous Speed Scaling with Variability: A simple and Direct Approach,” Theoretical Computer Science, vol. 678, 2017.
Export
BibTeX
@article{Antoniadis2017, TITLE = {Continuous Speed Scaling with Variability: {A} simple and Direct Approach}, AUTHOR = {Antoniadis, Antonios and Kling, Peter and Ott, Sebastian and Riechers, S{\"o}ren}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2017.03.021}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Theoretical Computer Science}, VOLUME = {678}, PAGES = {1--13}, }
Endnote
%0 Journal Article %A Antoniadis, Antonios %A Kling, Peter %A Ott, Sebastian %A Riechers, Sören %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Continuous Speed Scaling with Variability: A simple and Direct Approach : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-7857-F %R 10.1016/j.tcs.2017.03.021 %7 2017 %D 2017 %J Theoretical Computer Science %V 678 %& 1 %P 1 - 13 %I Elsevier %C Amsterdam %@ false
[5]
Y. Azar, M. Hoefer, I. Maor, R. Reiffenhäuser, and B. Vöcking, “Truthful Mechanism Design via Correlated Tree Rounding,” Mathematical Programming / A, vol. 163, no. 1–2, 2017.
Export
BibTeX
@article{Azar2017, TITLE = {Truthful Mechanism Design via Correlated Tree Rounding}, AUTHOR = {Azar, Yossi and Hoefer, Martin and Maor, Idan and Reiffenh{\"a}user, Rebecca and V{\"o}cking, Berthold}, LANGUAGE = {eng}, ISSN = {0025-5610}, DOI = {10.1007/s10107-016-1068-5}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Mathematical Programming / A}, VOLUME = {163}, NUMBER = {1-2}, PAGES = {445--469}, }
Endnote
%0 Journal Article %A Azar, Yossi %A Hoefer, Martin %A Maor, Idan %A Reiffenhäuser, Rebecca %A Vöcking, Berthold %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Truthful Mechanism Design via Correlated Tree Rounding : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-326B-A %R 10.1007/s10107-016-1068-5 %7 2016-09-10 %D 2017 %J Mathematical Programming / A %V 163 %N 1-2 %& 445 %P 445 - 469 %I Springer %C New York, NY %@ false
[6]
L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan, “Find Your Place: Simple Distributed Algorithms for Community Detection,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{BCNPT17, TITLE = {Find Your Place: {S}imple Distributed Algorithms for Community Detection}, AUTHOR = {Becchetti, Luca and Clementi, Andrea and Natale, Emanuele and Pasquale, Francesco and Trevisan, Luca}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.59}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {940--959}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Becchetti, Luca %A Clementi, Andrea %A Natale, Emanuele %A Pasquale, Francesco %A Trevisan, Luca %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Find Your Place: Simple Distributed Algorithms for Community Detection : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5877-A %R 10.1137/1.9781611974782.59 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 940 - 959 %I SIAM
[7]
R. Becker, M. Sagraloff, V. Sharma, and C. Yap, “A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration,” Journal of Symbolic Computation. (Accepted/in press)
Export
BibTeX
@article{Becker2017JSC, TITLE = {A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the {Pellet} Test and {Newton} Iteration}, AUTHOR = {Becker, Ruben and Sagraloff, Michael and Sharma, Vikram and Yap, Chee}, LANGUAGE = {eng}, ISSN = {0747-7171}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Symbolic Computation}, }
Endnote
%0 Journal Article %A Becker, Ruben %A Sagraloff, Michael %A Sharma, Vikram %A Yap, Chee %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5717-8 %D 2017 %J Journal of Symbolic Computation %I Elsevier %C Amsterdam %@ false
[8]
F. Benhamouda, T. Lepoint, C. Mathieu, and H. Zhou, “Optimization of Bootstrapping in Circuits,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.160, TITLE = {Optimization of Bootstrapping in Circuits}, AUTHOR = {Benhamouda, Fabrice and Lepoint, Tancr{\`e}de and Mathieu, Claire and Zhou, Hang}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.160}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {2423--2433}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Benhamouda, Fabrice %A Lepoint, Tancrède %A Mathieu, Claire %A Zhou, Hang %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Optimization of Bootstrapping in Circuits : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4EBE-A %R 10.1137/1.9781611974782.160 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 2423 - 2433 %I SIAM %@ 978-1-61197-478-2
[9]
O. Beyersdorff, L. Chew, and K. Sreenivasaiah, “A Game Characterisation of Tree-like Q-Resolution Size,” Journal of Computer and System Sciences, vol. In Press, 2017.
Export
BibTeX
@article{Beyersdorff2017, TITLE = {A Game Characterisation of Tree-like {Q-Resolution} Size}, AUTHOR = {Beyersdorff, Olaf and Chew, Leroy and Sreenivasaiah, Karteek}, LANGUAGE = {eng}, ISSN = {0022-0000}, DOI = {10.1016/j.jcss.2016.11.011}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {In Press}, }
Endnote
%0 Journal Article %A Beyersdorff, Olaf %A Chew, Leroy %A Sreenivasaiah, Karteek %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Game Characterisation of Tree-like Q-Resolution Size : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5F80-F %R 10.1016/j.jcss.2016.11.011 %7 2017 %D 2017 %J Journal of Computer and System Sciences %V In Press %I Elsevier %C Amsterdam %@ false
[10]
L. Boczkowski, A. Korman, and E. Natale, “Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{BKN17, TITLE = {Minimizing Message Size in Stochastic Communication Patterns: {F}ast Self-Stabilizing Protocols with 3 bits}, AUTHOR = {Boczkowski, Lucas and Korman, Amos and Natale, Emanuele}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.168}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {2540--2559}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Boczkowski, Lucas %A Korman, Amos %A Natale, Emanuele %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-587B-2 %R 10.1137/1.9781611974782.168 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 2540 - 2559 %I SIAM
[11]
J.-D. Boissonnat, R. Dyer, and A. Ghosh, “Delaunay Triangulation of Manifolds,” Foundations of Computational Mathematics, vol. First Online, 2017.
Export
BibTeX
@article{Boissonnat2017, TITLE = {Delaunay Triangulation of Manifolds}, AUTHOR = {Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit}, LANGUAGE = {eng}, ISSN = {1615-3375}, DOI = {10.1007/s10208-017-9344-1}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Foundations of Computational Mathematics}, VOLUME = {First Online}, PAGES = {1--33}, }
Endnote
%0 Journal Article %A Boissonnat, Jean-Daniel %A Dyer, Ramsay %A Ghosh, Arijit %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Delaunay Triangulation of Manifolds : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-7945-0 %R 10.1007/s10208-017-9344-1 %7 2017-02-01 %D 2017 %8 01.02.2017 %J Foundations of Computational Mathematics %V First Online %& 1 %P 1 - 33 %I Springer %C New York, NY %@ false
[12]
K. Bringmann, “A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{DBLP:conf/soda/Bringmann17, TITLE = {A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum}, AUTHOR = {Bringmann, Karl}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.69}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {1073--1084}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5522-4 %R 10.1137/1.9781611974782.69 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 1073 - 1084 %I SIAM
[13]
K. Bringmann, P. Gawrychowski, S. Mozes, and O. Weimann, “Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can),” 2017. [Online]. Available: http://arxiv.org/abs/1703.08940. (arXiv: 1703.08940)
Abstract
The edit distance between two rooted ordered trees with $n$ nodes labeled from an alphabet~$\Sigma$ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on a similar dynamic programming solution as string edit distance. In this paper we show that a truly subcubic $O(n^{3-\varepsilon})$ time algorithm for tree edit distance is unlikely: For $|\Sigma| = \Omega(n)$, a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For $|\Sigma| = O(1)$, a truly subcubic algorithm for tree edit distance implies an $O(n^{k-\varepsilon})$ algorithm for finding a maximum weight $k$-clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk STOC'15] whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.
Export
BibTeX
@online{DBLP:journals/corr/BringmannGMW17, TITLE = {Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless {APSP} can)}, AUTHOR = {Bringmann, Karl and Gawrychowski, Pawe{\l} and Mozes, Shay and Weimann, Oren}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1703.08940}, EPRINT = {1703.08940}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The edit distance between two rooted ordered trees with $n$ nodes labeled from an alphabet~$\Sigma$ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on a similar dynamic programming solution as string edit distance. In this paper we show that a truly subcubic $O(n^{3-\varepsilon})$ time algorithm for tree edit distance is unlikely: For $|\Sigma| = \Omega(n)$, a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For $|\Sigma| = O(1)$, a truly subcubic algorithm for tree edit distance implies an $O(n^{k-\varepsilon})$ algorithm for finding a maximum weight $k$-clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk STOC'15] whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.}, }
Endnote
%0 Report %A Bringmann, Karl %A Gawrychowski, Paweł %A Mozes, Shay %A Weimann, Oren %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can) : %O Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless {APSP} can) %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8A70-3 %U http://arxiv.org/abs/1703.08940 %D 2017 %X The edit distance between two rooted ordered trees with $n$ nodes labeled from an alphabet~$\Sigma$ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on a similar dynamic programming solution as string edit distance. In this paper we show that a truly subcubic $O(n^{3-\varepsilon})$ time algorithm for tree edit distance is unlikely: For $|\Sigma| = \Omega(n)$, a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For $|\Sigma| = O(1)$, a truly subcubic algorithm for tree edit distance implies an $O(n^{k-\varepsilon})$ algorithm for finding a maximum weight $k$-clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk STOC'15] whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems. %K Computer Science, Data Structures and Algorithms, cs.DS
[14]
K. Bringmann, S. Cabello, and M. Emmerich, “Maximum Volume Subset Selection for Anchored Boxes,” in 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia, 2017.
Export
BibTeX
@inproceedings{bringmann:scg, TITLE = {Maximum Volume Subset Selection for Anchored Boxes}, AUTHOR = {Bringmann, Karl and Cabello, Sergio and Emmerich, Michael}, LANGUAGE = {eng}, ISBN = {978-3-95977-038-5}, URL = {urn:nbn:de:0030-drops-72011}, DOI = {10.4230/LIPIcs.SoCG.2017.22}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {33rd International Symposium on Computational Geometry (SoCG 2017)}, EDITOR = {Aranov, Boris and Katz, Matthew J.}, PAGES = {1--15}, EID = {22}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {77}, ADDRESS = {Brisbane, Australia}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Cabello, Sergio %A Emmerich, Michael %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Maximum Volume Subset Selection for Anchored Boxes : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-7D6F-9 %U urn:nbn:de:0030-drops-72011 %R 10.4230/LIPIcs.SoCG.2017.22 %D 2017 %B 33rd International Symposium on Computational Geometry %Z date of event: 2017-07-04 - 2017-07-07 %C Brisbane, Australia %B 33rd International Symposium on Computational Geometry %E Aranov, Boris; Katz, Matthew J. %P 1 - 15 %Z sequence number: 22 %I Schloss Dagstuhl %@ 978-3-95977-038-5 %B Leibniz International Proceedings in Informatics %N 77 %U http://drops.dagstuhl.de/doku/urheberrecht1.htmlhttp://drops.dagstuhl.de/opus/volltexte/2017/7201/
[15]
K. Bringmann, T. Dueholm Hansen, and S. Krinninger, “Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs,” in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Warsaw, Poland. (Accepted/in press)
Export
BibTeX
@inproceedings{BringmannICALP2017, TITLE = {Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs}, AUTHOR = {Bringmann, Karl and Dueholm Hansen, Thomas and Krinninger, Sebastian}, LANGUAGE = {eng}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, SERIES = {Leibniz International Proceedings in Informatics}, ADDRESS = {Warsaw, Poland}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Dueholm Hansen, Thomas %A Krinninger, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-89C4-F %D 2017 %B 44th International Colloquium on Automata, Languages, and Programming %Z date of event: 2017-07-10 - 2017-07-14 %C Warsaw, Poland %B 44th International Colloquium on Automata, Languages, and Programming %I Schloss Dagstuhl %B Leibniz International Proceedings in Informatics
[16]
K. Bringmann, T. Dueholm Hansen, and S. Krinninger, “Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs,” 2017. [Online]. Available: http://arxiv.org/abs/1704.08122. (arXiv: 1704.08122)
Abstract
We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with $ n $ nodes and $ m $ edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We further demonstrate how to obtain both an algorithm with running time $ n^3 / 2^{\Omega{(\sqrt{\log n})}} $ on general graphs and an algorithm with running time $ \tilde O (n) $ on constant treewidth graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest.
Export
BibTeX
@online{DBLP:journals/corr/BringmannHK17, TITLE = {Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs}, AUTHOR = {Bringmann, Karl and Dueholm Hansen, Thomas and Krinninger, Sebastian}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1704.08122}, EPRINT = {1704.08122}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with $ n $ nodes and $ m $ edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We further demonstrate how to obtain both an algorithm with running time $ n^3 / 2^{\Omega{(\sqrt{\log n})}} $ on general graphs and an algorithm with running time $ \tilde O (n) $ on constant treewidth graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest.}, }
Endnote
%0 Report %A Bringmann, Karl %A Dueholm Hansen, Thomas %A Krinninger, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-89BC-3 %U http://arxiv.org/abs/1704.08122 %D 2017 %X We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with $ n $ nodes and $ m $ edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We further demonstrate how to obtain both an algorithm with running time $ n^3 / 2^{\Omega{(\sqrt{\log n})}} $ on general graphs and an algorithm with running time $ \tilde O (n) $ on constant treewidth graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest. %K Computer Science, Data Structures and Algorithms, cs.DS
[17]
K. Bringmann and S. Krinninger, “A Note on Hardness of Diameter Approximation,” 2017. [Online]. Available: http://arxiv.org/abs/1705.02127. (arXiv: 1705.02127)
Abstract
We revisit the hardness of approximating the diameter of a network. In the CONGEST model, $ \tilde \Omega (n) $ rounds are necessary to compute the diameter [Frischknecht et al. SODA'12]. Abboud et al. DISC 2016 extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer $ 1 \leq \ell \leq \operatorname{polylog} (n) $, distinguishing between networks of diameter $ 4 \ell + 2 $ and $ 6 \ell + 1 $ requires $ \tilde \Omega (n) $ rounds. We slightly tighten this result by showing that even distinguishing between diameter $ 2 \ell + 1 $ and $ 3 \ell + 1 $ requires $ \tilde \Omega (n) $ rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition. This is suited for teaching both the lower bound in the CONGEST model and the conditional lower bound in the RAM model.
Export
BibTeX
@online{DBLP:journals/corr/BringmannK17, TITLE = {A Note on Hardness of Diameter Approximation}, AUTHOR = {Bringmann, Karl and Krinninger, Sebastian}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1705.02127}, EPRINT = {1705.02127}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We revisit the hardness of approximating the diameter of a network. In the CONGEST model, $ \tilde \Omega (n) $ rounds are necessary to compute the diameter [Frischknecht et al. SODA'12]. Abboud et al. DISC 2016 extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer $ 1 \leq \ell \leq \operatorname{polylog} (n) $, distinguishing between networks of diameter $ 4 \ell + 2 $ and $ 6 \ell + 1 $ requires $ \tilde \Omega (n) $ rounds. We slightly tighten this result by showing that even distinguishing between diameter $ 2 \ell + 1 $ and $ 3 \ell + 1 $ requires $ \tilde \Omega (n) $ rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition. This is suited for teaching both the lower bound in the CONGEST model and the conditional lower bound in the RAM model.}, }
Endnote
%0 Report %A Bringmann, Karl %A Krinninger, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Note on Hardness of Diameter Approximation : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-89B7-D %U http://arxiv.org/abs/1705.02127 %D 2017 %X We revisit the hardness of approximating the diameter of a network. In the CONGEST model, $ \tilde \Omega (n) $ rounds are necessary to compute the diameter [Frischknecht et al. SODA'12]. Abboud et al. DISC 2016 extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer $ 1 \leq \ell \leq \operatorname{polylog} (n) $, distinguishing between networks of diameter $ 4 \ell + 2 $ and $ 6 \ell + 1 $ requires $ \tilde \Omega (n) $ rounds. We slightly tighten this result by showing that even distinguishing between diameter $ 2 \ell + 1 $ and $ 3 \ell + 1 $ requires $ \tilde \Omega (n) $ rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition. This is suited for teaching both the lower bound in the CONGEST model and the conditional lower bound in the RAM model. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
[18]
K. Bringmann, C. Ikenmeyer, and J. Zuiddam, “On Algebraic Branching Programs of Small Width,” Electronic Colloquium on Computational Complexity (ECCC) : Report Series, vol. 34 (Revision 1), 2017.
Export
BibTeX
@article{BringmannECCC2017, TITLE = {On Algebraic Branching Programs of Small Width}, AUTHOR = {Bringmann, Karl and Ikenmeyer, Christian and Zuiddam, Jeroen}, LANGUAGE = {eng}, ISSN = {1433-8092}, PUBLISHER = {Hasso-Plattner-Institut f{\"u}r Softwaretechnik GmbH}, ADDRESS = {Potsdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Electronic Colloquium on Computational Complexity (ECCC) : Report Series}, VOLUME = {34 (Revision 1)}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A Ikenmeyer, Christian %A Zuiddam, Jeroen %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Algebraic Branching Programs of Small Width : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-89B2-8 %7 2017 %D 2017 %J Electronic Colloquium on Computational Complexity (ECCC) : Report Series %V 34 (Revision 1) %I Hasso-Plattner-Institut für Softwaretechnik GmbH %C Potsdam %@ false %U https://eccc.weizmann.ac.il/report/2017/034/
[19]
K. Bringmann, C. Ikenmeyer, and J. Zuiddam, “On Algebraic Branching Programs of Small Width,” 2017. [Online]. Available: http://arxiv.org/abs/1702.05328. (arXiv: 1702.05328)
Abstract
In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.
Export
BibTeX
@online{BringmannArXiv2017, TITLE = {On Algebraic Branching Programs of Small Width}, AUTHOR = {Bringmann, Karl and Ikenmeyer, Christian and Zuiddam, Jeroen}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1702.05328}, EPRINT = {1702.05328}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.}, }
Endnote
%0 Report %A Bringmann, Karl %A Ikenmeyer, Christian %A Zuiddam, Jeroen %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Algebraic Branching Programs of Small Width : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-89A4-8 %U http://arxiv.org/abs/1702.05328 %D 2017 %X In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs. %K Computer Science, Computational Complexity, cs.CC,
[20]
J. Bund, C. Lenzen, and M. Medina, “Near-Optimal Metastability-Containing Sorting Networks,” in Proceedings of the 2017 Design, Automation & Test in Europe (DATE 2017), Lausanne, Switzerland, 2017.
Export
BibTeX
@inproceedings{BundDATE2017, TITLE = {Near-Optimal Metastability-Containing Sorting Networks}, AUTHOR = {Bund, Johannes and Lenzen, Christoph and Medina, Moti}, LANGUAGE = {eng}, ISBN = {978-1-5090-5826-6}, DOI = {10.23919/DATE.2017.7926987}, PUBLISHER = {IEEE}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the 2017 Design, Automation \& Test in Europe (DATE 2017)}, PAGES = {226--231}, ADDRESS = {Lausanne, Switzerland}, }
Endnote
%0 Conference Proceedings %A Bund, Johannes %A Lenzen, Christoph %A Medina, Moti %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Near-Optimal Metastability-Containing Sorting Networks : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-571A-2 %R 10.23919/DATE.2017.7926987 %D 2017 %B Design, Automation & Test in Europe Conference & Exhibition %Z date of event: 2017-03-27 - 2017-03-31 %C Lausanne, Switzerland %B Proceedings of the 2017 Design, Automation & Test in Europe %P 226 - 231 %I IEEE %@ 978-1-5090-5826-6
[21]
P. Bürgisser, C. Ikenmeyer, and J. Hüttenhain, “Permanent versus Determinant: Not via Saturations,” Proceedings of the American Mathematical Society, vol. 145, 2017.
Export
BibTeX
@article{BHI:17, TITLE = {Permanent versus Determinant: {N}ot via Saturations}, AUTHOR = {B{\"u}rgisser, Peter and Ikenmeyer, Christian and H{\"u}ttenhain, Jesko}, LANGUAGE = {eng}, ISSN = {0002-9939}, DOI = {10.1090/proc/13310}, PUBLISHER = {American Mathematical Society}, ADDRESS = {Providence, R.I. [etc.]}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Proceedings of the American Mathematical Society}, VOLUME = {145}, PAGES = {1247--1258}, }
Endnote
%0 Journal Article %A Bürgisser, Peter %A Ikenmeyer, Christian %A Hüttenhain, Jesko %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Permanent versus Determinant: Not via Saturations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4F48-A %R 10.1090/proc/13310 %7 2017 %D 2017 %J Proceedings of the American Mathematical Society %V 145 %& 1247 %P 1247 - 1258 %I American Mathematical Society %C Providence, R.I. [etc.] %@ false
[22]
P. Bürgisser and C. Ikenmeyer, “Fundamental Invariants of Orbit Closures,” Journal of Algebra, vol. 477, 2017.
Export
BibTeX
@article{BI:17, TITLE = {Fundamental Invariants of Orbit Closures}, AUTHOR = {B{\"u}rgisser, Peter and Ikenmeyer, Christian}, LANGUAGE = {eng}, ISSN = {0021-8693}, DOI = {10.1016/j.jalgebra.2016.12.035}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Algebra}, VOLUME = {477}, PAGES = {390--434}, }
Endnote
%0 Journal Article %A Bürgisser, Peter %A Ikenmeyer, Christian %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fundamental Invariants of Orbit Closures : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4F2E-8 %R 10.1016/j.jalgebra.2016.12.035 %7 2017-01-17 %D 2017 %J Journal of Algebra %V 477 %& 390 %P 390 - 434 %I Elsevier %C Amsterdam %@ false
[23]
P. Chalermsook and A. Schmid, “Finding Triangles for Maximum Planar Subgraphs,” in 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), Hsinchu, Taiwan. (Accepted/in press)
Export
BibTeX
@inproceedings{PCAS2017, TITLE = {Finding Triangles for Maximum Planar Subgraphs}, AUTHOR = {Chalermsook, Parinya and Schmid, Andreas}, LANGUAGE = {eng}, PUBLISHER = {Springer}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017)}, ADDRESS = {Hsinchu, Taiwan}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Schmid, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Finding Triangles for Maximum Planar Subgraphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5DDC-F %D 2016 %B 11th International Conference and Workshops on Algorithms and Computation %Z date of event: 2017-03-29 - 2017-03-31 %C Hsinchu, Taiwan %B 11th International Conference and Workshops on Algorithms and Computation %I Springer
[24]
P. Chalermsook and D. Vaz, “New Integrality Gap Results for the Firefighters Problem on Trees,” in Approximation and Online Algorithms (WAOA 2016), Aarhus, Denmark, 2017.
Export
BibTeX
@inproceedings{Chalermsook2017, TITLE = {New Integrality Gap Results for the Firefighters Problem on Trees}, AUTHOR = {Chalermsook, Parinya and Vaz, Daniel}, LANGUAGE = {eng}, ISBN = {978-3-319-51740-7}, DOI = {10.1007/978-3-319-51741-4_6}, PUBLISHER = {Springer}, YEAR = {2016}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Approximation and Online Algorithms (WAOA 2016)}, EDITOR = {Jansen, Klaus and Mastrolilli, Monaldo}, PAGES = {65--77}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {10138}, ADDRESS = {Aarhus, Denmark}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Vaz, Daniel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New Integrality Gap Results for the Firefighters Problem on Trees : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-575B-0 %R 10.1007/978-3-319-51741-4_6 %D 2017 %B 14th Workshop on Approximation and Online Algorithms %Z date of event: 2016-08-25 - 2016-08-26 %C Aarhus, Denmark %B Approximation and Online Algorithms %E Jansen, Klaus; Mastrolilli, Monaldo %P 65 - 77 %I Springer %@ 978-3-319-51740-7 %B Lecture Notes in Computer Science %N 10138
[25]
P. Chalermsook, S. Das, B. Laekhanukit, and D. Vaz, “Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.47, TITLE = {Beyond Metric Embedding: {A}pproximating {Group Steiner Trees} on Bounded Treewidth Graphs}, AUTHOR = {Chalermsook, Parinya and Das, Syamantak and Laekhanukit, Bundit and Vaz, Daniel}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.47}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {737--751}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Das, Syamantak %A Laekhanukit, Bundit %A Vaz, Daniel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-573D-3 %R 10.1137/1.9781611974782.47 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 737 - 751 %I SIAM
[26]
L. S. Chandran, D. Issac, and A. Karrenbauer, “On the Parameterized Complexity of Biclique Cover and Partition,” in 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, 2017.
Export
BibTeX
@inproceedings{BicliqueFPT, TITLE = {On the Parameterized Complexity of Biclique Cover and Partition}, AUTHOR = {Chandran, L. Sunil and Issac, Davis and Karrenbauer, Andreas}, LANGUAGE = {eng}, ISBN = {978-3-95977-023-1}, URL = {urn:nbn:de:0030-drops-69293}, DOI = {10.4230/LIPIcs.IPEC.2016.11}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2016}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, EDITOR = {Guo, Jiong and Hermelin, Danny}, PAGES = {1--13}, EID = {11}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {63}, ADDRESS = {Aarhus, Denmark}, }
Endnote
%0 Conference Proceedings %A Chandran, L. Sunil %A Issac, Davis %A Karrenbauer, Andreas %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On the Parameterized Complexity of Biclique Cover and Partition : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-53DB-3 %R 10.4230/LIPIcs.IPEC.2016.11 %U urn:nbn:de:0030-drops-69293 %D 2017 %B 11th International Symposium on Parameterized and Exact Computation %Z date of event: 2016-08-24 - 2016-08-26 %C Aarhus, Denmark %B 11th International Symposium on Parameterized and Exact Computation %E Guo, Jiong; Hermelin, Danny %P 1 - 13 %Z sequence number: 11 %I Schloss Dagstuhl %@ 978-3-95977-023-1 %B Leibniz International Proceedings in Informatics %N 63 %U http://drops.dagstuhl.de/doku/urheberrecht1.htmlhttp://drops.dagstuhl.de/opus/volltexte/2017/6929/
[27]
M. Cygan, M. Pilipczuk, M. Pilipczuk, E. J. van Leeuwen, and M. Wrochna, “Polynomial Kernelization for Removing Induced Claws and Diamonds,” Theory of Computing Systems, vol. 60, no. 4, 2017.
Export
BibTeX
@article{CyganAlgorithmica2016, TITLE = {Polynomial Kernelization for Removing Induced Claws and Diamonds}, AUTHOR = {Cygan, Marek and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan and Wrochna, Marcin}, LANGUAGE = {eng}, ISSN = {1432-4350}, DOI = {10.1007/s00224-016-9689-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Theory of Computing Systems}, VOLUME = {60}, NUMBER = {4}, PAGES = {615--636}, }
Endnote
%0 Journal Article %A Cygan, Marek %A Pilipczuk, Marcin %A Pilipczuk, Michał %A van Leeuwen, Erik Jan %A Wrochna, Marcin %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Polynomial Kernelization for Removing Induced Claws and Diamonds : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-8606-6 %R 10.1007/s00224-016-9689-x %7 2016-06-23 %D 2017 %J Theory of Computing Systems %V 60 %N 4 %& 615 %P 615 - 636 %I Springer %C New York, NY %@ false
[28]
J. Diaz, O. Pottonen, M. Serna, and E. J. van Leeuwen, “Complexity of Metric Dimension on Planar Graphs,” Journal of Computer and System Sciences, vol. 83, no. 1, 2017.
Export
BibTeX
@article{Diaz2017, TITLE = {Complexity of Metric Dimension on Planar Graphs}, AUTHOR = {Diaz, Josep and Pottonen, Olli and Serna, Maria and van Leeuwen, Erik Jan}, ISSN = {0022-0000}, DOI = {10.1016/j.jcss.2016.06.006}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {83}, NUMBER = {1}, PAGES = {132--158}, }
Endnote
%0 Journal Article %A Diaz, Josep %A Pottonen, Olli %A Serna, Maria %A van Leeuwen, Erik Jan %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Complexity of Metric Dimension on Planar Graphs : %U http://hdl.handle.net/11858/00-001M-0000-002B-A574-5 %R 10.1016/j.jcss.2016.06.006 %7 2016 %D 2017 %J Journal of Computer and System Sciences %V 83 %N 1 %& 132 %P 132 - 158 %I Elsevier %C Amsterdam %@ false
[29]
M. Dirnberger and K. Mehlhorn, “Characterizing Networks Formed by P. Polycephalum,” Journal of Physics D: Applied Physics, vol. 50, no. 22, 2017.
Export
BibTeX
@article{Dirnberg_Mehlhorn2017, TITLE = {Characterizing networks formed by \slshape{P. polycephalum}}, AUTHOR = {Dirnberger, Michael and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISSN = {0022-3727}, DOI = {10.1088/1361-6463/aa6e7b}, PUBLISHER = {IOP Publishing}, ADDRESS = {Bristol}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Physics D: Applied Physics}, VOLUME = {50}, NUMBER = {22}, EID = {224002}, }
Endnote
%0 Journal Article %A Dirnberger, Michael %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Characterizing Networks Formed by P. Polycephalum : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-56FA-2 %R 10.1088/1361-6463/aa6e7b %7 2017 %D 2017 %J Journal of Physics D: Applied Physics %O J. Phys. D: Appl. Phys. %V 50 %N 22 %Z sequence number: 224002 %I IOP Publishing %C Bristol %@ false
[30]
M. Dirnberger, K. Mehlhorn, and T. Mehlhorn, “Introducing the Slime Mold Graph Repository,” Journal of Physics D: Applied Physics, vol. 50, no. 26, 2017.
Export
BibTeX
@article{Dirnberger2017, TITLE = {Introducing the Slime Mold Graph Repository}, AUTHOR = {Dirnberger, Michael and Mehlhorn, Kurt and Mehlhorn, Tim}, LANGUAGE = {eng}, ISSN = {0022-3727}, DOI = {10.1088/1361-6463/aa7326}, PUBLISHER = {IOP Publishing}, ADDRESS = {Bristol}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Physics D: Applied Physics}, VOLUME = {50}, NUMBER = {26}, EID = {264001}, }
Endnote
%0 Journal Article %A Dirnberger, Michael %A Mehlhorn, Kurt %A Mehlhorn, Tim %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Introducing the Slime Mold Graph Repository : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8464-B %R 10.1088/1361-6463/aa7326 %7 2017 %D 2017 %J Journal of Physics D: Applied Physics %O J. Phys. D: Appl. Phys. %V 50 %N 26 %Z sequence number: 264001 %I IOP Publishing %C Bristol %@ false
[31]
K. Dutta, A. Ghosh, B. Jartoux, and N. H. Mustafa, “Shallow Packings, Semialgebraic Set Systems, Macbeath Regions and Polynomial Partitioning,” in 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia. (Accepted/in press)
Export
BibTeX
@inproceedings{DuttaGJM-Mnets-17, TITLE = {Shallow Packings, Semialgebraic Set Systems, {Macbeath} Regions and Polynomial Partitioning}, AUTHOR = {Dutta, Kunal and Ghosh, Arijit and Jartoux, Bruno and Mustafa, Nabil H.}, LANGUAGE = {eng}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {33rd International Symposium on Computational Geometry (SoCG 2017)}, ADDRESS = {Brisbane, Australia}, }
Endnote
%0 Conference Proceedings %A Dutta, Kunal %A Ghosh, Arijit %A Jartoux, Bruno %A Mustafa, Nabil H. %+ 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 %T Shallow Packings, Semialgebraic Set Systems, Macbeath Regions and Polynomial Partitioning : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-7941-7 %D 2017 %8 12.02.2017 %B 33rd International Symposium on Computational Geometry %Z date of event: 2017-07-04 - 2017-07-07 %C Brisbane, Australia %B 33rd International Symposium on Computational Geometry
[32]
P. Dütting and T. Kesselheim, “Best-Response Dynamics in Combinatorial Auctions with Item Bidding,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.33, TITLE = {Best-Response Dynamics in Combinatorial Auctions with Item Bidding}, AUTHOR = {D{\"u}tting, Paul and Kesselheim, Thomas}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.33}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {521--533}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Dütting, Paul %A Kesselheim, Thomas %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Best-Response Dynamics in Combinatorial Auctions with Item Bidding : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4E5E-2 %R 10.1137/1.9781611974782.33 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 521 - 533 %I SIAM %@ 978-1-61197-478-2
[33]
M. Ernestus, S. Friedrichs, M. Hemmer, J. Kokemüller, A. Kröller, M. Moeini, and C. Schmidt, “Algorithms for Art Gallery Illumination,” Journal of Global Optimization, vol. 68, no. 1, 2017.
Export
BibTeX
@article{ErnestusJGO2016, TITLE = {Algorithms for Art Gallery Illumination}, AUTHOR = {Ernestus, Maximilian and Friedrichs, Stephan and Hemmer, Michael and Kokem{\"u}ller, Jan and Kr{\"o}ller, Alexander and Moeini, Mahdi and Schmidt, Christiane}, LANGUAGE = {eng}, ISSN = {0925-5001}, DOI = {10.1007/s10898-016-0452-2}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Global Optimization}, VOLUME = {68}, NUMBER = {1}, PAGES = {23--45}, }
Endnote
%0 Journal Article %A Ernestus, Maximilian %A Friedrichs, Stephan %A Hemmer, Michael %A Kokemüller, Jan %A Kröller, Alexander %A Moeini, Mahdi %A Schmidt, Christiane %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations %T Algorithms for Art Gallery Illumination : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-0B3C-1 %R 10.1007/s10898-016-0452-2 %7 2016 %D 2017 %J Journal of Global Optimization %V 68 %N 1 %& 23 %P 23 - 45 %I Springer %C New York, NY %@ false
[34]
M. Függer, C. Lenzen, and T. Polzer, “Metastability-Aware Memory-Efficient Time-to-Digital Converters,” in 23rd IEEE International Symposium on Asynchronous Circuits and Systems, San Diego, CA, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{fueggerASYNC2017, TITLE = {Metastability-Aware Memory-Efficient Time-to-Digital Converters}, AUTHOR = {F{\"u}gger, Matthias and Lenzen, Christoph and Polzer, Thomas}, LANGUAGE = {eng}, PUBLISHER = {IEEE}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {23rd IEEE International Symposium on Asynchronous Circuits and Systems}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Függer, Matthias %A Lenzen, Christoph %A Polzer, Thomas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Metastability-Aware Memory-Efficient Time-to-Digital Converters : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-80CD-D %D 2017 %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %Z date of event: 2017-05-21 - 2017-05-24 %C San Diego, CA, USA %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %I IEEE
[35]
M. Goswami, X. Gu, V. P. Pingali, and G. Telang, “Computing Teichmüller Maps Between Polygons,” Foundations of Computational Mathematics, vol. 17, no. 2, 2017.
Export
BibTeX
@article{Goswami2017, TITLE = {Computing {Teichmüller} Maps Between Polygons}, AUTHOR = {Goswami, Mayank and Gu, Xianfeng and Pingali, Vamsi P. and Telang, Gaurish}, LANGUAGE = {eng}, ISSN = {1615-3375}, DOI = {10.1007/s10208-015-9294-4}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Foundations of Computational Mathematics}, VOLUME = {17}, NUMBER = {2}, PAGES = {497--526}, }
Endnote
%0 Journal Article %A Goswami, Mayank %A Gu, Xianfeng %A Pingali, Vamsi P. %A Telang, Gaurish %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Computing Teichmüller Maps Between Polygons : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-3E48-3 %R 10.1007/s10208-015-9294-4 %7 2015-11-25 %D 2017 %J Foundations of Computational Mathematics %V 17 %N 2 %& 497 %P 497 - 526 %I Springer %C New York, NY %@ false
[36]
F. Grandoni, T. Mömke, A. Wiese, and H. Zhou, “To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.159, TITLE = {To Augment or Not to Augment: {S}olving Unsplittable Flow on a Path by Creating Slack}, AUTHOR = {Grandoni, Fabrizio and M{\"o}mke, Tobias and Wiese, Andreas and Zhou, Hang}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.159}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {2411--2422}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Grandoni, Fabrizio %A Mömke, Tobias %A Wiese, Andreas %A Zhou, Hang %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4EB5-B %R 10.1137/1.9781611974782.159 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 2411 - 2422 %I SIAM %@ 978-1-61197-478-2
[37]
S. Heydrich and A. Wiese, “Faster Approximation Schemes for the Two-dimensional Knapsack Problem,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{HeydrichW17, TITLE = {Faster Approximation Schemes for the Two-dimensional Knapsack Problem}, AUTHOR = {Heydrich, Sandy and Wiese, Andreas}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.6}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {79--98}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Heydrich, Sandy %A Wiese, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Faster Approximation Schemes for the Two-dimensional Knapsack Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-54AD-3 %R 10.1137/1.9781611974782.6 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 79 - 98 %I SIAM %@ 978-1-61197-478-2
[38]
M. Hoefer and L. Wagner, “Locally Stable Marriage with Strict Preferences,” SIAM Journal on Discrete Mathematics, vol. 31, no. 1, 2017.
Export
BibTeX
@article{HoeferWagner2017, TITLE = {Locally Stable Marriage with Strict Preferences}, AUTHOR = {Hoefer, Martin and Wagner, Lisa}, LANGUAGE = {eng}, ISSN = {0895-4801}, DOI = {10.1137/151003854}, PUBLISHER = {SIAM}, ADDRESS = {Philadelphia, Pa.}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {31}, NUMBER = {1}, PAGES = {283--316}, }
Endnote
%0 Journal Article %A Hoefer, Martin %A Wagner, Lisa %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Locally Stable Marriage with Strict Preferences : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-26B4-1 %R 10.1137/151003854 %7 2017-02-23 %D 2017 %J SIAM Journal on Discrete Mathematics %V 31 %N 1 %& 283 %P 283 - 316 %I SIAM %C Philadelphia, Pa. %@ false
[39]
M. Hoefer and B. Kodric, “Combinatorial Secretary Problems with Ordinal Information,” 2017. [Online]. Available: http://arxiv.org/abs/1702.01290. (arXiv: 1702.01290)
Abstract
The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model.
Export
BibTeX
@online{Hoefer_Kodric2017, TITLE = {Combinatorial Secretary Problems with Ordinal Information}, AUTHOR = {Hoefer, Martin and Kodric, Bojana}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1702.01290}, EPRINT = {1702.01290}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model.}, }
Endnote
%0 Report %A Hoefer, Martin %A Kodric, Bojana %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Secretary Problems with Ordinal Information : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5C63-3 %U http://arxiv.org/abs/1702.01290 %D 2017 %X The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model. %K Computer Science, Data Structures and Algorithms, cs.DS
[40]
C. Ikenmeyer and J. M. Landsberg, “On the Complexity of the Permanent in Various Computational Models,” Journal of Pure and Applied Algebra, vol. Accepted Manuscript, 2017.
Export
BibTeX
@article{IL:17, TITLE = {On the Complexity of the Permanent in Various Computational Models}, AUTHOR = {Ikenmeyer, Christian and Landsberg, J. M.}, LANGUAGE = {eng}, ISSN = {0022-4049}, DOI = {10.1016/j.jpaa.2017.02.008}, PUBLISHER = {North-Holland}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Pure and Applied Algebra}, VOLUME = {Accepted Manuscript}, }
Endnote
%0 Journal Article %A Ikenmeyer, Christian %A Landsberg, J. M. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On the Complexity of the Permanent in Various Computational Models : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4F23-D %R 10.1016/j.jpaa.2017.02.008 %7 2017-02-23 %D 2017 %8 23.02.2017 %J Journal of Pure and Applied Algebra %O J. Pure Appl. Algebra %V Accepted Manuscript %I North-Holland %C Amsterdam %@ false
[41]
G. Jindal, P. Kolev, R. Peng, and S. Sawlani, “Density Independent Algorithms for Sparsifying k-Step Random Walks,” 2017. [Online]. Available: http://arxiv.org/abs/1702.06110. (arXiv: 1702.06110)
Abstract
We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.
Export
BibTeX
@online{DBLP:journals/corr/JindalKPS17, TITLE = {Density Independent Algorithms for Sparsifying $k$-Step Random Walks}, AUTHOR = {Jindal, Gorav and Kolev, Pavel and Peng, Richard and Sawlani, Saurabh}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1702.06110}, EPRINT = {1702.06110}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.}, }
Endnote
%0 Report %A Jindal, Gorav %A Kolev, Pavel %A Peng, Richard %A Sawlani, Saurabh %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Density Independent Algorithms for Sparsifying k-Step Random Walks : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-26A6-1 %U http://arxiv.org/abs/1702.06110 %D 2017 %X We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices. %K Computer Science, Data Structures and Algorithms, cs.DS
[42]
G. Jindal and M. Sagraloff, “Efficiently Computing Real Roots of Sparse Polynomials,” 2017. [Online]. Available: http://arxiv.org/abs/1704.06979. (arXiv: 1704.06979)
Abstract
We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{R}[x]$ having $k$ non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer $L$, our algorithm returns disjoint disks $\Delta_{1},\ldots,\Delta_{s}\subset\mathbb{C}$, with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $\mu_{1},\ldots,\mu_{s}$ such that each disk $\Delta_{i}$ contains exactly $\mu_{i}$ roots of $f$ counted with multiplicity. In addition, it is ensured that each real root of $f$ is contained in one of the disks. If $f$ has only simple real roots, our algorithm can also be used to isolate all real roots. The bit complexity of our algorithm is polynomial in $k$ and $\log n$, and near-linear in $L$ and $\tau$, where $2^{-\tau}$ and $2^{\tau}$ constitute lower and upper bounds on the absolute values of the non-zero coefficients of $f$, and $n$ is the degree of $f$. For root isolation, the bit complexity is polynomial in $k$ and $\log n$, and near-linear in $\tau$ and $\log\sigma^{-1}$, where $\sigma$ denotes the separation of the real roots.
Export
BibTeX
@online{DBLP:journals/corr/JindalS17, TITLE = {Efficiently Computing Real Roots of Sparse Polynomials}, AUTHOR = {Jindal, Gorav and Sagraloff, Michael}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1704.06979}, EPRINT = {1704.06979}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{R}[x]$ having $k$ non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer $L$, our algorithm returns disjoint disks $\Delta_{1},\ldots,\Delta_{s}\subset\mathbb{C}$, with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $\mu_{1},\ldots,\mu_{s}$ such that each disk $\Delta_{i}$ contains exactly $\mu_{i}$ roots of $f$ counted with multiplicity. In addition, it is ensured that each real root of $f$ is contained in one of the disks. If $f$ has only simple real roots, our algorithm can also be used to isolate all real roots. The bit complexity of our algorithm is polynomial in $k$ and $\log n$, and near-linear in $L$ and $\tau$, where $2^{-\tau}$ and $2^{\tau}$ constitute lower and upper bounds on the absolute values of the non-zero coefficients of $f$, and $n$ is the degree of $f$. For root isolation, the bit complexity is polynomial in $k$ and $\log n$, and near-linear in $\tau$ and $\log\sigma^{-1}$, where $\sigma$ denotes the separation of the real roots.}, }
Endnote
%0 Report %A Jindal, Gorav %A Sagraloff, Michael %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Efficiently Computing Real Roots of Sparse Polynomials : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8AD1-7 %U http://arxiv.org/abs/1704.06979 %D 2017 %X We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{R}[x]$ having $k$ non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer $L$, our algorithm returns disjoint disks $\Delta_{1},\ldots,\Delta_{s}\subset\mathbb{C}$, with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $\mu_{1},\ldots,\mu_{s}$ such that each disk $\Delta_{i}$ contains exactly $\mu_{i}$ roots of $f$ counted with multiplicity. In addition, it is ensured that each real root of $f$ is contained in one of the disks. If $f$ has only simple real roots, our algorithm can also be used to isolate all real roots. The bit complexity of our algorithm is polynomial in $k$ and $\log n$, and near-linear in $L$ and $\tau$, where $2^{-\tau}$ and $2^{\tau}$ constitute lower and upper bounds on the absolute values of the non-zero coefficients of $f$, and $n$ is the degree of $f$. For root isolation, the bit complexity is polynomial in $k$ and $\log n$, and near-linear in $\tau$ and $\log\sigma^{-1}$, where $\sigma$ denotes the separation of the real roots. %K Computer Science, Symbolic Computation, cs.SC
[43]
C. Lenzen and J. Rybicki, “Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus,” 2017. [Online]. Available: http://arxiv.org/abs/1705.06173. (arXiv: 1705.06173)
Abstract
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the $n$ nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to $f<n/3$ ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem: - In the deterministic setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $\Theta(f \log f)$ bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to $\Theta(\log f)$ while retaining the same stabilisation time. - In the randomised setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We exponentially reduce the stabilisation time to $\log^{O(1)} f$ while each node broadcasts $\log^{O(1)} f$ bits per time unit. These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.
Export
BibTeX
@online{DBLP:journals/corr/LenzenR17, TITLE = {Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus}, AUTHOR = {Lenzen, Christoph and Rybicki, Joel}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1705.06173}, EPRINT = {1705.06173}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the $n$ nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to $f<n/3$ ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem: -- In the deterministic setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $\Theta(f \log f)$ bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to $\Theta(\log f)$ while retaining the same stabilisation time. -- In the randomised setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We exponentially reduce the stabilisation time to $\log^{O(1)} f$ while each node broadcasts $\log^{O(1)} f$ bits per time unit. These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.}, }
Endnote
%0 Report %A Lenzen, Christoph %A Rybicki, Joel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus : %O Self-stabilising {B}yzantine Clock Synchronisation is Almost as Easy as Consensus %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8AAA-3 %U http://arxiv.org/abs/1705.06173 %D 2017 %X We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the $n$ nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to $f<n/3$ ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem: - In the deterministic setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $\Theta(f \log f)$ bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to $\Theta(\log f)$ while retaining the same stabilisation time. - In the randomised setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We exponentially reduce the stabilisation time to $\log^{O(1)} f$ while each node broadcasts $\log^{O(1)} f$ bits per time unit. These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
[44]
C. Lenzen and R. Levi, “A Local Algorithm for the Sparse Spanning Graph Problem,” 2017. [Online]. Available: http://arxiv.org/abs/1703.05418. (arXiv: 1703.05418)
Abstract
Constructing a sparse \emph{spanning subgraph} is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most $(1+\varepsilon)n$ edges (where $n$ is the number of vertices and $\varepsilon$ is a given approximation/sparsity parameter). We achieve query complexity of $\tilde{O}(poly(\Delta/\varepsilon)n^{2/3})$,\footnote{$\tilde{O}$-notation hides polylogarithmic factors in $n$.} where $\Delta$ is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary graphs. Moreover, we achieve the additional property that our algorithm outputs a \emph{spanner,} i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of $O(poly(\Delta/\varepsilon)\log^2 n)$ hops in the output that connects its endpoints.
Export
BibTeX
@online{DBLP:journals/corr/LenzenL17, TITLE = {A Local Algorithm for the Sparse Spanning Graph Problem}, AUTHOR = {Lenzen, Christoph and Levi, Reut}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1703.05418}, EPRINT = {1703.05418}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Constructing a sparse \emph{spanning subgraph} is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most $(1+\varepsilon)n$ edges (where $n$ is the number of vertices and $\varepsilon$ is a given approximation/sparsity parameter). We achieve query complexity of $\tilde{O}(poly(\Delta/\varepsilon)n^{2/3})$,\footnote{$\tilde{O}$-notation hides polylogarithmic factors in $n$.} where $\Delta$ is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary graphs. Moreover, we achieve the additional property that our algorithm outputs a \emph{spanner,} i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of $O(poly(\Delta/\varepsilon)\log^2 n)$ hops in the output that connects its endpoints.}, }
Endnote
%0 Report %A Lenzen, Christoph %A Levi, Reut %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Local Algorithm for the Sparse Spanning Graph Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8AB0-4 %U http://arxiv.org/abs/1703.05418 %D 2017 %X Constructing a sparse \emph{spanning subgraph} is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most $(1+\varepsilon)n$ edges (where $n$ is the number of vertices and $\varepsilon$ is a given approximation/sparsity parameter). We achieve query complexity of $\tilde{O}(poly(\Delta/\varepsilon)n^{2/3})$,\footnote{$\tilde{O}$-notation hides polylogarithmic factors in $n$.} where $\Delta$ is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary graphs. Moreover, we achieve the additional property that our algorithm outputs a \emph{spanner,} i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of $O(poly(\Delta/\varepsilon)\log^2 n)$ hops in the output that connects its endpoints. %K Computer Science, Data Structures and Algorithms, cs.DS
[45]
C. Lenzen and M. Medina, “Robust Routing Made Easy,” 2017. [Online]. Available: http://arxiv.org/abs/1705.04042. (arXiv: 1705.04042)
Abstract
Designing routing schemes is a multidimensional and complex task that depends on the objective function, the computational model (centralized vs. distributed), and the amount of uncertainty (online vs. offline). Nevertheless, there are quite a few well-studied general techniques, for a large variety of network problems. In contrast, in our view, practical techniques for designing robust routing schemes are scarce; while fault-tolerance has been studied from a number of angles, existing approaches are concerned with dealing with faults after the fact by rerouting, self-healing, or similar techniques. We argue that this comes at a high burden for the designer, as in such a system any algorithm must account for the effects of faults on communication. With the goal of initiating efforts towards addressing this issue, we showcase simple and generic transformations that can be used as a blackbox to increase resilience against (independently distributed) faults. Given a network and a routing scheme, we determine a reinforced network and corresponding routing scheme that faithfully preserves the specification and behavior of the original scheme. We show that reasonably small constant overheads in terms of size of the new network compared to the old are sufficient for substantially relaxing the reliability requirements on individual components. The main message in this paper is that the task of designing a robust routing scheme can be decoupled into (i) designing a routing scheme that meets the specification in a fault-free environment, (ii) ensuring that nodes correspond to fault-containment regions, i.e., fail (approximately) independently, and (iii) applying our transformation to obtain a reinforced network and a robust routing scheme that is fault-tolerant.
Export
BibTeX
@online{DBLP:journals/corr/LenzenM17, TITLE = {Robust Routing Made Easy}, AUTHOR = {Lenzen, Christoph and Medina, Moti}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1705.04042}, EPRINT = {1705.04042}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Designing routing schemes is a multidimensional and complex task that depends on the objective function, the computational model (centralized vs. distributed), and the amount of uncertainty (online vs. offline). Nevertheless, there are quite a few well-studied general techniques, for a large variety of network problems. In contrast, in our view, practical techniques for designing robust routing schemes are scarce; while fault-tolerance has been studied from a number of angles, existing approaches are concerned with dealing with faults after the fact by rerouting, self-healing, or similar techniques. We argue that this comes at a high burden for the designer, as in such a system any algorithm must account for the effects of faults on communication. With the goal of initiating efforts towards addressing this issue, we showcase simple and generic transformations that can be used as a blackbox to increase resilience against (independently distributed) faults. Given a network and a routing scheme, we determine a reinforced network and corresponding routing scheme that faithfully preserves the specification and behavior of the original scheme. We show that reasonably small constant overheads in terms of size of the new network compared to the old are sufficient for substantially relaxing the reliability requirements on individual components. The main message in this paper is that the task of designing a robust routing scheme can be decoupled into (i) designing a routing scheme that meets the specification in a fault-free environment, (ii) ensuring that nodes correspond to fault-containment regions, i.e., fail (approximately) independently, and (iii) applying our transformation to obtain a reinforced network and a robust routing scheme that is fault-tolerant.}, }
Endnote
%0 Report %A Lenzen, Christoph %A Medina, Moti %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Robust Routing Made Easy : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8AAD-E %U http://arxiv.org/abs/1705.04042 %D 2017 %X Designing routing schemes is a multidimensional and complex task that depends on the objective function, the computational model (centralized vs. distributed), and the amount of uncertainty (online vs. offline). Nevertheless, there are quite a few well-studied general techniques, for a large variety of network problems. In contrast, in our view, practical techniques for designing robust routing schemes are scarce; while fault-tolerance has been studied from a number of angles, existing approaches are concerned with dealing with faults after the fact by rerouting, self-healing, or similar techniques. We argue that this comes at a high burden for the designer, as in such a system any algorithm must account for the effects of faults on communication. With the goal of initiating efforts towards addressing this issue, we showcase simple and generic transformations that can be used as a blackbox to increase resilience against (independently distributed) faults. Given a network and a routing scheme, we determine a reinforced network and corresponding routing scheme that faithfully preserves the specification and behavior of the original scheme. We show that reasonably small constant overheads in terms of size of the new network compared to the old are sufficient for substantially relaxing the reliability requirements on individual components. The main message in this paper is that the task of designing a robust routing scheme can be decoupled into (i) designing a routing scheme that meets the specification in a fault-free environment, (ii) ensuring that nodes correspond to fault-containment regions, i.e., fail (approximately) independently, and (iii) applying our transformation to obtain a reinforced network and a robust routing scheme that is fault-tolerant. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
[46]
R. Levi, G. Moshkovitz, D. Ron, R. Rubinfeld, and A. Shapira, “Constructing Near Spanning Trees with Few Local Inspections,” Random Structures and Algorithms, vol. 50, 2017.
Export
BibTeX
@article{LeviMRRS15, TITLE = {Constructing Near Spanning Trees with Few Local Inspections}, AUTHOR = {Levi, Reut and Moshkovitz, Guy and Ron, Dana and Rubinfeld, Ronitt and Shapira, Asaf}, LANGUAGE = {eng}, ISSN = {1042-9832}, DOI = {10.1002/rsa.20652}, PUBLISHER = {Wiley}, ADDRESS = {New York, N.Y.}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Random Structures and Algorithms}, VOLUME = {50}, PAGES = {183--200}, }
Endnote
%0 Journal Article %A Levi, Reut %A Moshkovitz, Guy %A Ron, Dana %A Rubinfeld, Ronitt %A Shapira, Asaf %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Constructing Near Spanning Trees with Few Local Inspections : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-601B-C %R 10.1002/rsa.20652 %7 2016 %D 2017 %J Random Structures and Algorithms %V 50 %& 183 %P 183 - 200 %I Wiley %C New York, N.Y. %@ false
[47]
K. Mehlhorn, S. Näher, and P. Sanders, “Engineering DFS-Based Graph Algorithms,” 2017. [Online]. Available: http://arxiv.org/abs/1703.10023. (arXiv: 1703.10023)
Export
BibTeX
@online{MehlhornDFSarXiv2017, TITLE = {Engineering {DFS}-Based Graph Algorithms}, AUTHOR = {Mehlhorn, Kurt and N{\"a}her, Stefan and Sanders, Peter}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1703.10023}, EPRINT = {1703.10023}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, }
Endnote
%0 Report %A Mehlhorn, Kurt %A N&#228;her, Stefan %A Sanders, Peter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Engineering DFS-Based Graph Algorithms : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-4DAE-7 %U http://arxiv.org/abs/1703.10023 %D 2017
[48]
K. Mehlhorn, A. Neumann, and J. M. Schmidt, “Certifying 3-Edge-Connectivity,” Algorithmica, vol. 77, no. 2, 2017.
Export
BibTeX
@article{Mehlhorn_Neumann_Schmidt2017, TITLE = {Certifying 3-Edge-Connectivity}, AUTHOR = {Mehlhorn, Kurt and Neumann, Adrian and Schmidt, Jens M.}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-015-0075-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NX}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Algorithmica}, VOLUME = {77}, NUMBER = {2}, PAGES = {309--335}, }
Endnote
%0 Journal Article %A Mehlhorn, Kurt %A Neumann, Adrian %A Schmidt, Jens M. %+ 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 Certifying 3-Edge-Connectivity : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-6971-B %R 10.1007/s00453-015-0075-x %7 2015-09-22 %D 2017 %J Algorithmica %V 77 %N 2 %& 309 %P 309 - 335 %I Springer %C New York, NX %@ false
[49]
R. B. Tan, E. J. van Leeuwen, and J. van Leeuwen, “Shortcutting Directed and Undirected Networks with a Degree Constraint,” Discrete Applied Mathematics, vol. 220, 2017.
Export
BibTeX
@article{TanDAM2017, TITLE = {Shortcutting Directed and Undirected Networks with a Degree Constraint}, AUTHOR = {Tan, Richard B. and van Leeuwen, Erik Jan and van Leeuwen, Jan}, LANGUAGE = {eng}, ISSN = {0166-218X}, DOI = {10.1016/j.dam.2016.12.016}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Discrete Applied Mathematics}, VOLUME = {220}, PAGES = {91--117}, }
Endnote
%0 Journal Article %A Tan, Richard B. %A van Leeuwen, Erik Jan %A van Leeuwen, Jan %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Shortcutting Directed and Undirected Networks with a Degree Constraint : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-539D-F %R 10.1016/j.dam.2016.12.016 %7 2017 %D 2017 %J Discrete Applied Mathematics %V 220 %& 91 %P 91 - 117 %I Elsevier %C Amsterdam %@ false
[50]
G. Tarawneh, M. Függer, and C. Lenzen, “Metastability Tolerant Computing,” in 23rd IEEE International Symposium on Asynchronous Circuits and Systems, San Diego, CA, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{TarawnehASYNC2017, TITLE = {Metastability Tolerant Computing}, AUTHOR = {Tarawneh, Ghaith and F{\"u}gger, Matthias and Lenzen, Christoph}, LANGUAGE = {eng}, PUBLISHER = {IEEE}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {23rd IEEE International Symposium on Asynchronous Circuits and Systems}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Tarawneh, Ghaith %A F&#252;gger, Matthias %A Lenzen, Christoph %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Metastability Tolerant Computing : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-80CB-2 %D 2017 %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %Z date of event: 2017-05-21 - 2017-05-24 %C San Diego, CA, USA %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %I IEEE