# Current Year

[1]
A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay, “SETH-Based Lower Bounds for Subset Sum and Bicriteria Path,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Abboud_SODA19b, 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}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.3}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {41--57}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Abboud, Amir %A Bringmann, Karl %A Hermelin, Danny %A Shabtay, Dvir %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T SETH-Based Lower Bounds for Subset Sum and Bicriteria Path : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E12-8 %R 10.1137/1.9781611975482.3 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 41 - 57 %I SIAM %@ 978-1-61197-548-2
[2]
P. Afshani, M. Agrawal, B. Doerr, C. Doerr, K. G. Larsen, and K. Mehlhorn, “The Query Complexity of a Permutation-based Variant of Mastermind,” Discrete Applied Mathematics, vol. 260, 2019.
Export
BibTeX
@article{AFSHANI2019, TITLE = {The query complexity of a permutation-based variant of {M}astermind}, AUTHOR = {Afshani, Peyman and Agrawal, Manindra and Doerr, Benjamin and Doerr, Carola and Larsen, Kasper Green and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISSN = {0166-218X}, DOI = {10.1016/j.dam.2019.01.007}, PUBLISHER = {North-Holland}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Discrete Applied Mathematics}, VOLUME = {260}, PAGES = {28--50}, }
Endnote
%0 Journal Article %A Afshani, Peyman %A Agrawal, Manindra %A Doerr, Benjamin %A Doerr, Carola %A Larsen, Kasper Green %A Mehlhorn, Kurt %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Query Complexity of a Permutation-based Variant of Mastermind : %G eng %U http://hdl.handle.net/21.11116/0000-0002-FE83-C %R 10.1016/j.dam.2019.01.007 %7 2019 %D 2019 %J Discrete Applied Mathematics %V 260 %& 28 %P 28 - 50 %I North-Holland %C Amsterdam %@ false
[3]
H.-K. Ahn, T. Ahn, S. W. Bae, J. Choi, M. Kim, E. Oh, C.-S. Shin, and S. D. Yoon, “Minimum-width Annulus with Outliers: Circular, Square, and Rectangular Cases,” Information Processing Letters, vol. 145, 2019.
Export
BibTeX
@article{Ahn2019, TITLE = {Minimum-width Annulus with Outliers: {C}ircular, Square, and Rectangular Cases}, AUTHOR = {Ahn, Hee-Kap and Ahn, Taehoon and Bae, Sang Won and Choi, Jongmin and Kim, Mincheol and Oh, Eunjin and Shin, Chan-Su and Yoon, Sang Duk}, LANGUAGE = {eng}, ISSN = {0020-0190}, DOI = {10.1016/j.ipl.2019.01.004}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Information Processing Letters}, VOLUME = {145}, PAGES = {16--23}, }
Endnote
%0 Journal Article %A Ahn, Hee-Kap %A Ahn, Taehoon %A Bae, Sang Won %A Choi, Jongmin %A Kim, Mincheol %A Oh, Eunjin %A Shin, Chan-Su %A Yoon, Sang Duk %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Minimum-width Annulus with Outliers: Circular, Square, and Rectangular Cases : %G eng %U http://hdl.handle.net/21.11116/0000-0003-4FD4-6 %R 10.1016/j.ipl.2019.01.004 %7 2019 %D 2019 %J Information Processing Letters %V 145 %& 16 %P 16 - 23 %I Elsevier %C Amsterdam %@ false
[4]
H. Akrami, K. Mehlhorn, and T. Odland, “Ratio-Balanced Maximum Flows,” 2019. [Online]. Available: http://arxiv.org/abs/1902.11047. (arXiv: 1902.11047)
Abstract
When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form of \emph{security}, which will be collected if the lender defaults. Accounts can be secured by several securities and a security can be used for several accounts. The goal is to fractionally assign the securities to the accounts so as to balance the risk. This situation can be modelled by a bipartite graph. We have a set $S$ of securities and a set $A$ of accounts. Each security has a \emph{value} $v_i$ and each account has an \emph{exposure} $e_j$. If a security $i$ can be used to secure an account $j$, we have an edge from $i$ to $j$. Let $f_{ij}$ be part of security $i$'s value used to secure account $j$. We are searching for a maximum flow that send at most $v_i$ units out of node $i \in S$ and at most $e_j$ units into node $j \in A$. Then $s_j = e_j - \sum_i f_{ij}$ is the unsecured part of account $j$. We are searching for the maximum flow that minimizes $\sum_j s_j^2/e_j$.
Export
BibTeX
@online{Akrami_arXiv1902.11047, TITLE = {Ratio-Balanced Maximum Flows}, AUTHOR = {Akrami, Hannaneh and Mehlhorn, Kurt and Odland, Tommy}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1902.11047}, EPRINT = {1902.11047}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form of \emph{security}, which will be collected if the lender defaults. Accounts can be secured by several securities and a security can be used for several accounts. The goal is to fractionally assign the securities to the accounts so as to balance the risk. This situation can be modelled by a bipartite graph. We have a set $S$ of securities and a set $A$ of accounts. Each security has a \emph{value} $v_i$ and each account has an \emph{exposure} $e_j$. If a security $i$ can be used to secure an account $j$, we have an edge from $i$ to $j$. Let $f_{ij}$ be part of security $i$'s value used to secure account $j$. We are searching for a maximum flow that send at most $v_i$ units out of node $i \in S$ and at most $e_j$ units into node $j \in A$. Then $s_j = e_j -- \sum_i f_{ij}$ is the unsecured part of account $j$. We are searching for the maximum flow that minimizes $\sum_j s_j^2/e_j$.}, }
Endnote
%0 Report %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Odland, Tommy %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Ratio-Balanced Maximum Flows : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B2FE-6 %U http://arxiv.org/abs/1902.11047 %D 2019 %X When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form of \emph{security}, which will be collected if the lender defaults. Accounts can be secured by several securities and a security can be used for several accounts. The goal is to fractionally assign the securities to the accounts so as to balance the risk. This situation can be modelled by a bipartite graph. We have a set $S$ of securities and a set $A$ of accounts. Each security has a \emph{value} $v_i$ and each account has an \emph{exposure} $e_j$. If a security $i$ can be used to secure an account $j$, we have an edge from $i$ to $j$. Let $f_{ij}$ be part of security $i$'s value used to secure account $j$. We are searching for a maximum flow that send at most $v_i$ units out of node $i \in S$ and at most $e_j$ units into node $j \in A$. Then $s_j = e_j - \sum_i f_{ij}$ is the unsecured part of account $j$. We are searching for the maximum flow that minimizes $\sum_j s_j^2/e_j$. %K Computer Science, Data Structures and Algorithms, cs.DS
[5]
H. Akrami, K. Mehlhorn, and T. Odland, “Ratio-Balanced Maximum Flows,” Information Processing Letters, vol. 150, 2019.
Export
BibTeX
@article{Akrami_2019, TITLE = {Ratio-Balanced Maximum Flows}, AUTHOR = {Akrami, Hannaneh and Mehlhorn, Kurt and Odland, Tommy}, LANGUAGE = {eng}, ISSN = {0020-0190}, DOI = {10.1016/j.ipl.2019.06.003}, PUBLISHER = {Elsevier}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Information Processing Letters}, VOLUME = {150}, PAGES = {13--17}, }
Endnote
%0 Journal Article %A Akrami, Hannaneh %A Mehlhorn, Kurt %A Odland, Tommy %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Ratio-Balanced Maximum Flows : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8FF0-C %R 10.1016/j.ipl.2019.06.003 %7 2019 %D 2019 %J Information Processing Letters %V 150 %& 13 %P 13 - 17 %I Elsevier %@ false
[6]
S. A. Amiri, S. Schmid, and S. Siebertz, “Distributed Dominating Set Approximations beyond Planar Graphs,” ACM Transactions on Algorithms, vol. 15, no. 3, 2019.
Export
BibTeX
@article{Amiri2019, TITLE = {Distributed Dominating Set Approximations beyond Planar Graphs}, AUTHOR = {Amiri, Saeed Akhoondian and Schmid, Stefan and Siebertz, Sebastian}, LANGUAGE = {eng}, ISSN = {1549-6325}, DOI = {10.1145/3326170}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = {15}, NUMBER = {3}, EID = {39}, }
Endnote
%0 Journal Article %A Amiri, Saeed Akhoondian %A Schmid, Stefan %A Siebertz, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Distributed Dominating Set Approximations beyond Planar Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8335-C %R 10.1145/3326170 %7 2019 %D 2019 %J ACM Transactions on Algorithms %V 15 %N 3 %Z sequence number: 39 %I ACM %C New York, NY %@ false
[7]
A. Antoniadis, K. Fleszar, R. Hoeksma, and K. Schewior, “A PTAS for Euclidean TSP with Hyperplane Neighborhoods,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Antoniadis_SODA19, TITLE = {A {PTAS} for {E}uclidean {TSP} with Hyperplane Neighborhoods}, AUTHOR = {Antoniadis, Antonios and Fleszar, Krzysztof and Hoeksma, Ruben and Schewior, Kevin}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.67}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {1089--1105}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Antoniadis, Antonios %A Fleszar, Krzysztof %A Hoeksma, Ruben %A Schewior, Kevin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A PTAS for Euclidean TSP with Hyperplane Neighborhoods : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9F3A-B %R 10.1137/1.9781611975482.67 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 1089 - 1105 %I SIAM %@ 978-1-61197-548-2
[8]
A. Antoniadis, N. Barcelo, M. Nugent, K. Pruhs, and M. Scquizzato, “A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line,” Algorithmica, vol. 81, no. 7, 2019.
Export
BibTeX
@article{Antoniadis2019, TITLE = {A $o(n)$-Competitive Deterministic Algorithm for Online Matching on a Line}, AUTHOR = {Antoniadis, Antonios and Barcelo, Neal and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-019-00565-w}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Algorithmica}, VOLUME = {81}, NUMBER = {7}, PAGES = {2917--2933}, }
Endnote
%0 Journal Article %A Antoniadis, Antonios %A Barcelo, Neal %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 %T A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7DA-B %R 10.1007/s00453-019-00565-w %7 2019 %D 2019 %J Algorithmica %V 81 %N 7 %& 2917 %P 2917 - 2933 %I Springer %C New York, NY %@ false
[9]
A. Antoniadis, C.-C. Huang, and S. Ott, “A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State,” Algorithmica, vol. 81, no. 9, 2019.
Export
BibTeX
@article{Antoniadis2019, TITLE = {A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State}, AUTHOR = {Antoniadis, Antonios and Huang, Chien-Chung and Ott, Sebastian}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-019-00596-3}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Algorithmica}, VOLUME = {81}, NUMBER = {9}, PAGES = {3725 --3745}, }
Endnote
%0 Journal Article %A Antoniadis, Antonios %A Huang, Chien-Chung %A Ott, Sebastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State : %G eng %U http://hdl.handle.net/21.11116/0000-0004-AAC7-C %R 10.1007/s00453-019-00596-3 %7 2019 %D 2019 %J Algorithmica %V 81 %N 9 %& 3725 %P 3725 - 3745 %I Springer %C New York, NY %@ false
[10]
G. Ballard, C. Ikenmeyer, J. M. Landsberg, and N. Ryder, “The Geometry of Rank Decompositions of Matrix Multiplication II: 3 x 3 Matrices,” Journal of Pure and Applied Algebra, vol. 223, no. 8, 2019.
Export
BibTeX
@article{Ballard2018, TITLE = {The geometry of rank decompositions of matrix multiplication II: $3\times 3$ matrices}, AUTHOR = {Ballard, Grey and Ikenmeyer, Christian and Landsberg, J. M. and Ryder, Nick}, LANGUAGE = {eng}, ISSN = {0022-4049}, DOI = {10.1016/j.jpaa.2018.10.014}, PUBLISHER = {North-Holland}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Journal of Pure and Applied Algebra}, VOLUME = {223}, NUMBER = {8}, PAGES = {3205--3224}, }
Endnote
%0 Journal Article %A Ballard, Grey %A Ikenmeyer, Christian %A Landsberg, J. M. %A Ryder, Nick %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T The Geometry of Rank Decompositions of Matrix Multiplication II: 3 x 3 Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AB17-4 %R 10.1016/j.jpaa.2018.10.014 %7 2018 %D 2019 %J Journal of Pure and Applied Algebra %O J. Pure Appl. Algebra %V 223 %N 8 %& 3205 %P 3205 - 3224 %I North-Holland %C Amsterdam %@ false
[11]
A. Balliu, J. Hirvonen, C. Lenzen, D. Olivetti, and J. Suomela, “Locality of Not-So-Weak Coloring,” 2019. [Online]. Available: http://arxiv.org/abs/1904.05627. (arXiv: 1904.05627)
Abstract
Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally checkable labelings (LCLs), introduced by Naor and Stockmeyer (1995). Recently, Chang et al. (2016) showed that in bounded-degree graphs, every LCL problem belongs to one of the following classes: - "Easy": solvable in $O(\log^* n)$ rounds with both deterministic and randomized distributed algorithms. - "Hard": requires at least $\Omega(\log n)$ rounds with deterministic and $\Omega(\log \log n)$ rounds with randomized distributed algorithms. Hence for any parameterized LCL problem, when we move from local problems towards global problems, there is some point at which complexity suddenly jumps from easy to hard. For example, for vertex coloring in $d$-regular graphs it is now known that this jump is at precisely $d$ colors: coloring with $d+1$ colors is easy, while coloring with $d$ colors is hard. However, it is currently poorly understood where this jump takes place when one looks at defective colorings. To study this question, we define $k$-partial $c$-coloring as follows: nodes are labeled with numbers between $1$ and $c$, and every node is incident to at least $k$ properly colored edges. It is known that $1$-partial $2$-coloring (a.k.a. weak $2$-coloring) is easy for any $d \ge 1$. As our main result, we show that $k$-partial $2$-coloring becomes hard as soon as $k \ge 2$, no matter how large a $d$ we have. We also show that this is fundamentally different from $k$-partial $3$-coloring: no matter which $k \ge 3$ we choose, the problem is always hard for $d = k$ but it becomes easy when $d \gg k$. The same was known previously for partial $c$-coloring with $c \ge 4$, but the case of $c < 4$ was open.
Export
BibTeX
@online{Balliu_arXiv1904.05627, TITLE = {Locality of Not-So-Weak Coloring}, AUTHOR = {Balliu, Alkida and Hirvonen, Juho and Lenzen, Christoph and Olivetti, Dennis and Suomela, Jukka}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1904.05627}, EPRINT = {1904.05627}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally checkable labelings (LCLs), introduced by Naor and Stockmeyer (1995). Recently, Chang et al. (2016) showed that in bounded-degree graphs, every LCL problem belongs to one of the following classes: -- "Easy": solvable in $O(\log^* n)$ rounds with both deterministic and randomized distributed algorithms. -- "Hard": requires at least $\Omega(\log n)$ rounds with deterministic and $\Omega(\log \log n)$ rounds with randomized distributed algorithms. Hence for any parameterized LCL problem, when we move from local problems towards global problems, there is some point at which complexity suddenly jumps from easy to hard. For example, for vertex coloring in $d$-regular graphs it is now known that this jump is at precisely $d$ colors: coloring with $d+1$ colors is easy, while coloring with $d$ colors is hard. However, it is currently poorly understood where this jump takes place when one looks at defective colorings. To study this question, we define $k$-partial $c$-coloring as follows: nodes are labeled with numbers between $1$ and $c$, and every node is incident to at least $k$ properly colored edges. It is known that $1$-partial $2$-coloring (a.k.a. weak $2$-coloring) is easy for any $d \ge 1$. As our main result, we show that $k$-partial $2$-coloring becomes hard as soon as $k \ge 2$, no matter how large a $d$ we have. We also show that this is fundamentally different from $k$-partial $3$-coloring: no matter which $k \ge 3$ we choose, the problem is always hard for $d = k$ but it becomes easy when $d \gg k$. The same was known previously for partial $c$-coloring with $c \ge 4$, but the case of $c < 4$ was open.}, }
Endnote
%0 Report %A Balliu, Alkida %A Hirvonen, Juho %A Lenzen, Christoph %A Olivetti, Dennis %A Suomela, Jukka %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Locality of Not-So-Weak Coloring : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B39F-0 %U http://arxiv.org/abs/1904.05627 %D 2019 %X Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally checkable labelings (LCLs), introduced by Naor and Stockmeyer (1995). Recently, Chang et al. (2016) showed that in bounded-degree graphs, every LCL problem belongs to one of the following classes: - "Easy": solvable in $O(\log^* n)$ rounds with both deterministic and randomized distributed algorithms. - "Hard": requires at least $\Omega(\log n)$ rounds with deterministic and $\Omega(\log \log n)$ rounds with randomized distributed algorithms. Hence for any parameterized LCL problem, when we move from local problems towards global problems, there is some point at which complexity suddenly jumps from easy to hard. For example, for vertex coloring in $d$-regular graphs it is now known that this jump is at precisely $d$ colors: coloring with $d+1$ colors is easy, while coloring with $d$ colors is hard. However, it is currently poorly understood where this jump takes place when one looks at defective colorings. To study this question, we define $k$-partial $c$-coloring as follows: nodes are labeled with numbers between $1$ and $c$, and every node is incident to at least $k$ properly colored edges. It is known that $1$-partial $2$-coloring (a.k.a. weak $2$-coloring) is easy for any $d \ge 1$. As our main result, we show that $k$-partial $2$-coloring becomes hard as soon as $k \ge 2$, no matter how large a $d$ we have. We also show that this is fundamentally different from $k$-partial $3$-coloring: no matter which $k \ge 3$ we choose, the problem is always hard for $d = k$ but it becomes easy when $d \gg k$. The same was known previously for partial $c$-coloring with $c \ge 4$, but the case of $c < 4$ was open. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Computational Complexity, cs.CC
[12]
F. Ban, V. Bhattiprolu, K. Bringmann, P. Kolev, E. Lee, and D. Woodruff, “A PTAS for l_p-Low Rank Approximation,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Ban_SODA19a, TITLE = {A {PTAS} for $\ell_p$-Low Rank Approximation}, AUTHOR = {Ban, Frank and Bhattiprolu, Vijay and Bringmann, Karl and Kolev, Pavel and Lee, Euiwoong and Woodruff, David}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.47}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {747--766}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Ban, Frank %A Bhattiprolu, Vijay %A Bringmann, Karl %A Kolev, Pavel %A Lee, Euiwoong %A Woodruff, David %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A PTAS for l_p-Low Rank Approximation : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E0E-E %R 10.1137/1.9781611975482.47 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 747 - 766 %I SIAM %@ 978-1-61197-548-2
[13]
L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and G. Posta, “Self-Stabilizing Repeated Balls-into-Bins,” Distributed Computing, vol. 32, no. 1, 2019.
Export
BibTeX
@article{Becchetti2019, TITLE = {Self-Stabilizing Repeated Balls-into-Bins}, AUTHOR = {Becchetti, Luca and Clementi, Andrea and Natale, Emanuele and Pasquale, Francesco and Posta, Gustavo}, LANGUAGE = {eng}, ISSN = {0178-2770}, DOI = {10.1007/s00446-017-0320-4}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Distributed Computing}, VOLUME = {32}, NUMBER = {1}, PAGES = {59--68}, }
Endnote
%0 Journal Article %A Becchetti, Luca %A Clementi, Andrea %A Natale, Emanuele %A Pasquale, Francesco %A Posta, Gustavo %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Self-Stabilizing Repeated Balls-into-Bins : %G eng %U http://hdl.handle.net/21.11116/0000-0002-F6C1-E %R 10.1007/s00446-017-0320-4 %7 2017 %D 2019 %J Distributed Computing %V 32 %N 1 %& 59 %P 59 - 68 %I Springer International %C Berlin %@ false
[14]
R. Becker, V. Bonifaci, A. Karrenbauer, P. Kolev, and K. Mehlhorn, “Two Results on Slime Mold Computations,” Theoretical Computer Science, vol. 773, 2019.
Abstract
In this paper, we present two results on slime mold computations. The first one treats a biologically-grounded model, originally proposed by biologists analyzing the behavior of the slime mold Physarum polycephalum. This primitive organism was empirically shown by Nakagaki et al. to solve shortest path problems in wet-lab experiments (Nature'00). We show that the proposed simple mathematical model actually generalizes to a much wider class of problems, namely undirected linear programs with a non-negative cost vector. For our second result, we consider the discretization of a biologically-inspired model. This model is a directed variant of the biologically-grounded one and was never claimed to describe the behavior of a biological system. Straszak and Vishnoi showed that it can $\epsilon$-approximately solve flow problems (SODA'16) and even general linear programs with positive cost vector (ITCS'16) within a finite number of steps. We give a refined convergence analysis that improves the dependence on $\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a step size that is independent of $\epsilon$. Furthermore, we show that the dynamics can be initialized with a more general set of (infeasible) starting points.
Export
BibTeX
@article{BBKKM2018, TITLE = {Two Results on Slime Mold Computations}, AUTHOR = {Becker, Ruben and Bonifaci, Vincenzo and Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2018.08.027}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, ABSTRACT = {In this paper, we present two results on slime mold computations. The first one treats a biologically-grounded model, originally proposed by biologists analyzing the behavior of the slime mold Physarum polycephalum. This primitive organism was empirically shown by Nakagaki et al. to solve shortest path problems in wet-lab experiments (Nature'00). We show that the proposed simple mathematical model actually generalizes to a much wider class of problems, namely undirected linear programs with a non-negative cost vector. For our second result, we consider the discretization of a biologically-inspired model. This model is a directed variant of the biologically-grounded one and was never claimed to describe the behavior of a biological system. Straszak and Vishnoi showed that it can $\epsilon$-approximately solve flow problems (SODA'16) and even general linear programs with positive cost vector (ITCS'16) within a finite number of steps. We give a refined convergence analysis that improves the dependence on $\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a step size that is independent of $\epsilon$. Furthermore, we show that the dynamics can be initialized with a more general set of (infeasible) starting points.}, JOURNAL = {Theoretical Computer Science}, VOLUME = {773}, PAGES = {79--106}, }
Endnote
%0 Journal Article %A Becker, Ruben %A Bonifaci, Vincenzo %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ 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 Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Two Results on Slime Mold Computations : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A3AE-2 %R 10.1016/j.tcs.2018.08.027 %7 2018 %D 2019 %X In this paper, we present two results on slime mold computations. The first one treats a biologically-grounded model, originally proposed by biologists analyzing the behavior of the slime mold Physarum polycephalum. This primitive organism was empirically shown by Nakagaki et al. to solve shortest path problems in wet-lab experiments (Nature'00). We show that the proposed simple mathematical model actually generalizes to a much wider class of problems, namely undirected linear programs with a non-negative cost vector. For our second result, we consider the discretization of a biologically-inspired model. This model is a directed variant of the biologically-grounded one and was never claimed to describe the behavior of a biological system. Straszak and Vishnoi showed that it can $\epsilon$-approximately solve flow problems (SODA'16) and even general linear programs with positive cost vector (ITCS'16) within a finite number of steps. We give a refined convergence analysis that improves the dependence on $\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a step size that is independent of $\epsilon$. Furthermore, we show that the dynamics can be initialized with a more general set of (infeasible) starting points. %K Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Dynamical Systems, math.DS,Mathematics, Optimization and Control, math.OC, Physics, Biological Physics, physics.bio-ph %J Theoretical Computer Science %V 773 %& 79 %P 79 - 106 %I Elsevier %C Amsterdam %@ false
[15]
O. Beyersdorff, L. Chew, and K. Sreenivasaiah, “A Game Characterisation of Tree-like Q-Resolution Size,” Journal of Computer and System Sciences, vol. 104, 2019.
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 = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {104}, PAGES = {82--101}, }
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 2019 %J Journal of Computer and System Sciences %V 104 %& 82 %P 82 - 101 %I Elsevier %C Amsterdam %@ false
[16]
V. Bhargava, M. Bläser, G. Jindal, and A. Pandey, “A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Bhargava_SODA19d, TITLE = {A Deterministic {PTAS} for the Algebraic Rank of Bounded Degree Polynomials}, AUTHOR = {Bhargava, Vishwas and Bl{\"a}ser, Markus and Jindal, Gorav and Pandey, Anurag}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.41}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {647--661}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Bhargava, Vishwas %A Bl&#228;ser, Markus %A Jindal, Gorav %A Pandey, Anurag %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials : %G eng %U http://hdl.handle.net/21.11116/0000-0002-ABAD-B %R 10.1137/1.9781611975482.41 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 647 - 661 %I SIAM %@ 978-1-61197-548-2
[17]
L. Boczkowski, A. Korman, and E. Natale, “Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits,” Distributed Computing, vol. 32, no. 3, 2019.
Export
BibTeX
@article{Boczkowski2019, 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}, ISSN = {0178-2770}, DOI = {10.1007/s00446-018-0330-x}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Distributed Computing}, VOLUME = {32}, NUMBER = {3}, PAGES = {173--191}, }
Endnote
%0 Journal Article %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/21.11116/0000-0003-B2F2-2 %R 10.1007/s00446-018-0330-x %7 2018 %D 2019 %J Distributed Computing %V 32 %N 3 %& 173 %P 173 - 191 %I Springer International %C Berlin %@ false
[18]
M. Borassi and E. Natale, “KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation,” Journal of Experimental Algorithmics, vol. 24, no. 1, 2019.
Export
BibTeX
@article{Borassi2019, TITLE = {{KADABRA} is an {ADaptive} Algorithm for Betweenness via Random Approximation}, AUTHOR = {Borassi, Michele and Natale, Emanuele}, LANGUAGE = {eng}, ISSN = {1084-6654}, DOI = {10.1145/3284359}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Experimental Algorithmics}, VOLUME = {24}, NUMBER = {1}, EID = {1.2}, }
Endnote
%0 Journal Article %A Borassi, Michele %A Natale, Emanuele %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation : %G eng %U http://hdl.handle.net/21.11116/0000-0003-7A10-2 %R 10.1145/3284359 %7 2019 %D 2019 %J Journal of Experimental Algorithmics %V 24 %N 1 %Z sequence number: 1.2 %I ACM %C New York, NY %@ false
[19]
K. Bringmann, M. Künnemann, and K. Węgrzycki, “Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max,” in STOC’19, 51st Annual ACM Symposium on the Theory of Computing, Phoenix, AZ, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Bringmann_STOC2019, TITLE = {Approximating {APSP} without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max}, AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and W{\c e}grzycki, Karol}, LANGUAGE = {eng}, PUBLISHER = {ACM}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {STOC'19, 51st Annual ACM Symposium on the Theory of Computing}, ADDRESS = {Phoenix, AZ, USA}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A K&#252;nnemann, Marvin %A W&#281;grzycki, Karol %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max : %G eng %U http://hdl.handle.net/21.11116/0000-0002-FC7A-A %D 2019 %B 51st Annual ACM Symposium on the Theory of Computing %Z date of event: 2019-06-23 - 2019-06-26 %C Phoenix, AZ, USA %B STOC'19 %I ACM
[20]
K. Bringmann, R. Keusch, and J. Lengler, “Geometric Inhomogeneous Random Graphs,” Theoretical Computer Science, vol. 760, 2019.
Export
BibTeX
@article{BringmannTCS2019, TITLE = {Geometric Inhomogeneous Random Graphs}, AUTHOR = {Bringmann, Karl and Keusch, Ralph and Lengler, Johannes}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2018.08.014}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Theoretical Computer Science}, VOLUME = {760}, PAGES = {35--54}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A Keusch, Ralph %A Lengler, Johannes %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Geometric Inhomogeneous Random Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0B00-1 %R 10.1016/j.tcs.2018.08.014 %7 2018 %D 2019 %J Theoretical Computer Science %V 760 %& 35 %P 35 - 54 %I Elsevier %C Amsterdam %@ false
[21]
K. Bringmann, T. Husfeldt, and M. Magnusson, “Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth,” in 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2019.
Export
BibTeX
@inproceedings{Bringmann_IPEC2018, TITLE = {Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth}, AUTHOR = {Bringmann, Karl and Husfeldt, Thore and Magnusson, M{\aa}ns}, LANGUAGE = {eng}, ISBN = {978-3-95977-084-2}, URL = {urn:nbn:de:0030-drops-102050}, DOI = {10.4230/LIPIcs.IPEC.2018.4}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2018}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, EDITOR = {Paul, Christophe and Pilipczuk, Michal}, PAGES = {1--13}, EID = {4}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {115}, ADDRESS = {Helsinki, Finland}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Husfeldt, Thore %A Magnusson, M&#229;ns %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9CFE-1 %R 10.4230/LIPIcs.IPEC.2018.4 %U urn:nbn:de:0030-drops-102050 %D 2019 %B 13th International Symposium on Parameterized and Exact Computation %Z date of event: 2018-08-20 - 2018-08-24 %C Helsinki, Finland %B 13th International Symposium on Parameterized and Exact Computation %E Paul, Christophe; Pilipczuk, Michal %P 1 - 13 %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-084-2 %B Leibniz International Proceedings in Informatics %N 115 %U http://drops.dagstuhl.de/opus/volltexte/2019/10205/http://drops.dagstuhl.de/doku/urheberrecht1.html
[22]
K. Bringmann, M. Künnemann, and P. Wellnitz, “Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Bringmann_SODA19c, TITLE = {Few Matches or Almost Periodicity: {F}aster Pattern Matching with Mismatches in Compressed Texts}, AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and Wellnitz, Philip}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.69}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {1126--1145}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A K&#252;nnemann, Marvin %A Wellnitz, Philip %+ 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 Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E1F-B %R 10.1137/1.9781611975482.69 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 1126 - 1145 %I SIAM %@ 978-1-61197-548-2
[23]
K. Bringmann, M. Künnemann, and A. Nusser, “Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Bringmann_SODA19d, TITLE = {{F}r\'{e}chet Distance Under Translation: {C}onditional Hardness and an Algorithm via Offline Dynamic Grid Reachability}, AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and Nusser, Andr{\'e}}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.180}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {2902--2921}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %+ 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 Fr&#233;chet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E29-F %R 10.1137/1.9781611975482.180 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 2902 - 2921 %I SIAM %@ 978-1-61197-548-2
[24]
K. Bringmann, M. Künnemann, and A. Nusser, “Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, USA, 2019.
Export
BibTeX
@inproceedings{Bringmann_SoCG2019, TITLE = {Walking the Dog Fast in Practice: {A}lgorithm Engineering of the {F}r\'{e}chet Distance}, AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and Nusser, Andr{\'e}}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-104-7}, URL = {urn:nbn:de:0030-drops-104219}, DOI = {10.4230/LIPIcs.SoCG.2019.17}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {35th International Symposium on Computational Geometry (SoCG 2019)}, EDITOR = {Barequet, Gill and Wang, Yusu}, PAGES = {1--21}, EID = {17}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {129}, ADDRESS = {Portland, OR, USA}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %+ 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 Walking the Dog Fast in Practice: Algorithm Engineering of the Fr&#233;chet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-0003-65C1-1 %R 10.4230/LIPIcs.SoCG.2019.17 %U urn:nbn:de:0030-drops-104219 %D 2019 %B 35th International Symposium on Computational Geometry %Z date of event: 2019-06-18 - 2019-06-21 %C Portland, OR, USA %B 35th International Symposium on Computational Geometry %E Barequet, Gill; Wang, Yusu %P 1 - 21 %Z sequence number: 17 %I Schloss Dagstuhl %@ 978-3-95977-104-7 %B Leibniz International Proceedings in Informatics %N 129 %@ false %U http://drops.dagstuhl.de/opus/volltexte/2019/10421/http://drops.dagstuhl.de/doku/urheberrecht1.html
[25]
K. Bringmann and B. Ray Chaudhury, “Polyline Simplification has Cubic Complexity,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, USA, 2019.
Export
BibTeX
@inproceedings{Bringmann_SoCG2019b, TITLE = {Polyline Simplification has Cubic Complexity}, AUTHOR = {Bringmann, Karl and Ray Chaudhury, Bhaskar}, LANGUAGE = {eng}, ISBN = {978-3-95977-104-7}, URL = {urn:nbn:de:0030-drops-104224}, DOI = {10.4230/LIPIcs.SoCG.2019.18}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {35th International Symposium on Computational Geometry (SoCG 2019)}, EDITOR = {Barequet, Gill and Wang, Yusu}, PAGES = {1--16}, EID = {18}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {129}, ADDRESS = {Portland, OR, USA}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Ray Chaudhury, Bhaskar %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Polyline Simplification has Cubic Complexity : %G eng %U http://hdl.handle.net/21.11116/0000-0003-65C8-A %R 10.4230/LIPIcs.SoCG.2019.18 %U urn:nbn:de:0030-drops-104224 %D 2019 %B 35th International Symposium on Computational Geometry %Z date of event: 2019-06-18 - 2019-06-21 %C Portland, OR, USA %B 35th International Symposium on Computational Geometry %E Barequet, Gill; Wang, Yusu %P 1 - 16 %Z sequence number: 18 %I Schloss Dagstuhl %@ 978-3-95977-104-7 %B Leibniz International Proceedings in Informatics %N 129 %U http://drops.dagstuhl.de/opus/volltexte/2019/10422/http://drops.dagstuhl.de/doku/urheberrecht1.html
[26]
K. Bringmann, F. Grandoni, B. Saha, and V. Vassilevska Williams, “Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product,” SIAM Journal on Computing, vol. 48, no. 2, 2019.
Export
BibTeX
@article{Bringmann_Truly2019, TITLE = {Truly Subcubic Algorithms for Language Edit Distance and {RNA} Folding via Fast Bounded-Difference Min-Plus Product}, AUTHOR = {Bringmann, Karl and Grandoni, Fabrizio and Saha, Barna and Vassilevska Williams, Virginia}, LANGUAGE = {eng}, ISSN = {0097-5397}, DOI = {10.1137/17M112720X}, PUBLISHER = {SIAM}, ADDRESS = {Philadelphia, PA}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {48}, NUMBER = {2}, PAGES = {481--512}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A Grandoni, Fabrizio %A Saha, Barna %A Vassilevska Williams, Virginia %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7E4-F %R 10.1137/17M112720X %7 2019 %D 2019 %J SIAM Journal on Computing %V 48 %N 2 %& 481 %P 481 - 512 %I SIAM %C Philadelphia, PA %@ false
[27]
K. Bringmann, “Fine-Grained Complexity Theory (Tutorial),” in 36th Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany, 2019.
Export
BibTeX
@inproceedings{Bringmann_STACS2019, TITLE = {Fine-Grained Complexity Theory (Tutorial)}, AUTHOR = {Bringmann, Karl}, LANGUAGE = {eng}, ISBN = {978-3-95977-100-9}, DOI = {10.4230/LIPIcs.STACS.2019.4}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {36th Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, EDITOR = {Niedermeier, Rolf and Paul, Christophe}, PAGES = {1--7}, EID = {4}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {126}, ADDRESS = {Berlin, Germany}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fine-Grained Complexity Theory (Tutorial) : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B36E-8 %R 10.4230/LIPIcs.STACS.2019.4 %D 2019 %B 36th Symposium on Theoretical Aspects of Computer Science %Z date of event: 2019-03-13 - 2019-03-16 %C Berlin, Germany %B 36th Symposium on Theoretical Aspects of Computer Science %E Niedermeier, Rolf; Paul, Christophe %P 1 - 7 %Z sequence number: 4 %I Schloss Dagstuhl %@ 978-3-95977-100-9 %B Leibniz International Proceedings in Informatics %N 126 %U http://drops.dagstuhl.de/opus/volltexte/2019/10243/http://drops.dagstuhl.de/doku/urheberrecht1.html
[28]
J. Bund, C. Lenzen, and W. Rosenbaum, “Fault Tolerant Gradient Clock Synchronization,” 2019. [Online]. Available: http://arxiv.org/abs/1902.08042. (arXiv: 1902.08042)
Abstract
Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems and the dependence of local and global worst-case skews (i.e., maximum clock difference between neighbors and arbitrary pairs of nodes, respectively) on the diameter of fault-free systems. However, so far nothing non-trivial is known about the local skew that can be achieved in topologies that are not fully connected even under a single Byzantine fault. Put simply, in this work we show that the most powerful known techniques for fault-tolerant and gradient clock synchronization are compatible, in the sense that the best of both worlds can be achieved simultaneously. Concretely, we combine the Lynch-Welch algorithm [Welch1988] for synchronizing a clique of $n$ nodes despite up to $f<n/3$ Byzantine faults with the gradient clock synchronization (GCS) algorithm by Lenzen et al. [Lenzen2010] in order to render the latter resilient to faults. As this is not possible on general graphs, we augment an input graph $\mathcal{G}$ by replacing each node by $3f+1$ fully connected copies, which execute an instance of the Lynch-Welch algorithm. We then interpret these clusters as supernodes executing the GCS algorithm, where for each cluster its correct nodes' Lynch-Welch clocks provide estimates of the logical clock of the supernode in the GCS algorithm. By connecting clusters corresponding to neighbors in $\mathcal{G}$ in a fully bipartite manner, supernodes can inform each other about (estimates of) their logical clock values. This way, we achieve asymptotically optimal local skew, granted that no cluster contains more than $f$ faulty nodes, at factor $O(f)$ and $O(f^2)$ overheads in terms of nodes and edges, respectively. Note that tolerating $f$ faulty neighbors trivially requires degree larger than $f$, so this is asymptotically optimal as well.
Export
BibTeX
@online{Bund_arXiv1902.08042, TITLE = {Fault Tolerant Gradient Clock Synchronization}, AUTHOR = {Bund, Johannes and Lenzen, Christoph and Rosenbaum, Will}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1902.08042}, EPRINT = {1902.08042}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems and the dependence of local and global worst-case skews (i.e., maximum clock difference between neighbors and arbitrary pairs of nodes, respectively) on the diameter of fault-free systems. However, so far nothing non-trivial is known about the local skew that can be achieved in topologies that are not fully connected even under a single Byzantine fault. Put simply, in this work we show that the most powerful known techniques for fault-tolerant and gradient clock synchronization are compatible, in the sense that the best of both worlds can be achieved simultaneously. Concretely, we combine the Lynch-Welch algorithm [Welch1988] for synchronizing a clique of $n$ nodes despite up to $f<n/3$ Byzantine faults with the gradient clock synchronization (GCS) algorithm by Lenzen et al. [Lenzen2010] in order to render the latter resilient to faults. As this is not possible on general graphs, we augment an input graph $\mathcal{G}$ by replacing each node by $3f+1$ fully connected copies, which execute an instance of the Lynch-Welch algorithm. We then interpret these clusters as supernodes executing the GCS algorithm, where for each cluster its correct nodes' Lynch-Welch clocks provide estimates of the logical clock of the supernode in the GCS algorithm. By connecting clusters corresponding to neighbors in $\mathcal{G}$ in a fully bipartite manner, supernodes can inform each other about (estimates of) their logical clock values. This way, we achieve asymptotically optimal local skew, granted that no cluster contains more than $f$ faulty nodes, at factor $O(f)$ and $O(f^2)$ overheads in terms of nodes and edges, respectively. Note that tolerating $f$ faulty neighbors trivially requires degree larger than $f$, so this is asymptotically optimal as well.}, }
Endnote
%0 Report %A Bund, Johannes %A Lenzen, Christoph %A Rosenbaum, Will %+ 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 Fault Tolerant Gradient Clock Synchronization : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0CD6-F %U http://arxiv.org/abs/1902.08042 %D 2019 %X Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems and the dependence of local and global worst-case skews (i.e., maximum clock difference between neighbors and arbitrary pairs of nodes, respectively) on the diameter of fault-free systems. However, so far nothing non-trivial is known about the local skew that can be achieved in topologies that are not fully connected even under a single Byzantine fault. Put simply, in this work we show that the most powerful known techniques for fault-tolerant and gradient clock synchronization are compatible, in the sense that the best of both worlds can be achieved simultaneously. Concretely, we combine the Lynch-Welch algorithm [Welch1988] for synchronizing a clique of $n$ nodes despite up to $f<n/3$ Byzantine faults with the gradient clock synchronization (GCS) algorithm by Lenzen et al. [Lenzen2010] in order to render the latter resilient to faults. As this is not possible on general graphs, we augment an input graph $\mathcal{G}$ by replacing each node by $3f+1$ fully connected copies, which execute an instance of the Lynch-Welch algorithm. We then interpret these clusters as supernodes executing the GCS algorithm, where for each cluster its correct nodes' Lynch-Welch clocks provide estimates of the logical clock of the supernode in the GCS algorithm. By connecting clusters corresponding to neighbors in $\mathcal{G}$ in a fully bipartite manner, supernodes can inform each other about (estimates of) their logical clock values. This way, we achieve asymptotically optimal local skew, granted that no cluster contains more than $f$ faulty nodes, at factor $O(f)$ and $O(f^2)$ overheads in terms of nodes and edges, respectively. Note that tolerating $f$ faulty neighbors trivially requires degree larger than $f$, so this is asymptotically optimal as well. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Data Structures and Algorithms, cs.DS
[29]
P. Bürgisser, C. Ikenmeyer, and G. Panova, “No Occurrence Obstructions in Geometric Complexity Theory,” Journal of the American Mathematical Society, vol. 32, 2019.
Export
BibTeX
@article{Buergisser2019, TITLE = {No Occurrence Obstructions in Geometric Complexity Theory}, AUTHOR = {B{\"u}rgisser, Peter and Ikenmeyer, Christian and Panova, Greta}, LANGUAGE = {eng}, ISSN = {0894-0347}, DOI = {10.1090/jams/908}, PUBLISHER = {The Society}, ADDRESS = {Providence, R.I.}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Journal of the American Mathematical Society}, VOLUME = {32}, PAGES = {163--193}, }
Endnote
%0 Journal Article %A B&#252;rgisser, Peter %A Ikenmeyer, Christian %A Panova, Greta %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T No Occurrence Obstructions in Geometric Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0002-72B9-D %R 10.1090/jams/908 %7 2018 %D 2019 %J Journal of the American Mathematical Society %O J. Amer. Math. Soc. %V 32 %& 163 %P 163 - 193 %I The Society %C Providence, R.I. %@ false
[30]
P. Chalermsook, A. Schmid, and S. Uniyal, “A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs,” in 36th Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany, 2019.
Export
BibTeX
@inproceedings{Chalermsook_STACS2019, TITLE = {A Tight Extremal Bound on the {Lov\'{a}sz} Cactus Number in Planar Graphs}, AUTHOR = {Chalermsook, Parinya and Schmid, Andreas and Uniyal, Sumedha}, LANGUAGE = {eng}, ISBN = {978-3-95977-100-9}, DOI = {10.4230/LIPIcs.STACS.2019.19}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {36th Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, EDITOR = {Niedermeier, Rolf and Paul, Christophe}, PAGES = {1--14}, EID = {19}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {126}, ADDRESS = {Berlin, Germany}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Schmid, Andreas %A Uniyal, Sumedha %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Tight Extremal Bound on the Lov&#225;sz Cactus Number in Planar Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5D6-A %R 10.4230/LIPIcs.STACS.2019.19 %D 2019 %B 36th Symposium on Theoretical Aspects of Computer Science %Z date of event: 2019-03-13 - 2019-03-16 %C Berlin, Germany %B 36th Symposium on Theoretical Aspects of Computer Science %E Niedermeier, Rolf; Paul, Christophe %P 1 - 14 %Z sequence number: 19 %I Schloss Dagstuhl %@ 978-3-95977-100-9 %B Leibniz International Proceedings in Informatics %N 126 %U http://drops.dagstuhl.de/doku/urheberrecht1.htmlhttp://drops.dagstuhl.de/opus/volltexte/2019/10258/
[31]
L. S. Chandran, D. Issac, and S. Zhou, “Hadwiger’s Conjecture for Squares of 2-Trees,” European Journal of Combinatorics, vol. 76, 2019.
Export
BibTeX
@article{CHANDRAN2019hadwiger, TITLE = {Hadwiger's Conjecture for Squares of 2-Trees}, AUTHOR = {Chandran, L. Sunil and Issac, Davis and Zhou, Sanming}, LANGUAGE = {eng}, ISSN = {0195-6698}, DOI = {10.1016/j.ejc.2018.10.003}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {European Journal of Combinatorics}, VOLUME = {76}, PAGES = {159--174}, }
Endnote
%0 Journal Article %A Chandran, L. Sunil %A Issac, Davis %A Zhou, Sanming %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Hadwiger's Conjecture for Squares of 2-Trees : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E5B-7 %R 10.1016/j.ejc.2018.10.003 %7 2018 %D 2019 %J European Journal of Combinatorics %V 76 %& 159 %P 159 - 174 %I Elsevier %C Amsterdam %@ false
[32]
L. Chen, F. Eberle, N. Megow, K. Schewior, and C. Stein, “A General Framework for Handling Commitment in Online Admission Control,” in Integer Programming and Combinatorial Optimization (IPCO 2019), Ann Arbor, MI, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{SchewiorIPCO2019, TITLE = {A General Framework for Handling Commitment in Online Admission Control}, AUTHOR = {Chen, Lin and Eberle, Franziska and Megow, Nicole and Schewior, Kevin and Stein, Clifford}, LANGUAGE = {eng}, PUBLISHER = {Springer}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Integer Programming and Combinatorial Optimization (IPCO 2019)}, ADDRESS = {Ann Arbor, MI, USA}, }
Endnote
%0 Conference Proceedings %A Chen, Lin %A Eberle, Franziska %A Megow, Nicole %A Schewior, Kevin %A Stein, Clifford %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A General Framework for Handling Commitment in Online Admission Control : %G eng %U http://hdl.handle.net/21.11116/0000-0002-F4CC-5 %D 2019 %B 20th Conference on Integer Programming and Combinatorial Optimization %Z date of event: 2019-05-22 - 2019-05-24 %C Ann Arbor, MI, USA %B Integer Programming and Combinatorial Optimization %I Springer
[33]
Y. K. Cheung, M. Hoefer, and P. Nakhe, “Tracing Equilibrium in Dynamic Markets via Distributed Adaptation,” in AAMAS’19, 18th International Conference on Autonomous Agents and Multiagent Systems, Montreal, Canada, 2019.
Export
BibTeX
@inproceedings{aamas19-CHN, TITLE = {Tracing Equilibrium in Dynamic Markets via Distributed Adaptation}, AUTHOR = {Cheung, Yun Kuen and Hoefer, Martin and Nakhe, Paresh}, LANGUAGE = {eng}, ISBN = {978-1-4503-6309-9}, URL = {http://dl.acm.org/citation.cfm?id=3306127.3331825}, PUBLISHER = {ACM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {AAMAS'19, 18th International Conference on Autonomous Agents and Multiagent Systems}, PAGES = {1225--1233}, ADDRESS = {Montreal, Canada}, }
Endnote
%0 Conference Proceedings %A Cheung, Yun Kuen %A Hoefer, Martin %A Nakhe, Paresh %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Tracing Equilibrium in Dynamic Markets via Distributed Adaptation : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5FE-E %U http://dl.acm.org/citation.cfm?id=3306127.3331825 %D 2019 %B 18th International Conference on Autonomous Agents and Multiagent Systems %Z date of event: 2019-05-13 - 2019-05-17 %C Montreal, Canada %B AAMAS'19 %P 1225 - 1233 %I ACM %@ 978-1-4503-6309-9
[34]
L. Chiantini, C. Ikenmeyer, J. M. Landsberg, and G. Ottaviani, “The Geometry of Rank Decompositions of Matrix Multiplication I: 2x2 Matrices,” Experimental Mathematics, vol. 28, no. 3, 2019.
Export
BibTeX
@article{Chiantini2017, TITLE = {The geometry of rank decompositions of matrix multiplication I: $2\times 2$ matrices}, AUTHOR = {Chiantini, Luca and Ikenmeyer, Christian and Landsberg, J. M. and Ottaviani, Giorgio}, LANGUAGE = {eng}, ISSN = {1058-6458}, DOI = {10.1080/10586458.2017.1403981}, PUBLISHER = {Taylor \& Francis}, ADDRESS = {Boston, MA}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Experimental Mathematics}, VOLUME = {28}, NUMBER = {3}, PAGES = {322--327}, }
Endnote
%0 Journal Article %A Chiantini, Luca %A Ikenmeyer, Christian %A Landsberg, J. M. %A Ottaviani, Giorgio %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T The Geometry of Rank Decompositions of Matrix Multiplication I: 2x2 Matrices : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AB12-9 %R 10.1080/10586458.2017.1403981 %7 2017 %D 2019 %J Experimental Mathematics %V 28 %N 3 %& 322 %P 322 - 327 %I Taylor & Francis %C Boston, MA %@ false
[35]
A. Choudhary and A. Ghosh, “Delaunay Simplices in Diagonally Distorted Lattices,” Computational Geometry: Theory and Applications. (Accepted/in press)
Export
BibTeX
@article{Choudhary-diagonal, TITLE = {Delaunay Simplices in Diagonally Distorted Lattices}, AUTHOR = {Choudhary, Aruni and Ghosh, Arijit}, LANGUAGE = {eng}, ISSN = {0925-7721}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, JOURNAL = {Computational Geometry: Theory and Applications}, }
Endnote
%0 Journal Article %A Choudhary, Aruni %A Ghosh, Arijit %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Delaunay Simplices in Diagonally Distorted Lattices : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5C1-1 %D 2019 %J Computational Geometry: Theory and Applications %I Elsevier %C Amsterdam %@ false
[36]
A. Choudhary, M. Kerber, and S. Raghvendra, “Improved Topological Approximations by Digitization,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Choudhary-digital, TITLE = {Improved Topological Approximations by Digitization}, AUTHOR = {Choudhary, Aruni and Kerber, Michael and Raghvendra, Sharath}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.166}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {2675--2688}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Choudhary, Aruni %A Kerber, Michael %A Raghvendra, Sharath %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Improved Topological Approximations by Digitization : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5BC-8 %R 10.1137/1.9781611975482.166 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 2675 - 2688 %I SIAM %@ 978-1-61197-548-2
[37]
A. Choudhary, M. Kerber, and S. Raghvendra, “Polynomial-Sized Topological Approximations Using the Permutahedron,” Discrete & Computational Geometry, vol. 61, no. 1, 2019.
Export
BibTeX
@article{Choudhary-polynomial-dcg, TITLE = {Polynomial-Sized Topological Approximations Using the Permutahedron}, AUTHOR = {Choudhary, Aruni and Kerber, Michael and Raghvendra, Sharat}, LANGUAGE = {eng}, ISSN = {0179-5376}, DOI = {10.1007/s00454-017-9951-2}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Discrete \& Computational Geometry}, VOLUME = {61}, NUMBER = {1}, PAGES = {42--80}, }
Endnote
%0 Journal Article %A Choudhary, Aruni %A Kerber, Michael %A Raghvendra, Sharat %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Polynomial-Sized Topological Approximations Using the Permutahedron : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5B6-E %R 10.1007/s00454-017-9951-2 %7 2017 %D 2019 %J Discrete & Computational Geometry %V 61 %N 1 %& 42 %P 42 - 80 %I Springer %C New York, NY %@ false
[38]
J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld, “Recent Developments in Prophet Inequalities,” ACM SIGecom Exchanges, vol. 17, no. 1, 2019.
Export
BibTeX
@article{Correa2018, TITLE = {Recent Developments in Prophet Inequalities}, AUTHOR = {Correa, Jos{\'e} and Foncea, Patricio and Hoeksma, Ruben and Oosterwijk, Tim and Vredeveld, Tjark}, LANGUAGE = {eng}, ISSN = {1551-9031}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, JOURNAL = {ACM SIGecom Exchanges}, VOLUME = {17}, NUMBER = {1}, PAGES = {60--61}, }
Endnote
%0 Journal Article %A Correa, Jos&#233; %A Foncea, Patricio %A Hoeksma, Ruben %A Oosterwijk, Tim %A Vredeveld, Tjark %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Recent Developments in Prophet Inequalities : %G eng %U http://hdl.handle.net/21.11116/0000-0002-9E6F-1 %7 2019 %D 2019 %J ACM SIGecom Exchanges %V 17 %N 1 %& 60 %P 60 - 61 %I ACM %C New York, NY %@ false %U http://www.sigecom.org/exchanges/volume_17/1/CORREA.pdf
[39]
E. Cruciani, E. Natale, and G. Scornavacca, “Rigorous Analysis of a Label Propagation Algorithm for Distributed Community Detection,” in Thirty-Third AAAI Conference on Artificial Intelligence, Honolulu, HI, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Cruciani_aaai18, TITLE = {Rigorous Analysis of a Label Propagation Algorithm for Distributed Community Detection}, AUTHOR = {Cruciani, Emilio and Natale, Emanuele and Scornavacca, Giacomo}, LANGUAGE = {eng}, PUBLISHER = {AAAI}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Thirty-Third AAAI Conference on Artificial Intelligence}, ADDRESS = {Honolulu, HI, USA}, }
Endnote
%0 Conference Proceedings %A Cruciani, Emilio %A Natale, Emanuele %A Scornavacca, Giacomo %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Rigorous Analysis of a Label Propagation Algorithm for Distributed Community Detection : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A985-9 %D 2018 %B Thirty-Third AAAI Conference on Artificial Intelligence %Z date of event: 2019-01-27 - 2019-02-01 %C Honolulu, HI, USA %B Thirty-Third AAAI Conference on Artificial Intelligence %I AAAI
[40]
J. Dörfler, C. Ikenmeyer, and G. Panova, “On Geometric Complexity Theory: Multiplicity Obstructions are Stronger than Occurrence Obstructions,” 2019. [Online]. Available: http://arxiv.org/abs/1901.04576. (arXiv: 1901.04576)
Abstract
Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and B\"urgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite's reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases.
Export
BibTeX
@online{Doerfler_arXiv1901.04576, TITLE = {On Geometric Complexity Theory: {M}ultiplicity Obstructions are Stronger than Occurrence Obstructions}, AUTHOR = {D{\"o}rfler, Julian and Ikenmeyer, Christian and Panova, Greta}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1901.04576}, EPRINT = {1901.04576}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and B\"urgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite's reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases.}, }
Endnote
%0 Report %A D&#246;rfler, Julian %A Ikenmeyer, Christian %A Panova, Greta %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On Geometric Complexity Theory: Multiplicity Obstructions are Stronger than Occurrence Obstructions : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B393-C %U http://arxiv.org/abs/1901.04576 %D 2019 %X Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. The papers also conjecture that the vanishing behavior of these multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and B\"urgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. This paper provides for the first time a setting where separating with multiplicities can be achieved, while the separation with occurrences is provably impossible. Our setting is surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite's reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases. %K Computer Science, Computational Complexity, cs.CC,Mathematics, Algebraic Geometry, math.AG,Mathematics, Combinatorics, math.CO,Mathematics, Representation Theory, math.RT,
[41]
L. Duraj, M. Künnemann, and A. Polak, “Tight Conditional Lower Bounds for Longest Common Increasing Subsequence,” Algorithmica, vol. 81, no. 10, 2019.
Export
BibTeX
@article{Duraj2018, TITLE = {Tight Conditional Lower Bounds for Longest Common Increasing Subsequence}, AUTHOR = {Duraj, Lech and K{\"u}nnemann, Marvin and Polak, Adam}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-018-0485-7}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Algorithmica}, VOLUME = {81}, NUMBER = {10}, PAGES = {3968--3992}, }
Endnote
%0 Journal Article %A Duraj, Lech %A K&#252;nnemann, Marvin %A Polak, Adam %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Tight Conditional Lower Bounds for Longest Common Increasing Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-0002-A906-9 %R 10.1007/s00453-018-0485-7 %7 2018 %D 2019 %J Algorithmica %V 81 %N 10 %& 3968 %P 3968 - 3992 %I Springer %C New York, NY %@ false
[42]
T. Eden, D. Ron, and W. Rosenbaum, “The Arboricity Captures the Complexity of Sampling Edges,” 2019. [Online]. Available: http://arxiv.org/abs/1902.08086. (arXiv: 1902.08086)
Abstract
In this paper, we revisit the problem of sampling edges in an unknown graph $G = (V, E)$ from a distribution that is (pointwise) almost uniform over $E$. We consider the case where there is some a priori upper bound on the arboriciy of $G$. Given query access to a graph $G$ over $n$ vertices and of average degree $d$ and arboricity at most $\alpha$, we design an algorithm that performs $O\!\left(\frac{\alpha}{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$ queries in expectation and returns an edge in the graph such that every edge $e \in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm performs two types of queries: degree queries and neighbor queries. We show that the upper bound is tight (up to poly-logarithmic factors and the dependence in $\varepsilon$), as $\Omega\!\left(\frac{\alpha}{d} \right)$ queries are necessary for the easier task of sampling edges from any distribution over $E$ that is close to uniform in total variational distance. We also prove that even if $G$ is a tree (i.e., $\alpha = 1$ so that $\frac{\alpha}{d}=\Theta(1)$), $\Omega\left(\frac{\log n}{\log\log n}\right)$ queries are necessary to sample an edge from any distribution that is pointwise close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is necessary for constant $\alpha$. Finally we show how our algorithm can be applied to obtain a new result on approximately counting subgraphs, based on the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019).
Export
BibTeX
@online{Eden_arXiv1902.08086, TITLE = {The Arboricity Captures the Complexity of Sampling Edges}, AUTHOR = {Eden, Talya and Ron, Dana and Rosenbaum, Will}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1902.08086}, EPRINT = {1902.08086}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {In this paper, we revisit the problem of sampling edges in an unknown graph $G = (V, E)$ from a distribution that is (pointwise) almost uniform over $E$. We consider the case where there is some a priori upper bound on the arboriciy of $G$. Given query access to a graph $G$ over $n$ vertices and of average degree $d$ and arboricity at most $\alpha$, we design an algorithm that performs $O\!\left(\frac{\alpha}{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$ queries in expectation and returns an edge in the graph such that every edge $e \in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm performs two types of queries: degree queries and neighbor queries. We show that the upper bound is tight (up to poly-logarithmic factors and the dependence in $\varepsilon$), as $\Omega\!\left(\frac{\alpha}{d} \right)$ queries are necessary for the easier task of sampling edges from any distribution over $E$ that is close to uniform in total variational distance. We also prove that even if $G$ is a tree (i.e., $\alpha = 1$ so that $\frac{\alpha}{d}=\Theta(1)$), $\Omega\left(\frac{\log n}{\log\log n}\right)$ queries are necessary to sample an edge from any distribution that is pointwise close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is necessary for constant $\alpha$. Finally we show how our algorithm can be applied to obtain a new result on approximately counting subgraphs, based on the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019).}, }
Endnote
%0 Report %A Eden, Talya %A Ron, Dana %A Rosenbaum, Will %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T The Arboricity Captures the Complexity of Sampling Edges : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0CD0-5 %U http://arxiv.org/abs/1902.08086 %D 2019 %X In this paper, we revisit the problem of sampling edges in an unknown graph $G = (V, E)$ from a distribution that is (pointwise) almost uniform over $E$. We consider the case where there is some a priori upper bound on the arboriciy of $G$. Given query access to a graph $G$ over $n$ vertices and of average degree $d$ and arboricity at most $\alpha$, we design an algorithm that performs $O\!\left(\frac{\alpha}{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$ queries in expectation and returns an edge in the graph such that every edge $e \in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm performs two types of queries: degree queries and neighbor queries. We show that the upper bound is tight (up to poly-logarithmic factors and the dependence in $\varepsilon$), as $\Omega\!\left(\frac{\alpha}{d} \right)$ queries are necessary for the easier task of sampling edges from any distribution over $E$ that is close to uniform in total variational distance. We also prove that even if $G$ is a tree (i.e., $\alpha = 1$ so that $\frac{\alpha}{d}=\Theta(1)$), $\Omega\left(\frac{\log n}{\log\log n}\right)$ queries are necessary to sample an edge from any distribution that is pointwise close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is necessary for constant $\alpha$. Finally we show how our algorithm can be applied to obtain a new result on approximately counting subgraphs, based on the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019). %K Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
[43]
P. Fraigniaud and E. Natale, “Noisy Rumor Spreading and Plurality Consensus,” Distributed Computing, vol. 32, no. 4, 2019.
Export
BibTeX
@article{Fraigniaud2018, TITLE = {Noisy Rumor Spreading and Plurality Consensus}, AUTHOR = {Fraigniaud, Pierre and Natale, Emanuele}, LANGUAGE = {eng}, ISSN = {0178-2770}, DOI = {10.1007/s00446-018-0335-5}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Distributed Computing}, VOLUME = {32}, NUMBER = {4}, PAGES = {257--276}, }
Endnote
%0 Journal Article %A Fraigniaud, Pierre %A Natale, Emanuele %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Noisy Rumor Spreading and Plurality Consensus : %G eng %U http://hdl.handle.net/21.11116/0000-0002-6CD7-3 %R 10.1007/s00446-018-0335-5 %7 2018 %D 2019 %J Distributed Computing %V 32 %N 4 %& 257 %P 257 - 276 %I Springer International %C Berlin %@ false
[44]
F. Grandoni, B. Laekhanukit, and S. Li, “O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm,” in STOC’19, 51st Annual ACM Symposium on the Theory of Computing, Phoenix, AZ, USA, 2019.
Export
BibTeX
@inproceedings{Grandoni_STOC2019, TITLE = {{$O(\log^2k/\log\log{k})$}-Approximation Algorithm for Directed {S}teiner Tree: A Tight Quasi-Polynomial-Time Algorithm}, AUTHOR = {Grandoni, Fabrizio and Laekhanukit, Bundit and Li, Shi}, LANGUAGE = {eng}, ISBN = {978-1-4503-6705-9}, DOI = {10.1145/3313276.3316349}, PUBLISHER = {ACM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {STOC'19, 51st Annual ACM Symposium on the Theory of Computing}, PAGES = {253--264}, ADDRESS = {Phoenix, AZ, USA}, }
Endnote
%0 Conference Proceedings %A Grandoni, Fabrizio %A Laekhanukit, Bundit %A Li, Shi %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm : %G eng %U http://hdl.handle.net/21.11116/0000-0003-1625-B %R 10.1145/3313276.3316349 %D 2019 %B 51st Annual ACM Symposium on the Theory of Computing %Z date of event: 2019-06-23 - 2019-06-26 %C Phoenix, AZ, USA %B STOC'19 %P 253 - 264 %I ACM %@ 978-1-4503-6705-9
[45]
Y. Ibrahim, M. Riedewald, G. Weikum, and D. Zeinalipour-Yazti, “Bridging Quantities in Tables and Text,” in ICDE 2019, 35th IEEE International Conference on Data Engineering, Macau, China, 2019.
Export
BibTeX
@inproceedings{Ibrahim_ICDE2019, TITLE = {Bridging Quantities in Tables and Text}, AUTHOR = {Ibrahim, Yusra and Riedewald, Mirek and Weikum, Gerhard and Zeinalipour-Yazti, Demetrios}, LANGUAGE = {eng}, ISBN = {978-1-5386-7474-1}, DOI = {10.1109/ICDE.2019.00094}, PUBLISHER = {IEEE}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {ICDE 2019, 35th IEEE International Conference on Data Engineering}, PAGES = {1010--1021}, ADDRESS = {Macau, China}, }
Endnote
%0 Conference Proceedings %A Ibrahim, Yusra %A Riedewald, Mirek %A Weikum, Gerhard %A Zeinalipour-Yazti, Demetrios %+ Databases and Information Systems, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Databases and Information Systems, MPI for Informatics, Max Planck Society Databases and Information Systems, MPI for Informatics, Max Planck Society %T Bridging Quantities in Tables and Text : %G eng %U http://hdl.handle.net/21.11116/0000-0003-01AB-B %R 10.1109/ICDE.2019.00094 %D 2019 %B 35th IEEE International Conference on Data Engineering %Z date of event: 2019-04-08 - 2019-04-12 %C Macau, China %B ICDE 2019 %P 1010 - 1021 %I IEEE %@ 978-1-5386-7474-1
[46]
C. Ikenmeyer, B. Komarath, C. Lenzen, V. Lysikov, A. Mokhov, and K. Sreenivasaiah, “On the Complexity of Hazard-free Circuits,” Journal of the ACM, vol. 66, no. 4, 2019.
Export
BibTeX
@article{Ikenmeyer_JACM2019, TITLE = {On the Complexity of Hazard-free Circuits}, AUTHOR = {Ikenmeyer, Christian and Komarath, Balagopal and Lenzen, Christoph and Lysikov, Vladimir and Mokhov, Andrey and Sreenivasaiah, Karteek}, LANGUAGE = {eng}, ISSN = {0004-5411}, DOI = {10.1145/3320123}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Journal of the ACM}, VOLUME = {66}, NUMBER = {4}, EID = {25}, }
Endnote
%0 Journal Article %A Ikenmeyer, Christian %A Komarath, Balagopal %A Lenzen, Christoph %A Lysikov, Vladimir %A Mokhov, Andrey %A Sreenivasaiah, Karteek %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T On the Complexity of Hazard-free Circuits : %G eng %U http://hdl.handle.net/21.11116/0000-0004-8D51-2 %R 10.1145/3320123 %7 2019 %D 2019 %J Journal of the ACM %V 66 %N 4 %Z sequence number: 25 %I ACM %C New York, NY %@ false
[47]
G. Jindal and M. Bläser, “On the Complexity of Symmetric Polynomials,” in 10th Innovations in Theoretical Computer Science (ITCS 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Jindal_ITCS2019, TITLE = {On the Complexity of Symmetric Polynomials}, AUTHOR = {Jindal, Gorav and Bl{\"a}ser, Markus}, LANGUAGE = {eng}, ISBN = {978-3-95977-095-8}, URL = {urn:nbn:de:0030-drops-101402}, DOI = {10.4230/LIPIcs.ITCS.2019.47}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {10th Innovations in Theoretical Computer Science (ITCS 2019)}, EDITOR = {Blum, Avrim}, PAGES = {1--14}, EID = {47}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {124}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Jindal, Gorav %A Bl&#228;ser, Markus %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On the Complexity of Symmetric Polynomials : %G eng %U http://hdl.handle.net/21.11116/0000-0002-ABCC-8 %R 10.4230/LIPIcs.ITCS.2019.47 %U urn:nbn:de:0030-drops-101402 %D 2019 %B 10th Innovations in Theoretical Computer Science %Z date of event: 2019-01-10 - 2019-01-12 %C San Diego, CA, USA %B 10th Innovations in Theoretical Computer Science %E Blum, Avrim %P 1 - 14 %Z sequence number: 47 %I Schloss Dagstuhl %@ 978-3-95977-095-8 %B Leibniz International Proceedings in Informatics %N 124 %U http://drops.dagstuhl.de/opus/volltexte/2018/10140/http://drops.dagstuhl.de/doku/urheberrecht1.html
[48]
A. Karrenbauer, P. Kolev, and K. Mehlhorn, “Convergence of the Non-Uniform Physarum Dynamics,” 2019. [Online]. Available: http://arxiv.org/abs/1901.07231. (arXiv: 1901.07231)
Abstract
Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in \mathbb{Z}^n$. We show under fairly general conditions that the non-uniform Physarum dynamics $\dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right)$ converges to the optimum solution $x^*$ of the weighted basis pursuit problem minimize $c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$, and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| - x_e$ at time $t$ and in state $x$. Previously convergence was only shown for the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show convergence for the dynamics $\dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) - 1\right),$ where $g_e$ is an increasing differentiable function with $g_e(1) = 1$. Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges.
Export
BibTeX
@online{DBLP:journals/corr/abs-1901-07231, TITLE = {Convergence of the Non-Uniform Physarum Dynamics}, AUTHOR = {Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1901.07231}, EPRINT = {1901.07231}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in \mathbb{Z}^n$. We show under fairly general conditions that the non-uniform Physarum dynamics $\dot{x}_e = a_e(x,t) \left(|q_e| -- x_e\right)$ converges to the optimum solution $x^*$ of the weighted basis pursuit problem minimize $c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$, and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| - x_e$ at time $t$ and in state $x$. Previously convergence was only shown for the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show convergence for the dynamics $\dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) -- 1\right),$ where $g_e$ is an increasing differentiable function with $g_e(1) = 1$. Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges.}, }
Endnote
%0 Report %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Convergence of the Non-Uniform Physarum Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0002-F39F-9 %U http://arxiv.org/abs/1901.07231 %D 2019 %X Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in \mathbb{Z}^n$. We show under fairly general conditions that the non-uniform Physarum dynamics $\dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right)$ converges to the optimum solution $x^*$ of the weighted basis pursuit problem minimize $c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$, and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| - x_e$ at time $t$ and in state $x$. Previously convergence was only shown for the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show convergence for the dynamics $\dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) - 1\right),$ where $g_e$ is an increasing differentiable function with $g_e(1) = 1$. Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges. %K Computer Science, Data Structures and Algorithms, cs.DS
[49]
P. Khanchandani and C. Lenzen, “Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision,” Theory of Computing Systems, vol. 63, no. 2, 2019.
Export
BibTeX
@article{Khanchandani2018, TITLE = {Self-Stabilizing {B}yzantine Clock Synchronization with Optimal Precision}, AUTHOR = {Khanchandani, Pankaj and Lenzen, Christoph}, LANGUAGE = {eng}, ISSN = {1432-4350}, DOI = {10.1007/s00224-017-9840-3}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Theory of Computing Systems}, VOLUME = {63}, NUMBER = {2}, PAGES = {261--305}, }
Endnote
%0 Journal Article %A Khanchandani, Pankaj %A Lenzen, Christoph %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision : %G eng %U http://hdl.handle.net/21.11116/0000-0000-73AC-D %R 10.1007/s00224-017-9840-3 %7 2018-01-20 %D 2019 %J Theory of Computing Systems %V 63 %N 2 %& 261 %P 261 - 305 %I Springer %C New York, NY %@ false
[50]
A. Kinali, “A Physical Sine-to-Square Converter Noise Model,” in IEEE International Frequency Control Symposium (IFCS 2018), Olympic Valley, CA, USA, 2019.
Export
BibTeX
@inproceedings{Kinali_IFCS2018, TITLE = {A Physical Sine-to-Square Converter Noise Model}, AUTHOR = {Kinali, Attila}, LANGUAGE = {eng}, ISBN = {978-1-5386-3214-7}, DOI = {10.1109/FCS.2018.8597525}, PUBLISHER = {IEEE}, YEAR = {2018}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {IEEE International Frequency Control Symposium (IFCS 2018)}, PAGES = {383--388}, ADDRESS = {Olympic Valley, CA, USA}, }
Endnote
%0 Conference Proceedings %A Kinali, Attila %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Physical Sine-to-Square Converter Noise Model : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AC39-D %R 10.1109/FCS.2018.8597525 %D 2019 %B IEEE International Frequency Control Symposium %Z date of event: 2018-05-21 - 2018-05-24 %C Olympic Valley, CA, USA %B IEEE International Frequency Control Symposium %P 383 - 388 %I IEEE %@ 978-1-5386-3214-7
[51]
M. Künnemann, D. Moeller, R. Paturi, and S. Schneider, “Subquadratic Algorithms for Succinct Stable Matching,” Algorithmica, vol. 81, no. 7, 2019.
Export
BibTeX
@article{Kuennemann2019, TITLE = {Subquadratic Algorithms for Succinct Stable Matching}, AUTHOR = {K{\"u}nnemann, Marvin and Moeller, Daniel and Paturi, Ramamohan and Schneider, Stefan}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-019-00564-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Algorithmica}, VOLUME = {81}, NUMBER = {7}, PAGES = {2991--3024}, }
Endnote
%0 Journal Article %A K&#252;nnemann, Marvin %A Moeller, Daniel %A Paturi, Ramamohan %A Schneider, Stefan %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Subquadratic Algorithms for Succinct Stable Matching : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7E0-3 %R 10.1007/s00453-019-00564-x %7 2019 %D 2019 %J Algorithmica %V 81 %N 7 %& 2991 %P 2991 - 3024 %I Springer %C New York, NY %@ false
[52]
C. Lenzen, B. Patt-Shamir, and D. Peleg, “Distributed Distance Computation and Routing with Small Messages,” Distributed Computing, vol. 32, no. 2, 2019.
Export
BibTeX
@article{Lenzen_DC2018, TITLE = {Distributed Distance Computation and Routing with Small Messages}, AUTHOR = {Lenzen, Christoph and Patt-Shamir, Boaz and Peleg, David}, LANGUAGE = {eng}, ISSN = {0178-2770}, DOI = {10.1007/s00446-018-0326-6}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Distributed Computing}, VOLUME = {32}, NUMBER = {2}, PAGES = {133--157}, }
Endnote
%0 Journal Article %A Lenzen, Christoph %A Patt-Shamir, Boaz %A Peleg, David %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Distributed Distance Computation and Routing with Small Messages : %G eng %U http://hdl.handle.net/21.11116/0000-0002-6CD1-9 %R 10.1007/s00446-018-0326-6 %7 2018 %D 2019 %J Distributed Computing %V 32 %N 2 %& 133 %P 133 - 157 %I Springer International %C Berlin %@ false
[53]
C. Lenzen and J. Rybicki, “Near-Optimal Self-stabilising Counting and Firing Squads,” Distributed Computing, vol. 32, no. 4, 2019.
Export
BibTeX
@article{Lenzen2019, TITLE = {Near-Optimal Self-stabilising Counting and Firing Squads}, AUTHOR = {Lenzen, Christoph and Rybicki, Joel}, LANGUAGE = {eng}, ISSN = {0178-2770}, DOI = {10.1007/s00446-018-0342-6}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Distributed Computing}, VOLUME = {32}, NUMBER = {4}, PAGES = {339--360}, }
Endnote
%0 Journal Article %A Lenzen, Christoph %A Rybicki, Joel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Near-Optimal Self-stabilising Counting and Firing Squads : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7AD6-2 %R 10.1007/s00446-018-0342-6 %7 2018 %D 2019 %J Distributed Computing %V 32 %N 4 %& 339 %P 339 - 360 %I Springer International %C Berlin %@ false
[54]
C. Lenzen, M. Parter, and E. Yogev, “Parallel Balanced Allocations: The Heavily Loaded Case,” in SPAA’19, 31st ACM Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, USA, 2019.
Export
BibTeX
@inproceedings{Lenzen_SPAA2019, TITLE = {Parallel Balanced Allocations: {T}he Heavily Loaded Case}, AUTHOR = {Lenzen, Christoph and Parter, Merav and Yogev, Eylon}, LANGUAGE = {eng}, ISBN = {978-1-4503-6184-2}, DOI = {10.1145/3323165.3323203}, PUBLISHER = {ACM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {SPAA'19, 31st ACM Symposium on Parallelism in Algorithms and Architectures}, PAGES = {313--322}, ADDRESS = {Phoenix, AZ, USA}, }
Endnote
%0 Conference Proceedings %A Lenzen, Christoph %A Parter, Merav %A Yogev, Eylon %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Parallel Balanced Allocations: The Heavily Loaded Case : %G eng %U http://hdl.handle.net/21.11116/0000-0003-6593-5 %R 10.1145/3323165.3323203 %D 2019 %B 31st ACM Symposium on Parallelism in Algorithms and Architectures %Z date of event: 2019-06-22 - 2019-06-24 %C Phoenix, AZ, USA %B SPAA'19 %P 313 - 322 %I ACM %@ 978-1-4503-6184-2
[55]
C. Lenzen, M. Parter, and E. Yogev, “Parallel Balanced Allocations: The Heavily Loaded Case,” 2019. [Online]. Available: http://arxiv.org/abs/1904.07532. (arXiv: 1904.07532)
Abstract
We study parallel algorithms for the classical balls-into-bins problem, in which $m$ balls acting in parallel as separate agents are placed into $n$ bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+\Theta(\sqrt{m/n\cdot \log n})$ (for $m\geq n \log n$) w.h.p. In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(\log\log m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(\log\log (m/n)+\log^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(\log^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $\Omega(\min\{\log\log (m/n),n\})$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(\log n)$ messages w.h.p.
Export
BibTeX
@online{Lenzen_arXiv1904.07532, TITLE = {Parallel Balanced Allocations: {T}he Heavily Loaded Case}, AUTHOR = {Lenzen, Christoph and Parter, Merav and Yogev, Eylon}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1904.07532}, EPRINT = {1904.07532}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We study parallel algorithms for the classical balls-into-bins problem, in which $m$ balls acting in parallel as separate agents are placed into $n$ bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+\Theta(\sqrt{m/n\cdot \log n})$ (for $m\geq n \log n$) w.h.p. In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(\log\log m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(\log\log (m/n)+\log^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(\log^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $\Omega(\min\{\log\log (m/n),n\})$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(\log n)$ messages w.h.p.}, }
Endnote
%0 Report %A Lenzen, Christoph %A Parter, Merav %A Yogev, Eylon %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Parallel Balanced Allocations: The Heavily Loaded Case : %G eng %U http://hdl.handle.net/21.11116/0000-0003-B3A4-9 %U http://arxiv.org/abs/1904.07532 %D 2019 %X We study parallel algorithms for the classical balls-into-bins problem, in which $m$ balls acting in parallel as separate agents are placed into $n$ bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of $m=n$ balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of $m\gg n$. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load $m/n+\Theta(\sqrt{m/n\cdot \log n})$ (for $m\geq n \log n$) w.h.p. In contrast, for the sequential setting Berenbrink et al (SIAM J. Comput 2006) showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to $m/n+O(\log\log m)$ w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of $m/n+O(1)$ w.h.p. within $O(\log\log (m/n)+\log^* n)$ rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send $O(1)$ messages in expectation per round. The additive term of $O(\log^* n)$ in the complexity is known to be tight for such algorithms (Lenzen and Wattenhofer Distributed Computing 2016). We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for $\Omega(\min\{\log\log (m/n),n\})$ rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of $m/n + O(1)$ in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive $(1+o(1))m/n+O(\log n)$ messages w.h.p. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
[56]
C. Lenzen and J. Rybicki, “Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus,” Journal of the ACM, vol. 66, no. 5, 2019.
Export
BibTeX
@article{Lenzen_JACM2019, TITLE = {Self-Stabilising {B}yzantine Clock Synchronisation is Almost as Easy as Consensus}, AUTHOR = {Lenzen, Christoph and Rybicki, Joel}, LANGUAGE = {eng}, ISSN = {0004-5411}, DOI = {10.1145/3339471}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of the ACM}, VOLUME = {66}, NUMBER = {5}, EID = {32}, }
Endnote
%0 Journal Article %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 : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7CF6-C %R 10.1145/3339471 %7 2019 %D 2019 %J Journal of the ACM %V 66 %N 5 %Z sequence number: 32 %I ACM %C New York, NY %@ false
[57]
A. Miller, B. Patt-Shamir, and W. Rosenbaum, “With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing,” 2019. [Online]. Available: http://arxiv.org/abs/1902.08069. (arXiv: 1902.08069)
Abstract
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate $0\le\rho\le1$ and burstiness $\sigma\ge0$. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that $O(k d^{1/k})$ space suffice, where $d$ is the number of distinct destinations and $k=\lfloor 1/\rho \rfloor$; and we show that $\Omega(\frac 1 k d^{1/k})$ space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most $1 + d' + \sigma$ where $d'$ is the maximum number of destinations on any root-leaf path.
Export
BibTeX
@online{Miller_arXiv1902.08069, TITLE = {With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing}, AUTHOR = {Miller, Avery and Patt-Shamir, Boaz and Rosenbaum, Will}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1902.08069}, EPRINT = {1902.08069}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate $0\le\rho\le1$ and burstiness $\sigma\ge0$. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that $O(k d^{1/k})$ space suffice, where $d$ is the number of distinct destinations and $k=\lfloor 1/\rho \rfloor$; and we show that $\Omega(\frac 1 k d^{1/k})$ space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most $1 + d' + \sigma$ where $d'$ is the maximum number of destinations on any root-leaf path.}, }
Endnote
%0 Report %A Miller, Avery %A Patt-Shamir, Boaz %A Rosenbaum, Will %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing : %G eng %U http://hdl.handle.net/21.11116/0000-0003-0CD3-2 %U http://arxiv.org/abs/1902.08069 %D 2019 %X We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate $0\le\rho\le1$ and burstiness $\sigma\ge0$. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that $O(k d^{1/k})$ space suffice, where $d$ is the number of distinct destinations and $k=\lfloor 1/\rho \rfloor$; and we show that $\Omega(\frac 1 k d^{1/k})$ space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most $1 + d' + \sigma$ where $d'$ is the maximum number of destinations on any root-leaf path. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
[58]
E. Oh and H.-K. Ahn, “A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms,” Algorithmica, vol. 81, no. 7, 2019.
Export
BibTeX
@article{Oh2019, TITLE = {A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms}, AUTHOR = {Oh, Eunjin and Ahn, Hee-Kap}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-019-00558-9}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Algorithmica}, VOLUME = {81}, NUMBER = {7}, PAGES = {2829--2856}, }
Endnote
%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms : %G eng %U http://hdl.handle.net/21.11116/0000-0003-A7DE-7 %R 10.1007/s00453-019-00558-9 %7 2019 %D 2019 %J Algorithmica %V 81 %N 7 %& 2829 %P 2829 - 2856 %I Springer %C New York, NY %@ false
[59]
E. Oh and H.-K. Ahn, “Assigning Weights to Minimize the Covering Radius in the Plane,” Computational Geometry: Theory and Applications, vol. 81, 2019.
Export
BibTeX
@article{Oh2019, TITLE = {Assigning Weights to Minimize the Covering Radius in the Plane}, AUTHOR = {Oh, Eunjin and Ahn, Hee-Kap}, LANGUAGE = {eng}, ISSN = {0925-7721}, DOI = {10.1016/j.comgeo.2018.10.007}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Computational Geometry: Theory and Applications}, VOLUME = {81}, PAGES = {22--32}, }
Endnote
%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Assigning Weights to Minimize the Covering Radius in the Plane : %G eng %U http://hdl.handle.net/21.11116/0000-0003-C34C-C %R 10.1016/j.comgeo.2018.10.007 %7 2019 %D 2019 %J Computational Geometry: Theory and Applications %V 81 %& 22 %P 22 - 32 %I Elsevier %C Amsterdam %@ false
[60]
E. Oh, “Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
Export
BibTeX
@inproceedings{Oh_SODA19d, TITLE = {Optimal Algorithm for Geodesic Nearest-point {V}oronoi Diagrams in Simple Polygons}, AUTHOR = {Oh, Eunjin}, LANGUAGE = {eng}, ISBN = {978-1-61197-548-2}, DOI = {10.1137/1.9781611975482.25}, PUBLISHER = {SIAM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)}, EDITOR = {Chan, Timothy M.}, PAGES = {391--409}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Oh, Eunjin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons : %G eng %U http://hdl.handle.net/21.11116/0000-0002-AA78-8 %R 10.1137/1.9781611975482.25 %D 2019 %B 30th Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2019-01-06 - 2019-01-09 %C San Diego, CA, USA %B Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms %E Chan, Timothy M. %P 391 - 409 %I SIAM %@ 978-1-61197-548-2
[61]
B. Patt-Shamir and W. Rosenbaum, “Space-Optimal Packet Routing on Trees,” in IEEE Conference on Computer Communications (IEEE INFOCOM 2019), Paris, France, 2019.
Export
BibTeX
@inproceedings{Patt-Shamir_INFOCOM2019, TITLE = {Space-Optimal Packet Routing on Trees}, AUTHOR = {Patt-Shamir, Boaz and Rosenbaum, Will}, LANGUAGE = {eng}, ISBN = {978-1-7281-0515-4}, DOI = {10.1109/INFOCOM.2019.8737596}, PUBLISHER = {IEEE}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {IEEE Conference on Computer Communications (IEEE INFOCOM 2019)}, PAGES = {1036--1044}, ADDRESS = {Paris, France}, }
Endnote
%0 Conference Proceedings %A Patt-Shamir, Boaz %A Rosenbaum, Will %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Space-Optimal Packet Routing on Trees : %G eng %U http://hdl.handle.net/21.11116/0000-0004-AAD1-0 %R 10.1109/INFOCOM.2019.8737596 %D 2019 %B IEEE Conference on Computer Communications %Z date of event: 2019-04-29 - 2019-05-02 %C Paris, France %B IEEE Conference on Computer Communications %P 1036 - 1044 %I IEEE %@ 978-1-7281-0515-4
[62]
P. Schroeder, I. Kacem, and G. Schmidt, “Optimal Online Algorithms for the Portfolio Selection Problem, Bi-Directional Trading and -Search with Interrelated Prices,” RAIRO - Operations Research, vol. 53, no. 2, 2019.
Export
BibTeX
@article{Schroeder2019, TITLE = {Optimal Online Algorithms for the Portfolio Selection Problem, Bi-Directional Trading and -Search with Interrelated Prices}, AUTHOR = {Schroeder, Pascal and Kacem, Imed and Schmidt, G{\"u}nter}, LANGUAGE = {eng}, ISSN = {0399-0559}, DOI = {10.1051/ro/2018064}, PUBLISHER = {EDP Sciences}, ADDRESS = {Les Ulis, France}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, JOURNAL = {RAIRO -- Operations Research}, VOLUME = {53}, NUMBER = {2}, PAGES = {559--576}, }
Endnote
%0 Journal Article %A Schroeder, Pascal %A Kacem, Imed %A Schmidt, G&#252;nter %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Optimal Online Algorithms for the Portfolio Selection Problem, Bi-Directional Trading and -Search with Interrelated Prices : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7AEC-A %R 10.1051/ro/2018064 %7 2019 %D 2019 %J RAIRO - Operations Research %V 53 %N 2 %& 559 %P 559 - 576 %I EDP Sciences %C Les Ulis, France %@ false