Current Year

[1]
I. Abraham, S. Chechik, and S. Krinninger, “Fully dynamic all-pairs shortest paths with worst-case update-time,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{AbrahamCK17, TITLE = {Fully dynamic all-pairs shortest paths with worst-case update-time}, AUTHOR = {Abraham, Ittai and Chechik, Shiri and Krinninger, Sebastian}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.28}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {440--452}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Abraham, Ittai %A Chechik, Shiri %A Krinninger, Sebastian %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fully dynamic all-pairs shortest paths with worst-case update-time : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-52D0-1 %R 10.1137/1.9781611974782.28 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 440 - 452 %I SIAM %@ 978-1-61197-478-2
[2]
S. Anand, K. Bringmann, T. Friedrich, N. Garg, and A. Kumar, “Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines,” Algorithmica, vol. 77, no. 2, 2017.
Export
BibTeX
@article{DBLP:journals/algorithmica/0002B0G017, TITLE = {Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines}, AUTHOR = {Anand, S. and Bringmann, Karl and Friedrich, Tobias and Garg, Naveen and Kumar, Amit}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-015-0082-y}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Algorithmica}, VOLUME = {77}, NUMBER = {2}, PAGES = {515--536}, }
Endnote
%0 Journal Article %A Anand, S. %A Bringmann, Karl %A Friedrich, Tobias %A Garg, Naveen %A Kumar, Amit %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Discrete Optimization, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5527-9 %R 10.1007/s00453-015-0082-y %7 2015 %D 2017 %J Algorithmica %V 77 %N 2 %& 515 %P 515 - 536 %I Springer-Verlag %C New York, NY %@ false
[3]
Y. Azar, M. Hoefer, I. Maor, R. Reiffenhäuser, and B. Vöcking, “Truthful Mechanism Design via Correlated Tree Rounding,” Mathematical Programming / A, vol. 163, no. 1–2, 2017.
Export
BibTeX
@article{Azar2017, TITLE = {Truthful Mechanism Design via Correlated Tree Rounding}, AUTHOR = {Azar, Yossi and Hoefer, Martin and Maor, Idan and Reiffenh{\"a}user, Rebecca and V{\"o}cking, Berthold}, LANGUAGE = {eng}, ISSN = {0025-5610}, DOI = {10.1007/s10107-016-1068-5}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Mathematical Programming / A}, VOLUME = {163}, NUMBER = {1-2}, PAGES = {445--469}, }
Endnote
%0 Journal Article %A Azar, Yossi %A Hoefer, Martin %A Maor, Idan %A Reiffenhäuser, Rebecca %A Vöcking, Berthold %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Truthful Mechanism Design via Correlated Tree Rounding : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-326B-A %R 10.1007/s10107-016-1068-5 %7 2016-09-10 %D 2017 %J Mathematical Programming / A %V 163 %N 1-2 %& 445 %P 445 - 469 %I Springer %C New York, NY %@ false
[4]
L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan, “Find Your Place: Simple Distributed Algorithms for Community Detection,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{BCNPT17, TITLE = {Find Your Place: {S}imple Distributed Algorithms for Community Detection}, AUTHOR = {Becchetti, Luca and Clementi, Andrea and Natale, Emanuele and Pasquale, Francesco and Trevisan, Luca}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.59}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {940--959}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Becchetti, Luca %A Clementi, Andrea %A Natale, Emanuele %A Pasquale, Francesco %A Trevisan, Luca %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Find Your Place: Simple Distributed Algorithms for Community Detection : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5877-A %R 10.1137/1.9781611974782.59 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 940 - 959 %I SIAM
[5]
R. Becker, M. Sagraloff, V. Sharma, and C. Yap, “A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration,” Journal of Symbolic Computation. (Accepted/in press)
Export
BibTeX
@article{Becker2017JSC, TITLE = {A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the {Pellet} Test and {Newton} Iteration}, AUTHOR = {Becker, Ruben and Sagraloff, Michael and Sharma, Vikram and Yap, Chee}, LANGUAGE = {eng}, ISSN = {0747-7171}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Symbolic Computation}, }
Endnote
%0 Journal Article %A Becker, Ruben %A Sagraloff, Michael %A Sharma, Vikram %A Yap, Chee %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5717-8 %D 2017 %J Journal of Symbolic Computation %I Elsevier %C Amsterdam %@ false
[6]
F. Benhamouda, T. Lepoint, C. Mathieu, and H. Zhou, “Optimization of Bootstrapping in Circuits,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.160, TITLE = {Optimization of Bootstrapping in Circuits}, AUTHOR = {Benhamouda, Fabrice and Lepoint, Tancr{\`e}de and Mathieu, Claire and Zhou, Hang}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.160}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {2423--2433}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Benhamouda, Fabrice %A Lepoint, Tancrède %A Mathieu, Claire %A Zhou, Hang %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Optimization of Bootstrapping in Circuits : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4EBE-A %R 10.1137/1.9781611974782.160 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 2423 - 2433 %I SIAM %@ 978-1-61197-478-2
[7]
O. Beyersdorff, L. Chew, and K. Sreenivasaiah, “A Game Characterisation of Tree-like Q-Resolution Size,” Journal of Computer and System Sciences, vol. In Press, 2017.
Export
BibTeX
@article{Beyersdorff2017, TITLE = {A Game Characterisation of Tree-like {Q-Resolution} Size}, AUTHOR = {Beyersdorff, Olaf and Chew, Leroy and Sreenivasaiah, Karteek}, LANGUAGE = {eng}, ISSN = {0022-0000}, DOI = {10.1016/j.jcss.2016.11.011}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {In Press}, }
Endnote
%0 Journal Article %A Beyersdorff, Olaf %A Chew, Leroy %A Sreenivasaiah, Karteek %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Game Characterisation of Tree-like Q-Resolution Size : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5F80-F %R 10.1016/j.jcss.2016.11.011 %7 2017 %D 2017 %J Journal of Computer and System Sciences %V In Press %I Elsevier %C Amsterdam %@ false
[8]
L. Boczkowski, A. Korman, and E. Natale, “Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{BKN17, TITLE = {Minimizing Message Size in Stochastic Communication Patterns: {F}ast Self-Stabilizing Protocols with 3 bits}, AUTHOR = {Boczkowski, Lucas and Korman, Amos and Natale, Emanuele}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.168}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {2540--2559}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Boczkowski, Lucas %A Korman, Amos %A Natale, Emanuele %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-587B-2 %R 10.1137/1.9781611974782.168 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 2540 - 2559 %I SIAM
[9]
J.-D. Boissonnat, R. Dyer, and A. Ghosh, “Delaunay Triangulation of Manifolds,” Foundations of Computational Mathematics, vol. First Online, 2017.
Export
BibTeX
@article{Boissonnat2017, TITLE = {Delaunay Triangulation of Manifolds}, AUTHOR = {Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit}, LANGUAGE = {eng}, ISSN = {1615-3375}, DOI = {10.1007/s10208-017-9344-1}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Foundations of Computational Mathematics}, VOLUME = {First Online}, PAGES = {1--33}, }
Endnote
%0 Journal Article %A Boissonnat, Jean-Daniel %A Dyer, Ramsay %A Ghosh, Arijit %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Delaunay Triangulation of Manifolds : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-7945-0 %R 10.1007/s10208-017-9344-1 %7 2017-02-01 %D 2017 %8 01.02.2017 %J Foundations of Computational Mathematics %V First Online %& 1 %P 1 - 33 %I Springer %C New York, NY %@ false
[10]
K. Bringmann, “A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{DBLP:conf/soda/Bringmann17, TITLE = {A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum}, AUTHOR = {Bringmann, Karl}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.69}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {1073--1084}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5522-4 %R 10.1137/1.9781611974782.69 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 1073 - 1084 %I SIAM
[11]
K. Bringmann, S. Cabello, and M. Emmerich, “Maximum Volume Subset Selection for Anchored Boxes,” in 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia. (Accepted/in press)
Export
BibTeX
@inproceedings{bringmann:scg, TITLE = {Maximum Volume Subset Selection for Anchored Boxes}, AUTHOR = {Bringmann, Karl and Cabello, Sergio and Emmerich, Michael}, LANGUAGE = {eng}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {33rd International Symposium on Computational Geometry (SoCG 2017)}, ADDRESS = {Brisbane, Australia}, }
Endnote
%0 Conference Proceedings %A Bringmann, Karl %A Cabello, Sergio %A Emmerich, Michael %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Maximum Volume Subset Selection for Anchored Boxes : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-7D6F-9 %D 2017 %8 12.02.2017 %B 33rd International Symposium on Computational Geometry %Z date of event: 2017-07-04 - 2017-07-07 %C Brisbane, Australia %B 33rd International Symposium on Computational Geometry
[12]
J. Bund, C. Lenzen, and M. Medina, “Near-Optimal Metastability-Containing Sorting Networks,” in Design, Automation & Test in Europe Conference & Exhibition (DATE 2017), Lausanne, Switzerland. (Accepted/in press)
Export
BibTeX
@inproceedings{BundDATE2017, TITLE = {Near-Optimal Metastability-Containing Sorting Networks}, AUTHOR = {Bund, Johannes and Lenzen, Christoph and Medina, Moti}, LANGUAGE = {eng}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Design, Automation \& Test in Europe Conference \& Exhibition (DATE 2017)}, ADDRESS = {Lausanne, Switzerland}, }
Endnote
%0 Conference Proceedings %A Bund, Johannes %A Lenzen, Christoph %A Medina, Moti %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Near-Optimal Metastability-Containing Sorting Networks : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-571A-2 %D 2017 %B Design, Automation & Test in Europe Conference & Exhibition %Z date of event: 2017-03-27 - 2017-03-31 %C Lausanne, Switzerland %B Design, Automation & Test in Europe Conference & Exhibition
[13]
P. Bürgisser, C. Ikenmeyer, and J. Hüttenhain, “Permanent versus Determinant: Not via Saturations,” Proceedings of the American Mathematical Society, vol. 145, 2017.
Export
BibTeX
@article{BHI:17, TITLE = {Permanent versus Determinant: {N}ot via Saturations}, AUTHOR = {B{\"u}rgisser, Peter and Ikenmeyer, Christian and H{\"u}ttenhain, Jesko}, LANGUAGE = {eng}, ISSN = {0002-9939}, DOI = {10.1090/proc/13310}, PUBLISHER = {American Mathematical Society}, ADDRESS = {Providence, R.I. [etc.]}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Proceedings of the American Mathematical Society}, VOLUME = {145}, PAGES = {1247--1258}, }
Endnote
%0 Journal Article %A Bürgisser, Peter %A Ikenmeyer, Christian %A Hüttenhain, Jesko %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Permanent versus Determinant: Not via Saturations : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4F48-A %R 10.1090/proc/13310 %7 2017 %D 2017 %J Proceedings of the American Mathematical Society %V 145 %& 1247 %P 1247 - 1258 %I American Mathematical Society %C Providence, R.I. [etc.] %@ false
[14]
P. Bürgisser and C. Ikenmeyer, “Fundamental Invariants of Orbit Closures,” Journal of Algebra, vol. 477, 2017.
Export
BibTeX
@article{BI:17, TITLE = {Fundamental Invariants of Orbit Closures}, AUTHOR = {B{\"u}rgisser, Peter and Ikenmeyer, Christian}, LANGUAGE = {eng}, ISSN = {0021-8693}, DOI = {10.1016/j.jalgebra.2016.12.035}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Algebra}, VOLUME = {477}, PAGES = {390--434}, }
Endnote
%0 Journal Article %A Bürgisser, Peter %A Ikenmeyer, Christian %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fundamental Invariants of Orbit Closures : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4F2E-8 %R 10.1016/j.jalgebra.2016.12.035 %7 2017-01-17 %D 2017 %J Journal of Algebra %V 477 %& 390 %P 390 - 434 %I Elsevier %C Amsterdam %@ false
[15]
P. Chalermsook, S. Das, B. Laekhanukit, and D. Vaz, “Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.47, TITLE = {Beyond Metric Embedding: {A}pproximating {Group Steiner Trees} on Bounded Treewidth Graphs}, AUTHOR = {Chalermsook, Parinya and Das, Syamantak and Laekhanukit, Bundit and Vaz, Daniel}, LANGUAGE = {eng}, DOI = {10.1137/1.9781611974782.47}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, PAGES = {737--751}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Das, Syamantak %A Laekhanukit, Bundit %A Vaz, Daniel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-573D-3 %R 10.1137/1.9781611974782.47 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %P 737 - 751 %I SIAM
[16]
P. Chalermsook and D. Vaz, “New Integrality Gap Results for the Firefighters Problem on Trees,” in Approximation and Online Algorithms (WAOA 2016), Aarhus, Denmark, 2017.
Export
BibTeX
@inproceedings{Chalermsook2017, TITLE = {New Integrality Gap Results for the Firefighters Problem on Trees}, AUTHOR = {Chalermsook, Parinya and Vaz, Daniel}, LANGUAGE = {eng}, ISBN = {978-3-319-51740-7}, DOI = {10.1007/978-3-319-51741-4_6}, PUBLISHER = {Springer}, YEAR = {2016}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Approximation and Online Algorithms (WAOA 2016)}, EDITOR = {Jansen, Klaus and Mastrolilli, Monaldo}, PAGES = {65--77}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {10138}, ADDRESS = {Aarhus, Denmark}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Vaz, Daniel %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T New Integrality Gap Results for the Firefighters Problem on Trees : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-575B-0 %R 10.1007/978-3-319-51741-4_6 %D 2017 %B 14th Workshop on Approximation and Online Algorithms %Z date of event: 2016-08-25 - 2016-08-26 %C Aarhus, Denmark %B Approximation and Online Algorithms %E Jansen, Klaus; Mastrolilli, Monaldo %P 65 - 77 %I Springer %@ 978-3-319-51740-7 %B Lecture Notes in Computer Science %N 10138
[17]
P. Chalermsook and A. Schmid, “Finding Triangles for Maximum Planar Subgraphs,” in 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), Hsinchu, Taiwan. (Accepted/in press)
Export
BibTeX
@inproceedings{PCAS2017, TITLE = {Finding Triangles for Maximum Planar Subgraphs}, AUTHOR = {Chalermsook, Parinya and Schmid, Andreas}, LANGUAGE = {eng}, PUBLISHER = {Springer}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017)}, ADDRESS = {Hsinchu, Taiwan}, }
Endnote
%0 Conference Proceedings %A Chalermsook, Parinya %A Schmid, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Finding Triangles for Maximum Planar Subgraphs : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5DDC-F %D 2016 %B 11th International Conference and Workshops on Algorithms and Computation %Z date of event: 2017-03-29 - 2017-03-31 %C Hsinchu, Taiwan %B 11th International Conference and Workshops on Algorithms and Computation %I Springer
[18]
L. S. Chandran, D. Issac, and A. Karrenbauer, “On the Parameterized Complexity of Biclique Cover and Partition,” in 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, 2017.
Export
BibTeX
@inproceedings{BicliqueFPT, TITLE = {On the Parameterized Complexity of Biclique Cover and Partition}, AUTHOR = {Chandran, L. Sunil and Issac, Davis and Karrenbauer, Andreas}, LANGUAGE = {eng}, ISBN = {978-3-95977-023-1}, URL = {urn:nbn:de:0030-drops-69293}, DOI = {10.4230/LIPIcs.IPEC.2016.11}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2016}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, EDITOR = {Guo, Jiong and Hermelin, Danny}, PAGES = {1--13}, EID = {11}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {63}, ADDRESS = {Aarhus, Denmark}, }
Endnote
%0 Conference Proceedings %A Chandran, L. Sunil %A Issac, Davis %A Karrenbauer, Andreas %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On the Parameterized Complexity of Biclique Cover and Partition : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-53DB-3 %R 10.4230/LIPIcs.IPEC.2016.11 %U urn:nbn:de:0030-drops-69293 %D 2017 %B 11th International Symposium on Parameterized and Exact Computation %Z date of event: 2016-08-24 - 2016-08-26 %C Aarhus, Denmark %B 11th International Symposium on Parameterized and Exact Computation %E Guo, Jiong; Hermelin, Danny %P 1 - 13 %Z sequence number: 11 %I Schloss Dagstuhl %@ 978-3-95977-023-1 %B Leibniz International Proceedings in Informatics %N 63 %U http://drops.dagstuhl.de/doku/urheberrecht1.htmlhttp://drops.dagstuhl.de/opus/volltexte/2017/6929/
[19]
M. Cygan, M. Pilipczuk, M. Pilipczuk, E. J. van Leeuwen, and M. Wrochna, “Polynomial Kernelization for Removing Induced Claws and Diamonds,” Theory of Computing Systems, vol. 60, no. 4, 2017.
Export
BibTeX
@article{CyganAlgorithmica2016, TITLE = {Polynomial Kernelization for Removing Induced Claws and Diamonds}, AUTHOR = {Cygan, Marek and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan and Wrochna, Marcin}, LANGUAGE = {eng}, ISSN = {1432-4350}, DOI = {10.1007/s00224-016-9689-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Theory of Computing Systems}, VOLUME = {60}, NUMBER = {4}, PAGES = {615--636}, }
Endnote
%0 Journal Article %A Cygan, Marek %A Pilipczuk, Marcin %A Pilipczuk, Michał %A van Leeuwen, Erik Jan %A Wrochna, Marcin %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Polynomial Kernelization for Removing Induced Claws and Diamonds : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002B-8606-6 %R 10.1007/s00224-016-9689-x %7 2016-06-23 %D 2017 %J Theory of Computing Systems %V 60 %N 4 %& 615 %P 615 - 636 %I Springer %C New York, NY %@ false
[20]
J. Diaz, O. Pottonen, M. Serna, and E. J. van Leeuwen, “Complexity of Metric Dimension on Planar Graphs,” Journal of Computer and System Sciences, vol. 83, no. 1, 2017.
Export
BibTeX
@article{Diaz2017, TITLE = {Complexity of Metric Dimension on Planar Graphs}, AUTHOR = {Diaz, Josep and Pottonen, Olli and Serna, Maria and van Leeuwen, Erik Jan}, ISSN = {0022-0000}, DOI = {10.1016/j.jcss.2016.06.006}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {83}, NUMBER = {1}, PAGES = {132--158}, }
Endnote
%0 Journal Article %A Diaz, Josep %A Pottonen, Olli %A Serna, Maria %A van Leeuwen, Erik Jan %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Complexity of Metric Dimension on Planar Graphs : %U http://hdl.handle.net/11858/00-001M-0000-002B-A574-5 %R 10.1016/j.jcss.2016.06.006 %7 2016 %D 2017 %J Journal of Computer and System Sciences %V 83 %N 1 %& 132 %P 132 - 158 %I Elsevier %C Amsterdam %@ false
[21]
K. Dutta, A. Ghosh, B. Jartoux, and N. H. Mustafa, “Shallow Packings, Semialgebraic Set Systems, Macbeath Regions and Polynomial Partitioning,” in 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia. (Accepted/in press)
Export
BibTeX
@inproceedings{DuttaGJM-Mnets-17, TITLE = {Shallow Packings, Semialgebraic Set Systems, {Macbeath} Regions and Polynomial Partitioning}, AUTHOR = {Dutta, Kunal and Ghosh, Arijit and Jartoux, Bruno and Mustafa, Nabil H.}, LANGUAGE = {eng}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {33rd International Symposium on Computational Geometry (SoCG 2017)}, ADDRESS = {Brisbane, Australia}, }
Endnote
%0 Conference Proceedings %A Dutta, Kunal %A Ghosh, Arijit %A Jartoux, Bruno %A Mustafa, Nabil H. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Shallow Packings, Semialgebraic Set Systems, Macbeath Regions and Polynomial Partitioning : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-7941-7 %D 2017 %8 12.02.2017 %B 33rd International Symposium on Computational Geometry %Z date of event: 2017-07-04 - 2017-07-07 %C Brisbane, Australia %B 33rd International Symposium on Computational Geometry
[22]
P. Dütting and T. Kesselheim, “Best-Response Dynamics in Combinatorial Auctions with Item Bidding,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.33, TITLE = {Best-Response Dynamics in Combinatorial Auctions with Item Bidding}, AUTHOR = {D{\"u}tting, Paul and Kesselheim, Thomas}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.33}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {521--533}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Dütting, Paul %A Kesselheim, Thomas %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Best-Response Dynamics in Combinatorial Auctions with Item Bidding : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4E5E-2 %R 10.1137/1.9781611974782.33 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 521 - 533 %I SIAM %@ 978-1-61197-478-2
[23]
M. Ernestus, S. Friedrichs, M. Hemmer, J. Kokemüller, A. Kröller, M. Moeini, and C. Schmidt, “Algorithms for Art Gallery Illumination,” Journal of Global Optimization, vol. 68, no. 1, 2017.
Export
BibTeX
@article{ErnestusJGO2016, TITLE = {Algorithms for Art Gallery Illumination}, AUTHOR = {Ernestus, Maximilian and Friedrichs, Stephan and Hemmer, Michael and Kokem{\"u}ller, Jan and Kr{\"o}ller, Alexander and Moeini, Mahdi and Schmidt, Christiane}, LANGUAGE = {eng}, ISSN = {0925-5001}, DOI = {10.1007/s10898-016-0452-2}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Journal of Global Optimization}, VOLUME = {68}, NUMBER = {1}, PAGES = {23--45}, }
Endnote
%0 Journal Article %A Ernestus, Maximilian %A Friedrichs, Stephan %A Hemmer, Michael %A Kokemüller, Jan %A Kröller, Alexander %A Moeini, Mahdi %A Schmidt, Christiane %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations %T Algorithms for Art Gallery Illumination : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-0B3C-1 %R 10.1007/s10898-016-0452-2 %7 2016 %D 2017 %J Journal of Global Optimization %V 68 %N 1 %& 23 %P 23 - 45 %I Springer %C New York, NY %@ false
[24]
M. Függer, C. Lenzen, and T. Polzer, “Metastability-Aware Memory-Efficient Time-to-Digital Converters,” in 23rd IEEE International Symposium on Asynchronous Circuits and Systems, San Diego, CA, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{fueggerASYNC2017, TITLE = {Metastability-Aware Memory-Efficient Time-to-Digital Converters}, AUTHOR = {F{\"u}gger, Matthias and Lenzen, Christoph and Polzer, Thomas}, LANGUAGE = {eng}, PUBLISHER = {IEEE}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {23rd IEEE International Symposium on Asynchronous Circuits and Systems}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Függer, Matthias %A Lenzen, Christoph %A Polzer, Thomas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Metastability-Aware Memory-Efficient Time-to-Digital Converters : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-80CD-D %D 2017 %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %Z date of event: 2017-05-21 - 2017-05-24 %C San Diego, CA, USA %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %I IEEE
[25]
M. Goswami, X. Gu, V. P. Pingali, and G. Telang, “Computing Teichmüller Maps Between Polygons,” Foundations of Computational Mathematics, vol. 17, no. 2, 2017.
Export
BibTeX
@article{Goswami2017, TITLE = {Computing {Teichmüller} Maps Between Polygons}, AUTHOR = {Goswami, Mayank and Gu, Xianfeng and Pingali, Vamsi P. and Telang, Gaurish}, LANGUAGE = {eng}, ISSN = {1615-3375}, DOI = {10.1007/s10208-015-9294-4}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Foundations of Computational Mathematics}, VOLUME = {17}, NUMBER = {2}, PAGES = {497--526}, }
Endnote
%0 Journal Article %A Goswami, Mayank %A Gu, Xianfeng %A Pingali, Vamsi P. %A Telang, Gaurish %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Computing Teichmüller Maps Between Polygons : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-3E48-3 %R 10.1007/s10208-015-9294-4 %7 2015-11-25 %D 2017 %J Foundations of Computational Mathematics %V 17 %N 2 %& 497 %P 497 - 526 %I Springer %C New York, NY %@ false
[26]
F. Grandoni, T. Mömke, A. Wiese, and H. Zhou, “To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{doi:10.1137/1.9781611974782.159, TITLE = {To Augment or Not to Augment: {S}olving Unsplittable Flow on a Path by Creating Slack}, AUTHOR = {Grandoni, Fabrizio and M{\"o}mke, Tobias and Wiese, Andreas and Zhou, Hang}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.159}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {2411--2422}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Grandoni, Fabrizio %A Mömke, Tobias %A Wiese, Andreas %A Zhou, Hang %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4EB5-B %R 10.1137/1.9781611974782.159 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 2411 - 2422 %I SIAM %@ 978-1-61197-478-2
[27]
S. Heydrich and A. Wiese, “Faster Approximation Schemes for the Two-dimensional Knapsack Problem,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
Export
BibTeX
@inproceedings{HeydrichW17, TITLE = {Faster Approximation Schemes for the Two-dimensional Knapsack Problem}, AUTHOR = {Heydrich, Sandy and Wiese, Andreas}, LANGUAGE = {eng}, ISBN = {978-1-61197-478-2}, DOI = {10.1137/1.9781611974782.6}, PUBLISHER = {SIAM}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, BOOKTITLE = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)}, EDITOR = {Klein, Philip N.}, PAGES = {79--98}, ADDRESS = {Barcelona, Spain}, }
Endnote
%0 Conference Proceedings %A Heydrich, Sandy %A Wiese, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Faster Approximation Schemes for the Two-dimensional Knapsack Problem : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-54AD-3 %R 10.1137/1.9781611974782.6 %D 2017 %B Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2017-01-16 - 2017-01-19 %C Barcelona, Spain %B Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms %E Klein, Philip N. %P 79 - 98 %I SIAM %@ 978-1-61197-478-2
[28]
M. Hoefer and L. Wagner, “Locally Stable Marriage with Strict Preferences,” SIAM Journal on Discrete Mathematics, vol. 31, no. 1, 2017.
Export
BibTeX
@article{HoeferWagner2017, TITLE = {Locally Stable Marriage with Strict Preferences}, AUTHOR = {Hoefer, Martin and Wagner, Lisa}, LANGUAGE = {eng}, ISSN = {0895-4801}, DOI = {10.1137/151003854}, PUBLISHER = {SIAM}, ADDRESS = {Philadelphia, Pa.}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {31}, NUMBER = {1}, PAGES = {283--316}, }
Endnote
%0 Journal Article %A Hoefer, Martin %A Wagner, Lisa %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Locally Stable Marriage with Strict Preferences : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-26B4-1 %R 10.1137/151003854 %7 2017-02-23 %D 2017 %J SIAM Journal on Discrete Mathematics %V 31 %N 1 %& 283 %P 283 - 316 %I SIAM %C Philadelphia, Pa. %@ false
[29]
M. Hoefer and B. Kodric, “Combinatorial Secretary Problems with Ordinal Information,” 2017. [Online]. Available: http://arxiv.org/abs/1702.01290. (arXiv: 1702.01290)
Abstract
The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model.
Export
BibTeX
@online{Hoefer_Kodric2017, TITLE = {Combinatorial Secretary Problems with Ordinal Information}, AUTHOR = {Hoefer, Martin and Kodric, Bojana}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1702.01290}, EPRINT = {1702.01290}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model.}, }
Endnote
%0 Report %A Hoefer, Martin %A Kodric, Bojana %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Secretary Problems with Ordinal Information : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-5C63-3 %U http://arxiv.org/abs/1702.01290 %D 2017 %X The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model. %K Computer Science, Data Structures and Algorithms, cs.DS
[30]
C. Ikenmeyer and J. M. Landsberg, “On the Complexity of the Permanent in Various Computational Models,” Journal of Pure and Applied Algebra, vol. Accepted Manuscript, 2017.
Export
BibTeX
@article{IL:17, TITLE = {On the Complexity of the Permanent in Various Computational Models}, AUTHOR = {Ikenmeyer, Christian and Landsberg, J. M.}, LANGUAGE = {eng}, ISSN = {0022-4049}, DOI = {10.1016/j.jpaa.2017.02.008}, PUBLISHER = {North-Holland}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Pure and Applied Algebra}, VOLUME = {Accepted Manuscript}, }
Endnote
%0 Journal Article %A Ikenmeyer, Christian %A Landsberg, J. M. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T On the Complexity of the Permanent in Various Computational Models : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-4F23-D %R 10.1016/j.jpaa.2017.02.008 %7 2017-02-23 %D 2017 %8 23.02.2017 %J Journal of Pure and Applied Algebra %O J. Pure Appl. Algebra %V Accepted Manuscript %I North-Holland %C Amsterdam %@ false
[31]
G. Jindal, P. Kolev, R. Peng, and S. Sawlani, “Density Independent Algorithms for Sparsifying k-Step Random Walks,” 2017. [Online]. Available: http://arxiv.org/abs/1702.06110. (arXiv: 1702.06110)
Abstract
We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.
Export
BibTeX
@online{DBLP:journals/corr/JindalKPS17, TITLE = {Density Independent Algorithms for Sparsifying $k$-Step Random Walks}, AUTHOR = {Jindal, Gorav and Kolev, Pavel and Peng, Richard and Sawlani, Saurabh}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1702.06110}, EPRINT = {1702.06110}, EPRINTTYPE = {arXiv}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.}, }
Endnote
%0 Report %A Jindal, Gorav %A Kolev, Pavel %A Peng, Richard %A Sawlani, Saurabh %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Density Independent Algorithms for Sparsifying k-Step Random Walks : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002D-26A6-1 %U http://arxiv.org/abs/1702.06110 %D 2017 %X We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices. %K Computer Science, Data Structures and Algorithms, cs.DS
[32]
R. Levi, G. Moshkovitz, D. Ron, R. Rubinfeld, and A. Shapira, “Constructing Near Spanning Trees with Few Local Inspections,” Random Structures and Algorithms, vol. 50, 2017.
Export
BibTeX
@article{LeviMRRS15, TITLE = {Constructing Near Spanning Trees with Few Local Inspections}, AUTHOR = {Levi, Reut and Moshkovitz, Guy and Ron, Dana and Rubinfeld, Ronitt and Shapira, Asaf}, LANGUAGE = {eng}, ISSN = {1042-9832}, DOI = {10.1002/rsa.20652}, PUBLISHER = {Wiley}, ADDRESS = {New York, N.Y.}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Random Structures and Algorithms}, VOLUME = {50}, PAGES = {183--200}, }
Endnote
%0 Journal Article %A Levi, Reut %A Moshkovitz, Guy %A Ron, Dana %A Rubinfeld, Ronitt %A Shapira, Asaf %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Constructing Near Spanning Trees with Few Local Inspections : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-601B-C %R 10.1002/rsa.20652 %7 2016 %D 2017 %J Random Structures and Algorithms %V 50 %& 183 %P 183 - 200 %I Wiley %C New York, N.Y. %@ false
[33]
K. Mehlhorn, A. Neumann, and J. M. Schmidt, “Certifying 3-Edge-Connectivity,” Algorithmica, vol. 77, no. 2, 2017.
Export
BibTeX
@article{Mehlhorn_Neumann_Schmidt2017, TITLE = {Certifying 3-Edge-Connectivity}, AUTHOR = {Mehlhorn, Kurt and Neumann, Adrian and Schmidt, Jens M.}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-015-0075-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NX}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Algorithmica}, VOLUME = {77}, NUMBER = {2}, PAGES = {309--335}, }
Endnote
%0 Journal Article %A Mehlhorn, Kurt %A Neumann, Adrian %A Schmidt, Jens M. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Certifying 3-Edge-Connectivity : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-6971-B %R 10.1007/s00453-015-0075-x %7 2015-09-22 %D 2017 %J Algorithmica %V 77 %N 2 %& 309 %P 309 - 335 %I Springer %C New York, NX %@ false
[34]
R. B. Tan, E. J. van Leeuwen, and J. van Leeuwen, “Shortcutting Directed and Undirected Networks with a Degree Constraint,” Discrete Applied Mathematics, vol. 220, 2017.
Export
BibTeX
@article{TanDAM2017, TITLE = {Shortcutting Directed and Undirected Networks with a Degree Constraint}, AUTHOR = {Tan, Richard B. and van Leeuwen, Erik Jan and van Leeuwen, Jan}, LANGUAGE = {eng}, ISSN = {0166-218X}, DOI = {10.1016/j.dam.2016.12.016}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2017}, MARGINALMARK = {$\bullet$}, DATE = {2017}, JOURNAL = {Discrete Applied Mathematics}, VOLUME = {220}, PAGES = {91--117}, }
Endnote
%0 Journal Article %A Tan, Richard B. %A van Leeuwen, Erik Jan %A van Leeuwen, Jan %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Shortcutting Directed and Undirected Networks with a Degree Constraint : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-539D-F %R 10.1016/j.dam.2016.12.016 %7 2017 %D 2017 %J Discrete Applied Mathematics %V 220 %& 91 %P 91 - 117 %I Elsevier %C Amsterdam %@ false
[35]
G. Tarawneh, M. Függer, and C. Lenzen, “Metastability Tolerant Computing,” in 23rd IEEE International Symposium on Asynchronous Circuits and Systems, San Diego, CA, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{TarawnehASYNC2017, TITLE = {Metastability Tolerant Computing}, AUTHOR = {Tarawneh, Ghaith and F{\"u}gger, Matthias and Lenzen, Christoph}, LANGUAGE = {eng}, PUBLISHER = {IEEE}, YEAR = {2017}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {23rd IEEE International Symposium on Asynchronous Circuits and Systems}, ADDRESS = {San Diego, CA, USA}, }
Endnote
%0 Conference Proceedings %A Tarawneh, Ghaith %A Függer, Matthias %A Lenzen, Christoph %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Metastability Tolerant Computing : %G eng %U http://hdl.handle.net/11858/00-001M-0000-002C-80CB-2 %D 2017 %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %Z date of event: 2017-05-21 - 2017-05-24 %C San Diego, CA, USA %B 23rd IEEE International Symposium on Asynchronous Circuits and Systems %I IEEE