Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/conf/soda/soda2012.bht:"
download as .bib file
@inproceedings{DBLP:conf/soda/AdamaszekCER12,
author = {Anna Adamaszek and
Artur Czumaj and
Matthias Englert and
Harald R{\"{a}}cke},
editor = {Yuval Rabani},
title = {An \emph{O}(log \emph{k})-competitive algorithm for generalized caching},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1681--1689},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.133},
doi = {10.1137/1.9781611973099.133},
timestamp = {Tue, 02 Feb 2021 17:07:31 +0100},
biburl = {https://dblp.org/rec/conf/soda/AdamaszekCER12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Addario-BerryL12,
author = {Louigi Addario{-}Berry and
Tao Lei},
editor = {Yuval Rabani},
title = {The mixing time of the Newman: Watts small world},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1661--1668},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.131},
doi = {10.1137/1.9781611973099.131},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Addario-BerryL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AhnGM12,
author = {Kook Jin Ahn and
Sudipto Guha and
Andrew McGregor},
editor = {Yuval Rabani},
title = {Analyzing graph structure via linear measurements},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {459--467},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.40},
doi = {10.1137/1.9781611973099.40},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/AhnGM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AlbersA12,
author = {Susanne Albers and
Antonios Antoniadis},
editor = {Yuval Rabani},
title = {Race to idle: new algorithms for speed scaling with a sleep state},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1266--1285},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.100},
doi = {10.1137/1.9781611973099.100},
timestamp = {Wed, 10 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/AlbersA12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AlonRVX12,
author = {Noga Alon and
Ronitt Rubinfeld and
Shai Vardi and
Ning Xie},
editor = {Yuval Rabani},
title = {Space-efficient local computation algorithms},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1132--1139},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.89},
doi = {10.1137/1.9781611973099.89},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/AlonRVX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AnandGK12,
author = {S. Anand and
Naveen Garg and
Amit Kumar},
editor = {Yuval Rabani},
title = {Resource augmentation for weighted flow-time explained by dual fitting},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1228--1241},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.97},
doi = {10.1137/1.9781611973099.97},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/AnandGK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AndoniN12,
author = {Alexandr Andoni and
Huy L. Nguyen},
editor = {Yuval Rabani},
title = {Width of points in the streaming model},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {447--452},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.38},
doi = {10.1137/1.9781611973099.38},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/AndoniN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AryaFM12,
author = {Sunil Arya and
Guilherme Dias da Fonseca and
David M. Mount},
editor = {Yuval Rabani},
title = {Polytope approximation and the Mahler volume},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {29--42},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.3},
doi = {10.1137/1.9781611973099.3},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/AryaFM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AugustinePRU12,
author = {John Augustine and
Gopal Pandurangan and
Peter Robinson and
Eli Upfal},
editor = {Yuval Rabani},
title = {Towards robust and efficient computation in dynamic peer-to-peer networks},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {551--569},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.47},
doi = {10.1137/1.9781611973099.47},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/AugustinePRU12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AulettaFPP12,
author = {Vincenzo Auletta and
Diodato Ferraioli and
Francesco Pasquale and
Giuseppe Persiano},
editor = {Yuval Rabani},
title = {Metastability of logit dynamics for coordination games},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1006--1024},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.80},
doi = {10.1137/1.9781611973099.80},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/AulettaFPP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AvinCHKLPP12,
author = {Chen Avin and
Asaf Cohen and
Yoram Haddad and
Erez Kantor and
Zvi Lotker and
Merav Parter and
David Peleg},
editor = {Yuval Rabani},
title = {{SINR} diagram with interference cancellation},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {502--515},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.43},
doi = {10.1137/1.9781611973099.43},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/AvinCHKLPP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BadanidiyuruDFKNR12,
author = {Ashwinkumar Badanidiyuru and
Shahar Dobzinski and
Hu Fu and
Robert Kleinberg and
Noam Nisan and
Tim Roughgarden},
editor = {Yuval Rabani},
title = {Sketching valuation functions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1025--1035},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.81},
doi = {10.1137/1.9781611973099.81},
timestamp = {Mon, 30 Oct 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BadanidiyuruDFKNR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BarmanC12,
author = {Siddharth Barman and
Shuchi Chawla},
editor = {Yuval Rabani},
title = {Traffic-redundancy aware network design},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1487--1498},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.118},
doi = {10.1137/1.9781611973099.118},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BarmanC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BaswanaLM12,
author = {Surender Baswana and
Utkarsh Lath and
Anuradha S. Mehta},
editor = {Yuval Rabani},
title = {Single source distance oracle for planar digraphs avoiding a failed
node or link},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {223--232},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.20},
doi = {10.1137/1.9781611973099.20},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BaswanaLM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BateniHKM12,
author = {MohammadHossein Bateni and
MohammadTaghi Hajiaghayi and
Philip N. Klein and
Claire Mathieu},
editor = {Yuval Rabani},
title = {A polynomial-time approximation scheme for planar multiway cut},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {639--655},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.54},
doi = {10.1137/1.9781611973099.54},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BateniHKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BendichWM12,
author = {Paul Bendich and
Bei Wang and
Sayan Mukherjee},
editor = {Yuval Rabani},
title = {Local homology transfer and stratification learning},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1355--1370},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.107},
doi = {10.1137/1.9781611973099.107},
timestamp = {Fri, 19 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BendichWM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Bernstein12,
author = {Aaron Bernstein},
editor = {Yuval Rabani},
title = {Near linear time {(1} + {\(\epsilon\)})-approximation for restricted
shortest paths in undirected graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {189--201},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.17},
doi = {10.1137/1.9781611973099.17},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Bernstein12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BhaskaraCVGZ12,
author = {Aditya Bhaskara and
Moses Charikar and
Aravindan Vijayaraghavan and
Venkatesan Guruswami and
Yuan Zhou},
editor = {Yuval Rabani},
title = {Polynomial integrality gaps for strong {SDP} relaxations of Densest
\emph{k}-subgraph},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {388--405},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.34},
doi = {10.1137/1.9781611973099.34},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BhaskaraCVGZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BhattacharyyaGRS12,
author = {Arnab Bhattacharyya and
Elena Grigorescu and
Prasad Raghavendra and
Asaf Shapira},
editor = {Yuval Rabani},
title = {Testing odd-cycle-freeness in Boolean functions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1140--1149},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.90},
doi = {10.1137/1.9781611973099.90},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BhattacharyyaGRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Bjorklund12,
author = {Andreas Bj{\"{o}}rklund},
editor = {Yuval Rabani},
title = {Counting perfect matchings as fast as Ryser},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {914--921},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.73},
doi = {10.1137/1.9781611973099.73},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Bjorklund12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BjorklundHT12,
author = {Andreas Bj{\"{o}}rklund and
Thore Husfeldt and
Nina Taslaman},
editor = {Yuval Rabani},
title = {Shortest cycle through specified elements},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1747--1753},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.139},
doi = {10.1137/1.9781611973099.139},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BjorklundHT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BjorklundKHNKP12,
author = {Andreas Bj{\"{o}}rklund and
Mikko Koivisto and
Thore Husfeldt and
Jesper Nederlof and
Petteri Kaski and
Pekka Parviainen},
editor = {Yuval Rabani},
title = {Fast zeta transforms for lattices with few irreducibles},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1436--1444},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.113},
doi = {10.1137/1.9781611973099.113},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BjorklundKHNKP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BonifaciMV12,
author = {Vincenzo Bonifaci and
Kurt Mehlhorn and
Girish Varma},
editor = {Yuval Rabani},
title = {Physarum can compute shortest paths},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {233--240},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.21},
doi = {10.1137/1.9781611973099.21},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BonifaciMV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BoseFRV12,
author = {Prosenjit Bose and
Rolf Fagerberg and
Andr{\'{e}} van Renssen and
Sander Verdonschot},
editor = {Yuval Rabani},
title = {Competitive routing in the half-{\texttheta}\({}_{\mbox{6}}\)-graph},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1319--1328},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.104},
doi = {10.1137/1.9781611973099.104},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BoseFRV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BrodalTST12,
author = {Gerth St{\o}lting Brodal and
Konstantinos Tsakalidis and
Spyros Sioutas and
Kostas Tsichlas},
editor = {Yuval Rabani},
title = {Fully persistent B-trees},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {602--614},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.51},
doi = {10.1137/1.9781611973099.51},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BrodalTST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BroutinNS12,
author = {Nicolas Broutin and
Ralph Neininger and
Henning Sulzbach},
editor = {Yuval Rabani},
title = {Partial match queries in random quadtrees},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1056--1065},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.83},
doi = {10.1137/1.9781611973099.83},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/BroutinNS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CadekKMSVW12,
author = {Martin Cadek and
Marek Krc{\'{a}}l and
Jir{\'{\i}} Matousek and
Francis Sergeraert and
Luk{\'{a}}s Vokr{\'{\i}}nek and
Uli Wagner},
editor = {Yuval Rabani},
title = {Computing all maps into a sphere},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1--10},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.1},
doi = {10.1137/1.9781611973099.1},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CadekKMSVW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChakrabortyL12,
author = {Sourav Chakraborty and
Oded Lachish},
editor = {Yuval Rabani},
title = {Improved competitive ratio for the matroid secretary problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1702--1712},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.135},
doi = {10.1137/1.9781611973099.135},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChakrabortyL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChanGKS12,
author = {Timothy M. Chan and
Elyot Grant and
Jochen K{\"{o}}nemann and
Malcolm Sharpe},
editor = {Yuval Rabani},
title = {Weighted capacitated, priority, and geometric set cover via improved
quasi-uniform sampling},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1576--1585},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.125},
doi = {10.1137/1.9781611973099.125},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChanGKS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChangL12,
author = {Hsien{-}Chih Chang and
Hsueh{-}I Lu},
editor = {Yuval Rabani},
title = {A faster algorithm to recognize even-hole-free graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1286--1297},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.101},
doi = {10.1137/1.9781611973099.101},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChangL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChatterjeeH12,
author = {Krishnendu Chatterjee and
Monika Henzinger},
editor = {Yuval Rabani},
title = {An \emph{O}(\emph{n}\({}^{\mbox{2}}\)) time algorithm for alternating
B{\"{u}}chi games},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1386--1399},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.109},
doi = {10.1137/1.9781611973099.109},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChatterjeeH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChattopadhyayEEP12,
author = {Arkadev Chattopadhyay and
Jeff Edmonds and
Faith Ellen and
Toniann Pitassi},
editor = {Yuval Rabani},
title = {A little advice can be very helpful},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {615--625},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.52},
doi = {10.1137/1.9781611973099.52},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChattopadhyayEEP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChawlaHS12,
author = {Shuchi Chawla and
Jason D. Hartline and
Balasubramanian Sivan},
editor = {Yuval Rabani},
title = {Optimal crowdsourcing contests},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {856--868},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.69},
doi = {10.1137/1.9781611973099.69},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChawlaHS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenD12,
author = {Ho{-}Lin Chen and
David Doty},
editor = {Yuval Rabani},
title = {Parallelism and time in hierarchical self-assembly},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1163--1182},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.92},
doi = {10.1137/1.9781611973099.92},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenD12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChengGW12,
author = {Qi Cheng and
Shuhong Gao and
Daqing Wan},
editor = {Yuval Rabani},
title = {Constructing high order elements through subspace polynomials},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1457--1463},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.115},
doi = {10.1137/1.9781611973099.115},
timestamp = {Tue, 18 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChengGW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CheraghchiKKL12,
author = {Mahdi Cheraghchi and
Adam R. Klivans and
Pravesh Kothari and
Homin K. Lee},
editor = {Yuval Rabani},
title = {Submodular functions are noise stable},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1586--1592},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.126},
doi = {10.1137/1.9781611973099.126},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/CheraghchiKKL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CheriyanLNV12,
author = {Joseph Cheriyan and
Bundit Laekhanukit and
Guyslain Naves and
Adrian Vetta},
editor = {Yuval Rabani},
title = {Approximating rooted Steiner networks},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1499--1511},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.119},
doi = {10.1137/1.9781611973099.119},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/CheriyanLNV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChierichettiK12,
author = {Flavio Chierichetti and
Jon M. Kleinberg},
editor = {Yuval Rabani},
title = {Voting with limited information and many alternatives},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1036--1055},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.82},
doi = {10.1137/1.9781611973099.82},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChierichettiK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChierichettiK12a,
author = {Flavio Chierichetti and
Ravi Kumar},
editor = {Yuval Rabani},
title = {LSH-preserving functions and their applications},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1078--1094},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.85},
doi = {10.1137/1.9781611973099.85},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChierichettiK12a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChitnisHM12,
author = {Rajesh Hemant Chitnis and
MohammadTaghi Hajiaghayi and
D{\'{a}}niel Marx},
editor = {Yuval Rabani},
title = {Fixed-parameter tractability of directed multiway cut parameterized
by the size of the cutset},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1713--1725},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.136},
doi = {10.1137/1.9781611973099.136},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChitnisHM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChlamtacH12,
author = {Eden Chlamtac and
Ishay Haviv},
editor = {Yuval Rabani},
title = {Linear index coding via semidefinite programming},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {406--419},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.35},
doi = {10.1137/1.9781611973099.35},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChlamtacH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChoureV12,
author = {Ayush Choure and
Sundar Vishwanathan},
editor = {Yuval Rabani},
title = {Random walks, electric networks and the transience class problem of
sandpiles},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1593--1611},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.127},
doi = {10.1137/1.9781611973099.127},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChoureV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChuzhoyMVZ12,
author = {Julia Chuzhoy and
Yury Makarychev and
Aravindan Vijayaraghavan and
Yuan Zhou},
editor = {Yuval Rabani},
title = {Approximation algorithms and hardness of the \emph{k}-route cut problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {780--799},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.63},
doi = {10.1137/1.9781611973099.63},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChuzhoyMVZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CibulkaK12,
author = {Josef Cibulka and
Jan Kyncl},
editor = {Yuval Rabani},
title = {Tight bounds on the maximum size of a set of permutations with bounded
VC-dimension},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1113--1122},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.87},
doi = {10.1137/1.9781611973099.87},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/CibulkaK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Coja-OghlanZ12,
author = {Amin Coja{-}Oghlan and
Lenka Zdeborov{\'{a}}},
editor = {Yuval Rabani},
title = {The condensation transition in random hypergraph 2-coloring},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {241--250},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.22},
doi = {10.1137/1.9781611973099.22},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Coja-OghlanZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ColletteIL12,
author = {S{\'{e}}bastien Collette and
John Iacono and
Stefan Langerman},
editor = {Yuval Rabani},
title = {Confluent persistence revisited},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {593--601},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.50},
doi = {10.1137/1.9781611973099.50},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ColletteIL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DadushV12,
author = {Daniel Dadush and
Santosh S. Vempala},
editor = {Yuval Rabani},
title = {Deterministic construction of an approximate M-ellipsoid and its applications
to derandomizing lattice algorithms},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1445--1456},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.114},
doi = {10.1137/1.9781611973099.114},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DadushV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaskalakisDS12,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio},
editor = {Yuval Rabani},
title = {Learning \emph{k}-modal distributions via testing},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1371--1385},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.108},
doi = {10.1137/1.9781611973099.108},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DaskalakisDS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaudeMRR12,
author = {Herv{\'{e}} Daud{\'{e}} and
Conrado Mart{\'{\i}}nez and
Vonjy Rasendrahasina and
Vlady Ravelomanana},
editor = {Yuval Rabani},
title = {The {MAX-CUT} of sparse random graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {265--271},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.24},
doi = {10.1137/1.9781611973099.24},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DaudeMRR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DellM12,
author = {Holger Dell and
D{\'{a}}niel Marx},
editor = {Yuval Rabani},
title = {Kernelization of packing problems},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {68--81},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.6},
doi = {10.1137/1.9781611973099.6},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DellM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DiazGMRSS12,
author = {Josep D{\'{\i}}az and
Leslie Ann Goldberg and
George B. Mertzios and
David Richerby and
Maria J. Serna and
Paul G. Spirakis},
editor = {Yuval Rabani},
title = {Approximating fixation probabilities in the generalized Moran process},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {954--960},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.76},
doi = {10.1137/1.9781611973099.76},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/DiazGMRSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DieudonnePP12,
author = {Yoann Dieudonn{\'{e}} and
Andrzej Pelc and
David Peleg},
editor = {Yuval Rabani},
title = {Gathering despite mischief},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {527--540},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.45},
doi = {10.1137/1.9781611973099.45},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DieudonnePP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DriemelH12,
author = {Anne Driemel and
Sariel Har{-}Peled},
editor = {Yuval Rabani},
title = {Jaywalking your dog: computing the Fr{\'{e}}chet distance with
shortcuts},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {318--337},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.30},
doi = {10.1137/1.9781611973099.30},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/DriemelH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DrmotaGNPS12,
author = {Michael Drmota and
Omer Gim{\'{e}}nez and
Marc Noy and
Konstantinos Panagiotou and
Angelika Steger},
editor = {Yuval Rabani},
title = {The maximum degree of random planar graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {281--287},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.26},
doi = {10.1137/1.9781611973099.26},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DrmotaGNPS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DuanS12,
author = {Ran Duan and
Hsin{-}Hao Su},
editor = {Yuval Rabani},
title = {A scaling algorithm for maximum weight matching in bipartite graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1413--1424},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.111},
doi = {10.1137/1.9781611973099.111},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DuanS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DumitrescuT12,
author = {Adrian Dumitrescu and
Csaba D. T{\'{o}}th},
editor = {Yuval Rabani},
title = {Packing anchored rectangles},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {294--305},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.28},
doi = {10.1137/1.9781611973099.28},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/DumitrescuT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Efthymiou12,
author = {Charilaos Efthymiou},
editor = {Yuval Rabani},
title = {A simple algorithm for random colouring \emph{G}(\emph{n, d/n}) using
{(2} + {\(\epsilon\)})\emph{d} colours},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {272--280},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.25},
doi = {10.1137/1.9781611973099.25},
timestamp = {Tue, 05 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Efthymiou12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/EisenstatKM12,
author = {David Eisenstat and
Philip N. Klein and
Claire Mathieu},
editor = {Yuval Rabani},
title = {An efficient polynomial-time approximation scheme for Steiner forest
in planar graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {626--638},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.53},
doi = {10.1137/1.9781611973099.53},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/EisenstatKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/EricksonFN12,
author = {Jeff Erickson and
Kyle Fox and
Amir Nayyeri},
editor = {Yuval Rabani},
title = {Global minimum cuts in surface embedded graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1309--1318},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.103},
doi = {10.1137/1.9781611973099.103},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/EricksonFN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FaenzaOS12,
author = {Yuri Faenza and
Gianpaolo Oriolo and
Gautier Stauffer},
editor = {Yuval Rabani},
title = {Separating stable sets in claw-free graphs via Padberg-Rao and compact
linear programs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1298--1308},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.102},
doi = {10.1137/1.9781611973099.102},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FaenzaOS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FeldmanS12,
author = {Dan Feldman and
Leonard J. Schulman},
editor = {Yuval Rabani},
title = {Data reduction for weighted and outlier-resistant clustering},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1343--1354},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.106},
doi = {10.1137/1.9781611973099.106},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FeldmanS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FiatKLMO12,
author = {Amos Fiat and
Elias Koutsoupias and
Katrina Ligett and
Yishay Mansour and
Svetlana Olonetsky},
editor = {Yuval Rabani},
title = {Beyond myopic best response (in Cournot competition)},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {993--1005},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.79},
doi = {10.1137/1.9781611973099.79},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/FiatKLMO12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FleinerK12,
author = {Tam{\'{a}}s Fleiner and
Naoyuki Kamiyama},
editor = {Yuval Rabani},
title = {A matroid approach to stable matchings with lower quotas},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {135--142},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.12},
doi = {10.1137/1.9781611973099.12},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FleinerK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FominLS12,
author = {Fedor V. Fomin and
Daniel Lokshtanov and
Saket Saurabh},
editor = {Yuval Rabani},
title = {Bidimensionality and geometric graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1563--1575},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.124},
doi = {10.1137/1.9781611973099.124},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FominLS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FominLST12,
author = {Fedor V. Fomin and
Daniel Lokshtanov and
Saket Saurabh and
Dimitrios M. Thilikos},
editor = {Yuval Rabani},
title = {Linear kernels for (connected) dominating set on \emph{H}-minor-free
graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {82--93},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.7},
doi = {10.1137/1.9781611973099.7},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FominLST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FominV12,
author = {Fedor V. Fomin and
Yngve Villanger},
editor = {Yuval Rabani},
title = {Subexponential parameterized algorithm for minimum fill-in},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1737--1746},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.138},
doi = {10.1137/1.9781611973099.138},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FominV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FountoulakisPS12,
author = {Nikolaos Fountoulakis and
Konstantinos Panagiotou and
Thomas Sauerwald},
editor = {Yuval Rabani},
title = {Ultra-fast rumor spreading in social networks},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1642--1660},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.130},
doi = {10.1137/1.9781611973099.130},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/FountoulakisPS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FrischknechtHW12,
author = {Silvio Frischknecht and
Stephan Holzer and
Roger Wattenhofer},
editor = {Yuval Rabani},
title = {Networks cannot compute their diameter in sublinear time},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1150--1162},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.91},
doi = {10.1137/1.9781611973099.91},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/FrischknechtHW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Gall12,
author = {Fran{\c{c}}ois Le Gall},
editor = {Yuval Rabani},
title = {Improved output-sensitive quantum algorithms for Boolean matrix multiplication},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1464--1476},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.116},
doi = {10.1137/1.9781611973099.116},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Gall12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GeorgiouS12,
author = {Konstantinos Georgiou and
Chaitanya Swamy},
editor = {Yuval Rabani},
title = {Black-box reductions for cost-sharing mechanism design},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {896--913},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.72},
doi = {10.1137/1.9781611973099.72},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/GeorgiouS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GiakkoupisS12,
author = {George Giakkoupis and
Thomas Sauerwald},
editor = {Yuval Rabani},
title = {Rumor spreading and vertex expansion},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1623--1641},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.129},
doi = {10.1137/1.9781611973099.129},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/GiakkoupisS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GoelKK12,
author = {Ashish Goel and
Michael Kapralov and
Sanjeev Khanna},
editor = {Yuval Rabani},
title = {On the communication and streaming complexity of maximum bipartite
matching},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {468--485},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.41},
doi = {10.1137/1.9781611973099.41},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/GoelKK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GoodrichMOT12,
author = {Michael T. Goodrich and
Michael Mitzenmacher and
Olga Ohrimenko and
Roberto Tamassia},
editor = {Yuval Rabani},
title = {Privacy-preserving group data access via stateless oblivious {RAM}
simulation},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {157--167},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.14},
doi = {10.1137/1.9781611973099.14},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/GoodrichMOT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Grohe12,
author = {Martin Grohe},
editor = {Yuval Rabani},
title = {Structural and logical approaches to the graph isomorphism problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {188},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.16},
doi = {10.1137/1.9781611973099.16},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Grohe12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GuptaIKMP12,
author = {Anupam Gupta and
Sungjin Im and
Ravishankar Krishnaswamy and
Benjamin Moseley and
Kirk Pruhs},
editor = {Yuval Rabani},
title = {Scheduling heterogeneous processors isn't as easy as you think},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1242--1253},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.98},
doi = {10.1137/1.9781611973099.98},
timestamp = {Wed, 18 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/GuptaIKMP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GuptaKNR12,
author = {Anupam Gupta and
Ravishankar Krishnaswamy and
Viswanath Nagarajan and
R. Ravi},
editor = {Yuval Rabani},
title = {Approximation algorithms for stochastic orienteering},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1522--1538},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.121},
doi = {10.1137/1.9781611973099.121},
timestamp = {Wed, 18 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/GuptaKNR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GuruswamiRSW12,
author = {Venkatesan Guruswami and
Prasad Raghavendra and
Rishi Saket and
Yi Wu},
editor = {Yuval Rabani},
title = {Bypassing {UGC} from some optimal geometric inapproximability results},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {699--717},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.58},
doi = {10.1137/1.9781611973099.58},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/GuruswamiRSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GuruswamiS12,
author = {Venkatesan Guruswami and
Ali Kemal Sinop},
editor = {Yuval Rabani},
title = {Optimal column-based low-rank matrix reconstruction},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1207--1214},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.95},
doi = {10.1137/1.9781611973099.95},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/GuruswamiS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HaH12,
author = {Bach Q. Ha and
Jason D. Hartline},
editor = {Yuval Rabani},
title = {Mechanism design via consensus estimates, cross checking, and profit
extraction},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {887--895},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.71},
doi = {10.1137/1.9781611973099.71},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/HaH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HalldorssonM12,
author = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Pradipta Mitra},
editor = {Yuval Rabani},
title = {Wireless connectivity and capacity},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {516--526},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.44},
doi = {10.1137/1.9781611973099.44},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/HalldorssonM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HardtRS12,
author = {Moritz Hardt and
Guy N. Rothblum and
Rocco A. Servedio},
editor = {Yuval Rabani},
title = {Private data release via learning thresholds},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {168--187},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.15},
doi = {10.1137/1.9781611973099.15},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/HardtRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HassaniehIKP12,
author = {Haitham Hassanieh and
Piotr Indyk and
Dina Katabi and
Eric Price},
editor = {Yuval Rabani},
title = {Simple and practical algorithm for sparse Fourier transform},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1183--1194},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.93},
doi = {10.1137/1.9781611973099.93},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/HassaniehIKP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HermelinW12,
author = {Danny Hermelin and
Xi Wu},
editor = {Yuval Rabani},
title = {Weak compositions and their applications to polynomial lower bounds
for kernelization},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {104--113},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.9},
doi = {10.1137/1.9781611973099.9},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/HermelinW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HuangK12,
author = {Chien{-}Chung Huang and
Telikepalli Kavitha},
editor = {Yuval Rabani},
title = {Efficient algorithms for maximum weight matchings in general graphs
with small edge weights},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1400--1412},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.110},
doi = {10.1137/1.9781611973099.110},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/HuangK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/IaconoP12,
author = {John Iacono and
Mihai P{u{a}}tra{c{s}}cu},
editor = {Yuval Rabani},
title = {Using hashing to solve the dictionary problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {570--582},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.48},
doi = {10.1137/1.9781611973099.48},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/IaconoP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/IbrahimiKKM12,
author = {Morteza Ibrahimi and
Yashodhan Kanoria and
Matt Kraning and
Andrea Montanari},
editor = {Yuval Rabani},
title = {The set of solutions of random {XORSAT} formulae},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {760--779},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.62},
doi = {10.1137/1.9781611973099.62},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/IbrahimiKKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ImMP12,
author = {Sungjin Im and
Benjamin Moseley and
Kirk Pruhs},
editor = {Yuval Rabani},
title = {Online scheduling with general cost functions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1254--1265},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.99},
doi = {10.1137/1.9781611973099.99},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ImMP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ImpagliazzoMP12,
author = {Russell Impagliazzo and
William Matthews and
Ramamohan Paturi},
editor = {Yuval Rabani},
title = {A satisfiability algorithm for AC\({}^{\mbox{0}}\)},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {961--972},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.77},
doi = {10.1137/1.9781611973099.77},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ImpagliazzoMP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JohannsenKS12,
author = {Daniel Johannsen and
Michael Krivelevich and
Wojciech Samotij},
editor = {Yuval Rabani},
title = {Expanders are universal for the class of all spanning trees},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1539--1551},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.122},
doi = {10.1137/1.9781611973099.122},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/JohannsenKS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KakimuraKK12,
author = {Naonori Kakimura and
Ken{-}ichi Kawarabayashi and
Yusuke Kobayashi},
editor = {Yuval Rabani},
title = {Erd{\"{o}}s-P{\'{o}}sa property and its algorithmic applications:
parity constraints, subset feedback set, and subset packing},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1726--1736},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.137},
doi = {10.1137/1.9781611973099.137},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KakimuraKK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaminskiN12,
author = {Marcin Kaminski and
Naomi Nishimura},
editor = {Yuval Rabani},
title = {Finding an induced path of given parity in planar graphs in polynomial
time},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {656--670},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.55},
doi = {10.1137/1.9781611973099.55},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KaminskiN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KammerT12,
author = {Frank Kammer and
Torsten Tholey},
editor = {Yuval Rabani},
title = {Approximate tree decompositions of planar graphs in linear time},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {683--698},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.57},
doi = {10.1137/1.9781611973099.57},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KammerT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaneN12,
author = {Daniel M. Kane and
Jelani Nelson},
editor = {Yuval Rabani},
title = {Sparser Johnson-Lindenstrauss transforms},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1195--1206},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.94},
doi = {10.1137/1.9781611973099.94},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KaneN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaplanMNS12,
author = {Haim Kaplan and
Shay Mozes and
Yahav Nussbaum and
Micha Sharir},
editor = {Yuval Rabani},
title = {Submatrix maximum queries in Monge matrices and Monge partial matrices,
and their applications},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {338--355},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.31},
doi = {10.1137/1.9781611973099.31},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KaplanMNS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaravelasT12,
author = {Menelaos I. Karavelas and
Eleni Tzanaki},
editor = {Yuval Rabani},
title = {The maximum number of faces of the Minkowski sum of two convex polytopes},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {11--28},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.2},
doi = {10.1137/1.9781611973099.2},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KaravelasT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Kavitha12,
author = {Telikepalli Kavitha},
editor = {Yuval Rabani},
title = {Popularity vs maximum cardinality in the stable marriage setting},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {123--134},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.11},
doi = {10.1137/1.9781611973099.11},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Kavitha12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KawarabayashiK12,
author = {Ken{-}ichi Kawarabayashi and
Yusuke Kobayashi},
editor = {Yuval Rabani},
title = {List-coloring graphs without subdivisions and without immersions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1425--1435},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.112},
doi = {10.1137/1.9781611973099.112},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KawarabayashiK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KawarabayashiO12,
author = {Ken{-}ichi Kawarabayashi and
Kenta Ozeki},
editor = {Yuval Rabani},
title = {Spanning closed walks and {TSP} in 3-connected planar graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {671--682},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.56},
doi = {10.1137/1.9781611973099.56},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KawarabayashiO12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KociumakaKRRW12,
author = {Tomasz Kociumaka and
Marcin Kubica and
Jakub Radoszewski and
Wojciech Rytter and
Tomasz Walen},
editor = {Yuval Rabani},
title = {A linear time algorithm for seeds computation},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1095--1112},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.86},
doi = {10.1137/1.9781611973099.86},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/KociumakaKRRW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KolmanS12,
author = {Petr Kolman and
Christian Scheideler},
editor = {Yuval Rabani},
title = {Approximate duality of multicommodity multiroute flows and cuts: single
source case},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {800--810},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.64},
doi = {10.1137/1.9781611973099.64},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KolmanS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KolmogorovZ12,
author = {Vladimir Kolmogorov and
Stanislav Zivn{\'{y}}},
editor = {Yuval Rabani},
title = {The complexity of conservative valued CSPs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {750--759},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.61},
doi = {10.1137/1.9781611973099.61},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KolmogorovZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Kratsch12,
author = {Stefan Kratsch},
editor = {Yuval Rabani},
title = {Co-nondeterminism in compositions: a kernelization lower bound for
a Ramsey-type problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {114--122},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.10},
doi = {10.1137/1.9781611973099.10},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Kratsch12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KratschW12,
author = {Stefan Kratsch and
Magnus Wahlstr{\"{o}}m},
editor = {Yuval Rabani},
title = {Compression via matroids: a randomized polynomial kernel for odd cycle
transversal},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {94--103},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.8},
doi = {10.1137/1.9781611973099.8},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KratschW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KreutzerT12,
author = {Stephan Kreutzer and
Siamak Tazari},
editor = {Yuval Rabani},
title = {Directed nowhere dense classes of graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1552--1562},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.123},
doi = {10.1137/1.9781611973099.123},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KreutzerT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KrishnaswamyS12,
author = {Ravishankar Krishnaswamy and
Maxim Sviridenko},
editor = {Yuval Rabani},
title = {Inapproximability of the multi-level uncapacitated facility location
problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {718--734},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.59},
doi = {10.1137/1.9781611973099.59},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KrishnaswamyS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Kumar12,
author = {Amit Kumar},
editor = {Yuval Rabani},
title = {Constant factor approximation algorithm for the knapsack median problem},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {824--832},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.66},
doi = {10.1137/1.9781611973099.66},
timestamp = {Thu, 12 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/Kumar12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KushilevitzLO12,
author = {Eyal Kushilevitz and
Steve Lu and
Rafail Ostrovsky},
editor = {Yuval Rabani},
title = {On the (in)security of hash-based oblivious {RAM} and a new balancing
scheme},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {143--156},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.13},
doi = {10.1137/1.9781611973099.13},
timestamp = {Tue, 15 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KushilevitzLO12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LamLMSW12,
author = {Henry Lam and
Zhenming Liu and
Michael Mitzenmacher and
Xiaorui Sun and
Yajun Wang},
editor = {Yuval Rabani},
title = {Information dissemination via random walks in \emph{d}-dimensional
space},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1612--1622},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.128},
doi = {10.1137/1.9781611973099.128},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/LamLMSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LarsenP12,
author = {Kasper Green Larsen and
Rasmus Pagh},
editor = {Yuval Rabani},
title = {I/O-efficient data structures for colored range and prefix reporting},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {583--592},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.49},
doi = {10.1137/1.9781611973099.49},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/LarsenP12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LeeMM12,
author = {James R. Lee and
Arnaud de Mesmay and
Mohammad Moharrami},
editor = {Yuval Rabani},
title = {Dimension reduction for finite trees in \emph{l}\({}_{\mbox{1}}\)},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {43--50},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.4},
doi = {10.1137/1.9781611973099.4},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/LeeMM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Lelarge12,
author = {Marc Lelarge},
editor = {Yuval Rabani},
title = {A new approach to the orientation of random hypergraphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {251--264},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.23},
doi = {10.1137/1.9781611973099.23},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Lelarge12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LemeST12,
author = {Renato Paes Leme and
Vasilis Syrgkanis and
{\'{E}}va Tardos},
editor = {Yuval Rabani},
title = {Sequential auctions and externalities},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {869--886},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.70},
doi = {10.1137/1.9781611973099.70},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/LemeST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LiLY12,
author = {Liang Li and
Pinyan Lu and
Yitong Yin},
editor = {Yuval Rabani},
title = {Approximate counting via correlation decay in spin systems},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {922--940},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.74},
doi = {10.1137/1.9781611973099.74},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/LiLY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LohL12,
author = {Po{-}Shen Loh and
Eyal Lubetzky},
editor = {Yuval Rabani},
title = {Stochastic coalescence in logarithmic time},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {541--550},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.46},
doi = {10.1137/1.9781611973099.46},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/LohL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MakarychevSS12,
author = {Konstantin Makarychev and
Warren Schudy and
Maxim Sviridenko},
editor = {Yuval Rabani},
title = {Concentration inequalities for nonlinear matroid intersection},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {420--436},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.36},
doi = {10.1137/1.9781611973099.36},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/MakarychevSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/McGregorV12,
author = {Andrew McGregor and
Paul Valiant},
editor = {Yuval Rabani},
title = {The shifting sands algorithm},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {453--458},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.39},
doi = {10.1137/1.9781611973099.39},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/McGregorV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MirrokniGZ12,
author = {Vahab S. Mirrokni and
Shayan Oveis Gharan and
Morteza Zadimoghaddam},
editor = {Yuval Rabani},
title = {Simultaneous approximations for adversarial and stochastic online
budgeted allocation},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1690--1701},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.134},
doi = {10.1137/1.9781611973099.134},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/MirrokniGZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MorozA12,
author = {Guillaume Moroz and
Boris Aronov},
editor = {Yuval Rabani},
title = {Computing the distance between piecewise-linear bivariate functions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {288--293},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.27},
doi = {10.1137/1.9781611973099.27},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/MorozA12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MoruzN12,
author = {Gabriel Moruz and
Andrei Negoescu},
editor = {Yuval Rabani},
title = {Outperforming {LRU} via competitive analysis on parametrized inputs
for paging},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1669--1680},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.132},
doi = {10.1137/1.9781611973099.132},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/MoruzN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MozesS12,
author = {Shay Mozes and
Christian Sommer},
editor = {Yuval Rabani},
title = {Exact distance oracles for planar graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {209--222},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.19},
doi = {10.1137/1.9781611973099.19},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/MozesS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/NavarroN12,
author = {Gonzalo Navarro and
Yakov Nekrich},
editor = {Yuval Rabani},
title = {Top-\emph{k} document retrieval in optimal time and linear space},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1066--1077},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.84},
doi = {10.1137/1.9781611973099.84},
timestamp = {Wed, 28 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/NavarroN12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/NewmanR12,
author = {Ilan Newman and
Yuri Rabinovich},
editor = {Yuval Rabani},
title = {On multiplicative {\(\lambda\)}-approximations and some geometric
applications},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {51--67},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.5},
doi = {10.1137/1.9781611973099.5},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/NewmanR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/OnakRRR12,
author = {Krzysztof Onak and
Dana Ron and
Michal Rosen and
Ronitt Rubinfeld},
editor = {Yuval Rabani},
title = {A near-optimal sublinear-time algorithm for approximating the minimum
vertex cover size},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1123--1131},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.88},
doi = {10.1137/1.9781611973099.88},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/OnakRRR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/PhillipsVZ12,
author = {Jeff M. Phillips and
Elad Verbin and
Qin Zhang},
editor = {Yuval Rabani},
title = {Lower bounds for number-in-hand multiparty communication complexity,
made easy},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {486--501},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.42},
doi = {10.1137/1.9781611973099.42},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/PhillipsVZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/PopatW12,
author = {Preyas Popat and
Yi Wu},
editor = {Yuval Rabani},
title = {On the hardness of pricing loss-leaders},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {735--749},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.60},
doi = {10.1137/1.9781611973099.60},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/PopatW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/PoratS12,
author = {Ely Porat and
Martin J. Strauss},
editor = {Yuval Rabani},
title = {Sublinear time, measurement-optimal, sparse recovery for all},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1215--1227},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.96},
doi = {10.1137/1.9781611973099.96},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/PoratS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RaghavendraT12,
author = {Prasad Raghavendra and
Ning Tan},
editor = {Yuval Rabani},
title = {Approximating CSPs with global cardinality constraints using {SDP}
hierarchies},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {373--387},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.33},
doi = {10.1137/1.9781611973099.33},
timestamp = {Tue, 07 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/RaghavendraT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RodittyW12,
author = {Liam Roditty and
Virginia Vassilevska Williams},
editor = {Yuval Rabani},
title = {Subquadratic time approximation algorithms for the girth},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {833--845},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.67},
doi = {10.1137/1.9781611973099.67},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/RodittyW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Rothvoss12,
author = {Thomas Rothvo{\ss}},
editor = {Yuval Rabani},
title = {The entropy rounding method in approximation algorithms},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {356--372},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.32},
doi = {10.1137/1.9781611973099.32},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Rothvoss12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SchalekampWZ12,
author = {Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
editor = {Yuval Rabani},
title = {A proof of the Boyd-Carr conjecture},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1477--1486},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.117},
doi = {10.1137/1.9781611973099.117},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/SchalekampWZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SchudyS12,
author = {Warren Schudy and
Maxim Sviridenko},
editor = {Yuval Rabani},
title = {Concentration and moment inequalities for polynomials of independent
random variables},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {437--446},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.37},
doi = {10.1137/1.9781611973099.37},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/SchudyS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SharathkumarA12,
author = {R. Sharathkumar and
Pankaj K. Agarwal},
editor = {Yuval Rabani},
title = {Algorithms for the transportation problem in geometric settings},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {306--317},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.29},
doi = {10.1137/1.9781611973099.29},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/SharathkumarA12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SinclairST12,
author = {Alistair Sinclair and
Piyush Srivastava and
Marc Thurley},
editor = {Yuval Rabani},
title = {Approximation algorithms for two-state anti-ferromagnetic spin systems
on bounded degree graphs},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {941--953},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.75},
doi = {10.1137/1.9781611973099.75},
timestamp = {Thu, 21 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/SinclairST12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/VaradarajanX12,
author = {Kasturi R. Varadarajan and
Xin Xiao},
editor = {Yuval Rabani},
title = {A near-linear algorithm for projective clustering integer points},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1329--1342},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.105},
doi = {10.1137/1.9781611973099.105},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/VaradarajanX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Vazirani12,
author = {Vijay V. Vazirani},
editor = {Yuval Rabani},
title = {The notion of a rational convex program, and an algorithm for the
Arrow-Debreu Nash bargaining game},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {973--992},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.78},
doi = {10.1137/1.9781611973099.78},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Vazirani12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Vocking12,
author = {Berthold V{\"{o}}cking},
editor = {Yuval Rabani},
title = {A universally-truthful approximation scheme for multi-unit auctions},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {846--855},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.68},
doi = {10.1137/1.9781611973099.68},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Vocking12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Wulff-Nilsen12,
author = {Christian Wulff{-}Nilsen},
editor = {Yuval Rabani},
title = {Approximate distance oracles with improved preprocessing time},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {202--208},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.18},
doi = {10.1137/1.9781611973099.18},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Wulff-Nilsen12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/YousefiY12,
author = {Arman Yousefi and
Neal E. Young},
editor = {Yuval Rabani},
title = {On a linear program for minimum-weight triangulation},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {811--823},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.65},
doi = {10.1137/1.9781611973099.65},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/YousefiY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Zenklusen12,
author = {Rico Zenklusen},
editor = {Yuval Rabani},
title = {Matroidal degree-bounded minimum spanning trees},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1512--1521},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.120},
doi = {10.1137/1.9781611973099.120},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Zenklusen12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/soda/2012,
editor = {Yuval Rabani},
title = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099},
doi = {10.1137/1.9781611973099},
isbn = {978-1-61197-210-8},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/2012.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
retrieved on 2024-05-23 22:04 CEST from data curated by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
