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, 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$}, JOURNAL = {Discrete Applied Mathematics}, }
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 %I North-Holland %C Amsterdam %@ false
[3]
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
[4]
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
[5]
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
[6]
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ä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
[7]
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ü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
[8]
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ünnemann, Marvin %A Nusser, André %+ 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é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
[9]
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ünnemann, Marvin %A Wę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
[10]
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ü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
[11]
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. (Accepted/in press)
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}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {36th Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, 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ász Cactus Number in Planar Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5D6-A %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
[12]
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
[13]
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
[14]
Y. K. Cheung, M. Hoefer, and P. Nakhe, “Tracing Equilibrium in Dynamic Markets via Distributed Adaptation,” in International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montreal, Canada. (Accepted/in press)
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}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019)}, 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 %D 2019 %B International Conference on Autonomous Agents and Multiagent Systems %Z date of event: 2019-05-13 - 2019-05-17 %C Montreal, Canada %B International Conference on Autonomous Agents and Multiagent Systems
[15]
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
[16]
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
[17]
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
[18]
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. (Accepted/in press)
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}, PUBLISHER = {IEEE}, YEAR = {2019}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {ICDE 2019, 35th IEEE International Conference on Data Engineering}, 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 %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 %I IEEE
[19]
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ä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
[20]
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
[21]
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 = {1--6}, 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 1 - 6 %I IEEE %@ 978-1-5386-3214-7
[22]
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, pp. 391–409.
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