# 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, N. Barcelo, M. Consuegra, P. Kling, M. Nugent, K. Pruhs, and M. Scquizzato, “Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules,” Algorithmica, vol. 79, no. 2, 2017.
Export
BibTeX
@article{Antoniadis2016, TITLE = {Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules}, AUTHOR = {Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peter and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-016-0208-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Algorithmica}, VOLUME = {79}, NUMBER = {2}, PAGES = {568--597}, }
Endnote
%0 Journal Article %A Antoniadis, Antonios %A Barcelo, Neal %A Consuegra, Mario %A Kling, Peter %A Nugent, Michael %A Pruhs, Kirk %A Scquizzato, Michele %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations %T Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-58AA-7 %R 10.1007/s00453-016-0208-x %7 2016-08-31 %D 2017 %J Algorithmica %V 79 %N 2 %& 568 %P 568 - 597 %I Springer %C New York, NY %@ false
[5]
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&#246;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
[6]
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&#228;user, Rebecca %A V&#246;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
[7]
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
[8]
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
[9]
X. Bei, J. Garg, M. Hoefer, and K. Mehlhorn, “Earning Limits in Fisher Markets with Spending-Constraint Utilities,” in Algorithmic Game Theory (SAGT 2017), L’Aquila, Italy, 2017.
Export
BibTeX
@inproceedings{BeiSAGT2017, TITLE = {Earning Limits in {Fisher} Markets with Spending-Constraint Utilities}, AUTHOR = {Bei, Xiaohui and Garg, Jugal and Hoefer, Martin and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISBN = {978-3-319-66699-0}, DOI = {10.1007/978-3-319-66700-3_6}, PUBLISHER = {Springer}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Algorithmic Game Theory (SAGT 2017)}, PAGES = {67--79}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {10504}, ADDRESS = {L'Aquila, Italy}, }
Endnote
%0 Conference Proceedings %A Bei, Xiaohui %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Earning Limits in Fisher Markets with Spending-Constraint Utilities : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-E7DB-7 %R 10.1007/978-3-319-66700-3_6 %D 2017 %B 10th International Symposium on Algorithmic Game Theory %Z date of event: 2017-09-12 - 2017-09-14 %C L'Aquila, Italy %B Algorithmic Game Theory %P 67 - 79 %I Springer %@ 978-3-319-66699-0 %B Lecture Notes in Computer Science %N 10504
[10]
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&#232;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
[11]
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
[12]
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
[13]
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
[14]
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
[15]
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&#322; %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
[16]
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/
[17]
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
[18]
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
[19]
K. Bringmann and K. Panagiotou, “Efficient Sampling Methods for Discrete Distributions,” Algorithmica, vol. 79, no. 2, 2017.
Export
BibTeX
@article{BringmannAlgorithmica2016, TITLE = {Efficient Sampling Methods for Discrete Distributions}, AUTHOR = {Bringmann, Karl and Panagiotou, Konstantinos}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-016-0205-0}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Algorithmica}, VOLUME = {79}, NUMBER = {2}, PAGES = {484--508}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A Panagiotou, Konstantinos %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Efficient Sampling Methods for Discrete Distributions : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-85D0-8 %R 10.1007/s00453-016-0205-0 %7 2016-08-29 %D 2017 %J Algorithmica %V 79 %N 2 %& 484 %P 484 - 508 %I Springer-Verlag %C New York %@ false
[20]
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
[21]
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&#252;r Softwaretechnik GmbH %C Potsdam %@ false %U https://eccc.weizmann.ac.il/report/2017/034/
[22]
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,
[23]
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
[24]
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&#252;rgisser, Peter %A Ikenmeyer, Christian %A H&#252;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
[25]
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&#252;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
[26]
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
[27]
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
[28]
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
[29]
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/
[30]
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&#322; %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
[31]
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
[32]
M. Dirnberger, K. Mehlhorn, M. Grube, and H.-G. Döbereiner, “Preliminaries for Distributed Natural Computing Inspired by the Slime Mold Physarum Polycephalum,” Universität des Saarlandes, Saarbrücken, 2017.
Abstract
This doctoral thesis aims towards distributed natural computing inspired by the slime mold Physarum polycephalum. The vein networks formed by this organism presumably support efficient transport of protoplasmic fluid. Devising models which capture the natural efficiency of the organism and form a suitable basis for the development of natural computing algorithms is an interesting and challenging goal. We start working towards this goal by designing and executing wet-lab experi- ments geared towards producing a large number of images of the vein networks of P. polycephalum. Next, we turn the depicted vein networks into graphs using our own custom software called Nefi. This enables a detailed numerical study, yielding a catalogue of characterizing observables spanning a wide array of different graph properties. To share our results and data, i.e. raw experimental data, graphs and analysis results, we introduce a dedicated repository revolving around slime mold data, the Smgr. The purpose of this repository is to promote data reuse and to foster a practice of increased data sharing. Finally we present a model based on interacting electronic circuits including current controlled voltage sources, which mimics the emergent flow patterns observed in live P. polycephalum. The model is simple, distributed and robust to changes in the underlying network topology. Thus it constitutes a promising basis for the development of distributed natural computing algorithms.
Export
BibTeX
@phdthesis{dirnbergerphd17, TITLE = {Preliminaries for Distributed Natural Computing Inspired by the Slime Mold Physarum Polycephalum}, AUTHOR = {Dirnberger, Michael and Mehlhorn, Kurt and Grube, Martin and D{\"o}bereiner, Hans-G{\"u}nther}, LANGUAGE = {eng}, URL = {urn:nbn:de:bsz:291-scidok-69424}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, ABSTRACT = {This doctoral thesis aims towards distributed natural computing inspired by the slime mold Physarum polycephalum. The vein networks formed by this organism presumably support efficient transport of protoplasmic fluid. Devising models which capture the natural efficiency of the organism and form a suitable basis for the development of natural computing algorithms is an interesting and challenging goal. We start working towards this goal by designing and executing wet-lab experi- ments geared towards producing a large number of images of the vein networks of P. polycephalum. Next, we turn the depicted vein networks into graphs using our own custom software called Nefi. This enables a detailed numerical study, yielding a catalogue of characterizing observables spanning a wide array of different graph properties. To share our results and data, i.e. raw experimental data, graphs and analysis results, we introduce a dedicated repository revolving around slime mold data, the Smgr. The purpose of this repository is to promote data reuse and to foster a practice of increased data sharing. Finally we present a model based on interacting electronic circuits including current controlled voltage sources, which mimics the emergent flow patterns observed in live P. polycephalum. The model is simple, distributed and robust to changes in the underlying network topology. Thus it constitutes a promising basis for the development of distributed natural computing algorithms.}, }
Endnote
%0 Thesis %A Dirnberger, Michael %A Mehlhorn, Kurt %A Grube, Martin %A D&#246;bereiner, Hans-G&#252;nther %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Preliminaries for Distributed Natural Computing Inspired by the Slime Mold Physarum Polycephalum : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-DE4F-0 %U urn:nbn:de:bsz:291-scidok-69424 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2017 %P XV, 193 p. %V phd %9 phd %X This doctoral thesis aims towards distributed natural computing inspired by the slime mold Physarum polycephalum. The vein networks formed by this organism presumably support efficient transport of protoplasmic fluid. Devising models which capture the natural efficiency of the organism and form a suitable basis for the development of natural computing algorithms is an interesting and challenging goal. We start working towards this goal by designing and executing wet-lab experi- ments geared towards producing a large number of images of the vein networks of P. polycephalum. Next, we turn the depicted vein networks into graphs using our own custom software called Nefi. This enables a detailed numerical study, yielding a catalogue of characterizing observables spanning a wide array of different graph properties. To share our results and data, i.e. raw experimental data, graphs and analysis results, we introduce a dedicated repository revolving around slime mold data, the Smgr. The purpose of this repository is to promote data reuse and to foster a practice of increased data sharing. Finally we present a model based on interacting electronic circuits including current controlled voltage sources, which mimics the emergent flow patterns observed in live P. polycephalum. The model is simple, distributed and robust to changes in the underlying network topology. Thus it constitutes a promising basis for the development of distributed natural computing algorithms. %U http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=dehttp://scidok.sulb.uni-saarland.de/volltexte/2017/6942/
[33]
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
[34]
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
[35]
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
[36]
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&#252;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
[37]
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&#252;ller, Jan %A Kr&#246;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
[38]
S. Friedrichs, C. Lenzen, K. Mehlhorn, and M. Ghaffari, “Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding,” Unversität des Saarlandes, Saarbrücken, 2017.
Abstract
We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle. The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work. Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver.
Export
BibTeX
@phdthesis{Friedrichsphd2017, TITLE = {Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding}, AUTHOR = {Friedrichs, Stephan and Lenzen, Christoph and Mehlhorn, Kurt and Ghaffari, Mohsen}, LANGUAGE = {eng}, URL = {urn:nbn:de:bsz:291-scidok-69660}, SCHOOL = {Unversit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, ABSTRACT = {We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle. The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work. Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver.}, }
Endnote
%0 Thesis %A Friedrichs, Stephan %A Lenzen, Christoph %A Mehlhorn, Kurt %A Ghaffari, Mohsen %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-E9A7-B %U urn:nbn:de:bsz:291-scidok-69660 %I Unversit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2017 %P x, 226 p. %V phd %9 phd %X We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle. The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work. Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver. %U http://scidok.sulb.uni-saarland.de/volltexte/2017/6966/http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de
[39]
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&#252;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
[40]
J. Garg, M. Hoefer, and K. Mehlhorn, “Approximating the Nash Social Welfare with Budget-Additive Valuations,” 2017. [Online]. Available: http://arxiv.org/abs/1707.04428. (arXiv: 1707.04428)
Abstract
We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every $\varepsilon > 0$, our algorithm obtains a $(2.404 + \varepsilon)$-approximation in time polynomial in the input size and $1/\varepsilon$. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.
Export
BibTeX
@online{GargHoeferMehlhorn2017, TITLE = {Approximating the {Nash} Social Welfare with Budget-Additive Valuations}, AUTHOR = {Garg, Jugal and Hoefer, Martin and Mehlhorn, Kurt}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1707.04428}, EPRINT = {1707.04428}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every $\varepsilon > 0$, our algorithm obtains a $(2.404 + \varepsilon)$-approximation in time polynomial in the input size and $1/\varepsilon$. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.}, }
Endnote
%0 Report %A Garg, Jugal %A Hoefer, Martin %A Mehlhorn, Kurt %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximating the Nash Social Welfare with Budget-Additive Valuations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-E7D6-2 %U http://arxiv.org/abs/1707.04428 %D 2017 %X We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every $\varepsilon > 0$, our algorithm obtains a $(2.404 + \varepsilon)$-approximation in time polynomial in the input size and $1/\varepsilon$. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT
[41]
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&#252;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&#252;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
[42]
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&#246;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
[43]
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
[44]
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
[45]
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
[46]
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
[47]
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
[48]
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
[49]
C. Lenzen, N. A. Lynch, C. Newport, and T. Radeva, “Searching without Communicating: Tradeoffs between Performance and Selection Complexity,” Distributed Computing, vol. 30, no. 3, 2017.
Export
BibTeX
@article{DBLP:journals/dc/LenzenLNR17, TITLE = {Searching without Communicating: {T}radeoffs between Performance and Selection Complexity}, AUTHOR = {Lenzen, Christoph and Lynch, Nancy A. and Newport, Calvin and Radeva, Tsvetomira}, LANGUAGE = {eng}, ISSN = {0178-2770}, DOI = {10.1007/s00446-016-0283-x}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Distributed Computing}, VOLUME = {30}, NUMBER = {3}, PAGES = {169--191}, }
Endnote
%0 Journal Article %A Lenzen, Christoph %A Lynch, Nancy A. %A Newport, Calvin %A Radeva, Tsvetomira %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Searching without Communicating: Tradeoffs between Performance and Selection Complexity : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-8AA7-9 %R 10.1007/s00446-016-0283-x %7 2016-09-19 %D 2017 %J Distributed Computing %V 30 %N 3 %& 169 %P 169 - 191 %I Springer International %C Berlin %@ false
[50]
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
[51]
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
[52]
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
[53]
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
[54]
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
[55]
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
[56]
M. Mnich and E. J. van Leeuwen, “Polynomial Kernels for Deletion to Classes of Acyclic Digraphs,” Discrete Optimization, vol. 25, 2017.
Export
BibTeX
@article{MnichLeeuwen2017, TITLE = {Polynomial Kernels for Deletion to Classes of Acyclic Digraphs}, AUTHOR = {Mnich, Matthias and van Leeuwen, Erik Jan}, LANGUAGE = {eng}, ISSN = {1572-5286}, DOI = {10.1016/j.disopt.2017.02.002}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Discrete Optimization}, VOLUME = {25}, PAGES = {48--76}, }
Endnote
%0 Journal Article %A Mnich, Matthias %A van Leeuwen, Erik Jan %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Polynomial Kernels for Deletion to Classes of Acyclic Digraphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-DDCA-F %R 10.1016/j.disopt.2017.02.002 %7 2017 %D 2017 %J Discrete Optimization %V 25 %& 48 %P 48 - 76 %I Elsevier %C Amsterdam %@ false
[57]
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
[58]
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