Last active
November 12, 2023 23:26
-
-
Save Zuza/cc1b69afa9e615383e8104f151b2208f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| % Abbreviations | |
| @STRING{lncs = {Lecture Notes in Computer Science (LNCS)}} | |
| @STRING{lnai = {Lecture Notes in Artificial Intelligence (LNAI)}} | |
| @STRING{proc = {Proceedings of the }} | |
| @STRING{cryptadv = {Advances in Cryptology - Proceedings of the }} | |
| @STRING{ijcai = { International Joint Conference on Artificial Intelligence (IJCAI)}} | |
| @STRING{stoc = { Annual ACM Symposium on Theory of Computing (STOC)}} | |
| @STRING{focs = { Symposium on Foundations of Computer Science (FOCS)}} | |
| @STRING{soda = { Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}} | |
| @STRING{eurocrypt = { Eurocrypt Conference}} | |
| @STRING{crypto = { Annual International Cryptology Conference (CRYPTO)}} | |
| @STRING{asiacrypt = { Asiacrypt Conference}} | |
| @STRING{aamas = { International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)}} | |
| @STRING{aaaiold = { National Conference on Artificial Intelligence (AAAI)}} | |
| @STRING{aaai = { AAAI Conference on Artificial Intelligence (AAAI)}} | |
| @STRING{fc = { Annual Conference on Financial Cryptography (FC)}} | |
| @STRING{fcds = { International Conference on Financial Cryptography and Data Security (FC)}} | |
| @STRING{pkc = { International Workshop on Practice and Theory in Public Key Cryptography (PKC)}} | |
| @STRING{ec = { ACM Conference on Economics and Computation (EC)}} | |
| @STRING{ecold = { ACM Conference on Electronic Commerce (EC)}} | |
| @STRING{stacs = { International Symposium on Theoretical Aspects of Computer Science (STACS)}} | |
| @STRING{uai = { Annual Conference on Uncertainty in Artificial Intelligence (UAI)}} | |
| @STRING{tark = { Conference on Theoretical Aspects of Rationality and Knowledge (TARK)}} | |
| @STRING{aaim = { International Conference on Algorithmic Aspects in Information and Management (AAIM)}} | |
| @STRING{agents = { Annual Conference on Autonomous Agents (AGENTS)}} | |
| @STRING{mpref = { Multidisciplinary Workshop on Advances in Preference Handling (M-PREF)}} | |
| @STRING{eacl = { Conference of the European Chapter of the Association for Computational Linguistics (EACL)}} | |
| @STRING{kdd = { International Conference on Knowledge Discovery and Data Mining (KDD)}} | |
| @STRING{swat = { Scandinavian Workshop on Algorithm Theory (SWAT)}} | |
| @STRING{mfcs = { International Symposium on Mathematical Foundations of Computer Science (MFCS)}} | |
| @STRING{comsoc = { International Workshop on Computational Social Choice (COMSOC)}} | |
| @STRING{colt = { Conference on Computational Learning Theory (COLT)}} | |
| @STRING{asiaccs = { ACM Symposium on Information, Computer and Communications Security (ASIACCS)}} | |
| @STRING{eumas = { European Workshop on Multi-Agent Systems (EUMAS)}} | |
| @STRING{wine = { Conference on Web and Internet Economics (WINE)}} | |
| @STRING{esa = { Annual European Symposium on Algorithms (ESA)}} | |
| @STRING{fomc = { International Workshop on Foundations of Mobile Computing (FOMC)}} | |
| @STRING{cie = { Conference on Computability in Europe (CiE)}} | |
| @STRING{cia = { International Workshop on Cooperative Information Agents (CIA)}} | |
| @STRING{p2pecon = { Workshop on the Economics of Peer-to-Peer Systems (P2PECON)}} | |
| @STRING{www = { International World Wide Web Conference (WWW)}} | |
| @STRING{sagt = { International Symposium on Algorithmic Game Theory (SAGT)}} | |
| @STRING{isaac = { Annual International Symposium on Algorithms and Computation (ISAAC)}} | |
| @STRING{icml = { International Conference on Machine Learning (ICML)}} | |
| @STRING{nips = { Annual Conference on Neural Information Processing Systems (NIPS)}} | |
| @STRING{nspw = { New Security Paradigms Workshop (NSPW)}} | |
| @STRING{iat = { IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT)}} | |
| @STRING{atal = { International Workshop on Intelligent Agents (ATAL)}} | |
| @STRING{uist = { Annual ACM symposium on User interface software and technology (UIST)}} | |
| @STRING{hcomp = { Human Computation Workshop (HCOMP)}} | |
| @STRING{nsdi = { USENIX Conference on Networked Systems Design and Implementation (NSDI)}} | |
| @STRING{osdi = { USENIX Symposium on Operating Systems Design and Implementation (OSDI)}} | |
| @STRING{sigcomm = { ACM Symposium on Communications Architectures \& Protocols (SIGCOMM)}} | |
| @STRING{itcs = { Innovations in Theoretical Computer Science Conference (ITCS)}} | |
| @STRING{adt = { International Conference on Algorithmic Decision Theory (ADT)}} | |
| @STRING{sofsem = { International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)}} | |
| @STRING{ecai = { European Conference on Artificial Intelligence (ECAI)}} | |
| @STRING{spaa = { ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}} | |
| @STRING{icalp = { International Colloquium on Automata, Languages and Programming (ICALP)}} | |
| @STRING{mcs = { International Workshop on Multiple Classifier Systems (MCS)}} | |
| @STRING{cig = { IEEE Conference on Computational Intelligence and Games (CIG)}} | |
| @STRING{ipco = { Conference on Integer Programming and Combinatorial Optimization (IPCO)}} | |
| @STRING{sea = { International Symposium on Experimental Algorithms (SEA)}} | |
| @STRING{random = { International Workshop on Randomization and Computation (RANDOM)}} | |
| @STRING{approx = { International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}} | |
| @STRING{gamesec = { Conference on Decision and Game Theory for Security (GameSec)}} | |
| @STRING{cse = { International Conference on Computational Science and Engineering (CSE)}} | |
| @STRING{gtdt = { Workshop on Game Theoretic and Decision Theoretic Agents (GTDT)}} | |
| @STRING{dalt = { International Workshop on Declarative Agent Languages and Technologies (DALT)}} | |
| @STRING{allerton = { Annual Allerton Conference on Communication, Control, and Computing (Allerton)}} | |
| @STRING{ecml = { European Conference on Machine Learning (ECML)}} | |
| @STRING{ala = { Adaptive Learning Agents Workshop (ALA)}} | |
| @STRING{podc = { ACM Symposium on Principles of Distributed Computing (PODC)}} | |
| @STRING{disc = { International Symposium on Distributed Computing (DISC)}} | |
| @STRING{optmas = { International Workshop on Optimization in Multi-Agent Systems (OptMas)}} | |
| @STRING{amec = { International Workshop on Agent-Mediated Electronic Commerce (AMEC)}} | |
| @STRING{latin = { Latin American Theoretical Informatics Symposium (LATIN)}} | |
| @STRING{socg = { Symposium on Computational geometry (SoCG)}} | |
| @STRING{ipdps = { International Parallel and Distributed Processing Symposium (IPDPS)}} | |
| @STRING{waoa = { Workshop on Approximation and Online Algorithms (WAOA)}} | |
| @STRING{isit = { IEEE International Symposium on Information Theory (ISIT)}} | |
| @STRING{itw = { Workshop on Approximation and Online Algorithms (ISIT)}} | |
| @STRING{pods = { ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)}} | |
| @STRING{sosa = { Symposium on Simplicity in Algorithms (SOSA)}} | |
| @STRING{ppopp = { ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP)}} | |
| @STRING{alenex = { Workshop on Algorithm Engineering and Experiments (ALENEX)}} | |
| @STRING{ton = {IEEE/ACM Transactions on Networking (TON)}} | |
| @STRING{jacm = {Journal of the ACM (JACM)}} | |
| @STRING{sicomp = { SIAM Journal on Computing (SICOMP)}} | |
| @STRING{tods = {ACM Transactions on Database Systems (TODS)}} | |
| @STRING{springer = {Springer-Verlag}} | |
| @STRING{acm = {ACM Press}} | |
| @STRING{ieee = {IEEE Press}} | |
| @STRING{ip = {In Preparation}} | |
| @STRING{ur = {Preliminary Draft}} | |
| @string{ta = {To Appear}} | |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| @article{khursheed1981positive, | |
| title={Positive dependence in multivariate distributions}, | |
| author={Khursheed, Alam and Lai Saxena, KM}, | |
| journal={Communications in Statistics - Theory and Methods}, | |
| volume={10}, | |
| number={12}, | |
| pages={1183--1196}, | |
| year={1981}, | |
| publisher={Taylor \& Francis} | |
| } | |
| @article{joag1983negative, | |
| title={Negative association of random variables with applications}, | |
| author={Joag-Dev, Kumar and Proschan, Frank}, | |
| journal={The Annals of Statistics}, | |
| pages={286--295}, | |
| year={1983} | |
| } | |
| @article{dubhashi1996balls, | |
| title={Balls and bins: A study in negative dependence}, | |
| author={Dubhashi, Devdatt and Ranjan, Desh}, | |
| journal={BRICS Report Series}, | |
| volume={3}, | |
| number={25}, | |
| year={1996} | |
| } | |
| %%%%% Some Sources of Theorems Simplified by use of NA %%%% | |
| @article{kamath1995tail, | |
| title={Tail bounds for occupancy and the satisfiability threshold conjecture}, | |
| author={Kamath, Anil and Motwani, Rajeev and Palem, Krishna and Spirakis, Paul}, | |
| journal={Random Structures \& Algorithms}, | |
| volume={7}, | |
| number={1}, | |
| pages={59--80}, | |
| year={1995} | |
| } | |
| @inproceedings{panconesi92fast, | |
| author = {Panconesi, Alessandro and Srinivasan, Aravind}, | |
| title = {Fast Randomized Algorithms for Distributed Edge Coloring}, | |
| booktitle = proc # {11th} # podc, | |
| pages = {251--262}, | |
| year = 1992 | |
| } | |
| @inproceedings{feder1992balanced, | |
| author={Feder, Tom{\'a}s and Mihail, Milena}, | |
| title={Balanced matroids}, | |
| booktitle = proc # {24th} # stoc, | |
| pages={26--38}, | |
| year=1992 | |
| } | |
| %%%% More Properties of NA variables %%%% | |
| @article{shao2000comparison, | |
| title={A comparison theorem on moment inequalities between negatively associated and independent random variables}, | |
| author={Shao, Qi-Man}, | |
| journal={Journal of Theoretical Probability}, | |
| volume={13}, | |
| number={2}, | |
| pages={343--356}, | |
| year={2000} | |
| } | |
| @article{matula1992note, | |
| author={Matu{\l}a, Przemys{\l}aw}, | |
| title={A note on the almost sure convergence of sums of negatively dependent random variables}, | |
| journal={Statistics \& Probability Letters}, | |
| volume={15}, | |
| number={3}, | |
| pages={209--213}, | |
| year={1992} | |
| } | |
| @article{shao1999law, | |
| author={Shao, Qi-Man and Su, Chun}, | |
| title={The law of the iterated logarithm for negatively associated random variables}, | |
| journal={Stochastic Processes and Their Applications}, | |
| volume={83}, | |
| number={1}, | |
| pages={139--148}, | |
| year={1999} | |
| } | |
| %%%% SURVEYS %%%% | |
| @article{borcea2009negative, | |
| author={Borcea, Julius and Br{\"a}nd{\'e}n, Petter and Liggett, Thomas}, | |
| title={Negative dependence and the geometry of polynomials}, | |
| journal={Journal of the American Mathematical Society}, | |
| volume={22}, | |
| number={2}, | |
| pages={521--567}, | |
| year={2009} | |
| } | |
| @personalcommunication{bhattiprolu15, | |
| author={Bhattiprolu, Vijay and Wajc, David}, | |
| year={2015}, | |
| howpublished = "unpublished" | |
| } | |
| @inproceedings{srinivasan2001distributions, | |
| author={Srinivasan, Aravind}, | |
| title={Distributions on level-sets with applications to approximation algorithms}, | |
| booktitle = proc # {42nd} # focs, | |
| pages={588--597}, | |
| year=2001 | |
| } | |
| @article{dubhashi2007positive, | |
| author={Dubhashi, Devdatt and Jonasson, Johan and Ranjan, Desh}, | |
| title={Positive influence and negative dependence}, | |
| journal={Combinatorics, Probability and Computing}, | |
| volume={16}, | |
| number={01}, | |
| pages={29--41}, | |
| year={2007}, | |
| publisher={Cambridge Univ Press} | |
| } | |
| @article{fortuin1971correlation, | |
| author={Fortuin, Cees M and Kasteleyn, Pieter W and Ginibre, Jean}, | |
| title={Correlation inequalities on some partially ordered sets}, | |
| journal={Communications in Mathematical Physics}, | |
| volume={22}, | |
| number={2}, | |
| pages={89--103}, | |
| year={1971} | |
| } | |
| @article{dubhashi1996negative, | |
| title={Negative dependence through the FKG inequality}, | |
| author={Dubhashi, Devdatt P and Priebe, Volker and Ranjan, Desh}, | |
| journal={BRICS Report Series}, | |
| volume={3}, | |
| number={27}, | |
| year={1996} | |
| } | |
| @inproceedings{chekuri2011multi, | |
| author={Chekuri, Chandra and Vondr{\'a}k, Jan and Zenklusen, Rico}, | |
| title={Multi-budgeted matchings and matroid intersection via dependent rounding}, | |
| booktitle = proc # {22nd} # soda, | |
| pages={1080--1097}, | |
| year=2011 | |
| } | |
| @phdthesis{wallenius1963biased, | |
| author={Wallenius, Kenneth T}, | |
| title={Biased sampling; the noncentral hypergeometric probability distribution}, | |
| school={Stanford University}, | |
| year=1963 | |
| } | |
| @article{geary1935ratio, | |
| author={Geary, RC}, | |
| title={The ratio of the mean deviation to the standard deviation as a test of normality}, | |
| journal={Biometrika}, | |
| volume={27}, | |
| number={3/4}, | |
| pages={310--332}, | |
| year={1935} | |
| } | |
| @article{pemantle2014concentration, | |
| author={Pemantle, Robin and Peres, Yuval}, | |
| title={Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures}, | |
| journal={Combinatorics, Probability and Computing}, | |
| volume={23}, | |
| number={1}, | |
| pages={140--160}, | |
| year={2014}, | |
| publisher={Cambridge University Press} | |
| } | |
| @article{panconesi1997randomized, | |
| author={Panconesi, Alessandro and Srinivasan, Aravind}, | |
| title={Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds}, | |
| journal=sicomp, | |
| volume={26}, | |
| number={2}, | |
| pages={350--368}, | |
| year={1997} | |
| } | |
| @article{kuhn1955hungarian, | |
| author={Kuhn, Harold W}, | |
| title={The Hungarian method for the assignment problem}, | |
| journal={Naval research logistics quarterly}, | |
| volume={2}, | |
| number={1-2}, | |
| pages={83--97}, | |
| year={1955} | |
| } | |
| @article{berge1957two, | |
| author={Berge, Claude}, | |
| title={Two theorems in graph theory}, | |
| journal={Proceedings of the National Academy of Sciences}, | |
| volume={43}, | |
| number={9}, | |
| pages={842--844}, | |
| year={1957}, | |
| publisher={National Acad Sciences} | |
| } | |
| @article{edmonds1965paths, | |
| author={Edmonds, Jack}, | |
| title={Paths, trees, and flowers}, | |
| journal={Canadian Journal of mathematics}, | |
| volume={17}, | |
| number={3}, | |
| pages={449--467}, | |
| year={1965} | |
| } | |
| @inproceedings{hopcroft1971n5, | |
| title={An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs}, | |
| author={Hopcroft, John E and Karp, Richard M}, | |
| booktitle={Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT)}, | |
| pages={122--125}, | |
| year=1971 | |
| } | |
| @inproceedings{micali1980v, | |
| title={An ${O}(\sqrt{|V|}{|E|})$ algoithm for finding maximum matching in general graphs}, | |
| author={Micali, Silvio and Vazirani, Vijay V}, | |
| booktitle = proc # {21st} # focs, | |
| pages={17--27}, | |
| year=1980 | |
| } | |
| @article{gabow1982algorithms, | |
| author={Gabow, Harold N and Kariv, Oded}, | |
| title={Algorithms for edge coloring bipartite graphs and multigraphs}, | |
| journal=sicomp, | |
| volume={11}, | |
| number={1}, | |
| pages={117--129}, | |
| year={1982}, | |
| } | |
| @article{cole1982edge, | |
| author={Cole, Richard and Hopcroft, John}, | |
| title={On edge coloring bipartite graphs}, | |
| journal=sicomp, | |
| volume={11}, | |
| number={3}, | |
| pages={540--546}, | |
| year={1982}, | |
| } | |
| @article{schrijver1998bipartite, | |
| author={Schrijver, Alexander}, | |
| title={Bipartite Edge Coloring in {O}(${\Delta}$m) Time}, | |
| journal=sicomp, | |
| volume={28}, | |
| number={3}, | |
| pages={841--846}, | |
| year={1998}, | |
| } | |
| @article{cole2001edge, | |
| author={Cole, Richard and Ost, Kirstin and Schirra, Stefan}, | |
| title={Edge-coloring bipartite multigraphs in ${O}({E} \log {D})$ time}, | |
| journal={Combinatorica}, | |
| volume={21}, | |
| number={1}, | |
| pages={5--12}, | |
| year={2001}, | |
| } | |
| @article{goel2010perfect, | |
| author={Goel, Ashish and Kapralov, Michael and Khanna, Sanjeev}, | |
| title={Perfect matchings via uniform sampling in regular bipartite graphs}, | |
| journal={ACM Transactions on Algorithms (TALG)}, | |
| volume={6}, | |
| number={2}, | |
| pages={27}, | |
| year={2010}, | |
| } | |
| @article{goel2009perfect, | |
| author={Goel, Ashish and Kapralov, Michael and Khanna, Sanjeev}, | |
| title={Perfect Matchings in ${O}(n^{1.5})$ Time in Regular Bipartite Graphs}, | |
| journal={arXiv preprint arXiv:0902.1617}, | |
| year={2009} | |
| } | |
| @article{goel2013perfect, | |
| author={Goel, Ashish and Kapralov, Michael and Khanna, Sanjeev}, | |
| title={Perfect Matchings in ${O}(n \log n)$ Time in Regular Bipartite Graphs}, | |
| journal=sicomp, | |
| volume={42}, | |
| number={3}, | |
| pages={1392--1404}, | |
| year={2013}, | |
| } | |
| @inproceedings{madry2013navigating, | |
| author={Madry, Aleksander}, | |
| title={Navigating central path with electrical flows: From flows to matchings, and back}, | |
| booktitle = proc # {54th} # focs, | |
| pages={253--262}, | |
| year=2013 | |
| } | |
| @book{ahuja1993network, | |
| author={Ahuja, Ravindra K and Magnanti, Thomas L and Orlin, James B}, | |
| title={Network flows - theory, algorithms, and applications}, | |
| year={1993}, | |
| publisher={Prentice hall} | |
| } | |
| @book{lovasz2009matching, | |
| author={Lov{\'a}sz, L{\'a}szl{\'o} and Plummer, Michael D}, | |
| title={Matching theory}, | |
| volume={367}, | |
| year={2009}, | |
| publisher={American Mathematical Society} | |
| } | |
| @book{motwani2010randomized, | |
| author={Motwani, Rajeev and Raghavan, Prabhakar}, | |
| title={Randomized algorithms}, | |
| year={2010}, | |
| publisher={Cambridge University Press} | |
| } | |
| @inproceedings{aggarwal2003switch, | |
| author={Aggarwal, Gagan and Motwani, Rajeev and Shah, Devavrat and Zhu, An}, | |
| title={Switch scheduling via randomized edge coloring}, | |
| booktitle = proc # {44th} # focs, | |
| pages={502--512}, | |
| year=2003 | |
| } | |
| @book{bollobas2013modern, | |
| author={Bollob{\'a}s, B{\'e}la}, | |
| title={Modern graph theory}, | |
| year=2013, | |
| publisher={Springer} | |
| } | |
| @article{alon2003simple, | |
| author={Alon, Noga}, | |
| title={A simple algorithm for edge-coloring bipartite multigraphs}, | |
| journal={Information Processing Letters (IPL)}, | |
| volume={85}, | |
| number={6}, | |
| pages={301--302}, | |
| year={2003}, | |
| } | |
| @article{csima1992matching, | |
| author={Csima, J and Lov{\'a}sz, L{\'a}szl{\'o}}, | |
| title={A matching algorithm for regular bipartite graphs}, | |
| journal={Discrete Applied Mathematics}, | |
| volume={35}, | |
| number={3}, | |
| pages={197--203}, | |
| year={1992}, | |
| } | |
| @article{raghavan1987randomized, | |
| author={Raghavan, Prabhakar and Tompson, Clark D}, | |
| title={Randomized rounding: a technique for provably good algorithms and algorithmic proofs}, | |
| journal={Combinatorica}, | |
| volume={7}, | |
| number={4}, | |
| pages={365--374}, | |
| year={1987}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{srinivasan2001distributions, | |
| author={Srinivasan, Aravind}, | |
| title={Distributions on level-sets with applications to approximation algorithms}, | |
| booktitle = proc # {42nd} # focs, | |
| pages={588--597}, | |
| year=2001 | |
| } | |
| @article{dubhashi2007positive, | |
| author={Dubhashi, Devdatt and Jonasson, Johan and Ranjan, Desh}, | |
| title={Positive influence and negative dependence}, | |
| journal={Combinatorics, Probability and Computing}, | |
| volume={16}, | |
| number={01}, | |
| pages={29--41}, | |
| year={2007}, | |
| publisher={Cambridge Univ Press} | |
| } | |
| @article{ageev2004pipage, | |
| author={Ageev, Alexander A and Sviridenko, Maxim I}, | |
| title={Pipage rounding: A new method of constructing algorithms with proven performance guarantee}, | |
| journal={Journal of Combinatorial Optimization}, | |
| volume={8}, | |
| number={3}, | |
| pages={307--328}, | |
| year={2004}, | |
| publisher={Springer} | |
| } | |
| @article{gandhi2006dependent, | |
| author={Gandhi, Rajiv and Khuller, Samir and Parthasarathy, Srinivasan and Srinivasan, Aravind}, | |
| title={Dependent rounding and its applications to approximation algorithms}, | |
| journal=jacm, | |
| volume={53}, | |
| number={3}, | |
| pages={324--360}, | |
| year={2006}, | |
| } | |
| @inproceedings{gandhi2002dependent, | |
| author={Gandhi, Rajiv and Khuller, Samir and Parthasarathy, Srinivasan and Srinivasan, Aravind}, | |
| title={Dependent rounding in bipartite graphs}, | |
| booktitle = proc # {43rd} # focs, | |
| pages={323--332}, | |
| year=2002 | |
| } | |
| @inproceedings{chekuri2010dependent, | |
| author={Chekuri, Chandra and Vondrak, Jan and Zenklusen, Rico}, | |
| title={Dependent randomized rounding via exchange properties of combinatorial structures}, | |
| booktitle = proc # {51st} # focs, | |
| pages={575--584}, | |
| year=2010 | |
| } | |
| @article{bertsimas1999dependent, | |
| author={Bertsimas, Dimitris and Teo, Chungpiaw and Vohra, Rakesh}, | |
| title={On dependent randomized rounding algorithms}, | |
| journal={Operations Research Letters}, | |
| volume={24}, | |
| number={3}, | |
| pages={105--114}, | |
| year={1999}, | |
| } | |
| @inproceedings{feldman2016online, | |
| author={Feldman, Moran and Svensson, Ola and Zenklusen, Rico}, | |
| title={Online contention resolution schemes}, | |
| booktitle = proc # {27th} # soda, | |
| pages={1014--1033}, | |
| year=2016 | |
| } | |
| @article{harris2017fairness, | |
| title={Fairness in Resource Allocation and Slowed-down Dependent Rounding}, | |
| author={Harris, David G and Pensyl, Thomas and Srinivasan, Aravind and Trinh, Khoa}, | |
| journal={arXiv preprint arXiv:1704.06528}, | |
| year={2017} | |
| } | |
| @inproceedings{arora1996new, | |
| author={Arora, Sanjeev and Frieze, Alan and Kaplan, Haim}, | |
| title={A new rounding procedure for the assignment problem with applications to dense graph arrangement problems}, | |
| booktitle = proc # {37th} # focs, | |
| pages={21--30}, | |
| year=1996 | |
| } | |
| @article{arora2002new, | |
| author={Arora, Sanjeev and Frieze, Alan and Kaplan, Haim}, | |
| title={A new rounding procedure for the assignment problem with applications to dense graph arrangement problems}, | |
| journal={Mathematical programming}, | |
| volume={92}, | |
| number={1}, | |
| pages={1--36}, | |
| year={2002}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{harvey2014pipage, | |
| author={Harvey, Nicholas JA and Olver, Neil}, | |
| title={Pipage rounding, pessimistic estimators and matrix concentration}, | |
| booktitle = proc # {25th} # soda, | |
| pages={926--945}, | |
| year=2014 | |
| } | |
| @inproceedings{doerr2003non, | |
| author={Doerr, Benjamin}, title={Non-independent randomized rounding}, | |
| booktitle = proc # {14th} # soda, | |
| pages={506--507}, | |
| year=2003 | |
| } | |
| @article{doerr2005nonindependent, | |
| author={Doerr, Benjamin}, | |
| title={Nonindependent randomized rounding and an application to digital halftoning}, | |
| journal=sicomp, | |
| volume={34}, | |
| number={2}, | |
| pages={299--317}, | |
| year={2005}, | |
| } | |
| @inproceedings{doerr2006generating, | |
| author={Doerr, Benjamin}, | |
| title={Generating randomized roundings with cardinality constraints and derandomizations}, | |
| booktitle = proc # {23rd} # stacs, | |
| pages={571--583}, | |
| year=2006 | |
| } | |
| %%%%%%% APPLICATIONS %%%%%%%% | |
| @article{bansal2012lp, | |
| author={Bansal, Nikhil and Gupta, Anupam and Li, Jian and Mestre, Juli{\'a}n and Nagarajan, Viswanath and Rudra, Atri}, | |
| title={When LP is the cure for your matching woes: Improved bounds for stochastic matchings}, | |
| journal={Algorithmica}, | |
| volume={63}, | |
| number={4}, | |
| pages={733--762}, | |
| year={2012}, | |
| publisher={Springer} | |
| } | |
| @article{calinescu2011maximizing, | |
| author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan}, | |
| title={Maximizing a monotone submodular function subject to a matroid constraint}, | |
| journal=sicomp, | |
| volume={40}, | |
| number={6}, | |
| pages={1740--1766}, | |
| year=2011 | |
| } | |
| @inproceedings{chekuri2011multi, | |
| author={Chekuri, Chandra and Vondr{\'a}k, Jan and Zenklusen, Rico}, | |
| title={Multi-budgeted matchings and matroid intersection via dependent rounding}, | |
| booktitle = proc # {22nd} # soda, | |
| pages={1080--1097}, | |
| year=2011 | |
| } | |
| @misc{iab2014, | |
| author = "PricewaterhouseCoopers", | |
| title = "{IAB} internet advertising revenue report -- 2014 full year results", | |
| year = "2015", | |
| url = "\url{http://www.iab.net/media/file/PwC_IAB_Webinar_Presentation_FY2014_PWC.pdf}", | |
| note = "[Online; accessed 17-December-2015]" | |
| } | |
| @article{kurtz1970solutions, | |
| title={Solutions of ordinary differential equations as limits of pure jump Markov processes}, | |
| author={Kurtz, Thomas G}, | |
| journal={Journal of Applied Probability}, | |
| volume={7}, | |
| number={1}, | |
| pages={49--58}, | |
| year={1970}, | |
| publisher={JSTOR} | |
| } | |
| @inproceedings{yao1977lemma, | |
| author = {Yao, Andrew Chi-Chin}, | |
| title = {Probabilistic Computations: Toward a Unified Measure of Complexity}, | |
| booktitle = proc # {18th} # focs, | |
| pages = {222--227}, | |
| year = 1977 | |
| } | |
| @inproceedings{karp1990optimal, | |
| author={Karp, Richard M and Vazirani, Umesh V and Vazirani, Vijay V}, | |
| title={An optimal algorithm for on-line bipartite matching}, | |
| booktitle = proc # {22nd} # stoc, | |
| pages={352--358}, | |
| year=1990 | |
| } | |
| @article{kalyanasundaram2000optimal, | |
| title={An optimal deterministic algorithm for online $b$-matching}, | |
| author={Kalyanasundaram, Bala and Pruhs, Kirk R}, | |
| journal={Theoretical Computer Science (TCS)}, | |
| volume={233}, | |
| number={1}, | |
| pages={319--325}, | |
| year={2000}, | |
| } | |
| @article{mehta2007adwords, | |
| author={Mehta, Aranyak and Saberi, Amin and Vazirani, Umesh and Vazirani, Vijay}, | |
| title={Adwords and generalized online matching}, | |
| journal=jacm, | |
| volume={54}, | |
| number={5}, | |
| pages={22}, | |
| year={2007}, | |
| } | |
| @inproceedings{mahdian2007allocating, | |
| author={Mahdian, Mohammad and Nazerzadeh, Hamid and Saberi, Amin}, | |
| title={Allocating online advertisement space with unreliable estimates}, | |
| booktitle = proc # {8th} # ecold, | |
| pages={288--294}, | |
| year=2007 | |
| } | |
| @incollection{buchbinder2007online, | |
| author={Buchbinder, Niv and Jain, Kamal and Naor, Joseph (Seffi)}, | |
| title={Online primal-dual algorithms for maximizing ad-auctions revenue}, | |
| booktitle = proc # {15th} # esa, | |
| pages={253--264}, | |
| year=2007 | |
| } | |
| @inproceedings{abrams2007optimal, | |
| author={Abrams, Zoe and Mendelevitch, Ofer and Tomlin, John}, | |
| title={Optimal delivery of sponsored search advertisements subject to budget constraints}, | |
| booktitle = proc # {8th} # ecold, | |
| pages={272--278}, | |
| year=2007 | |
| } | |
| @article{birnbaum2008line, | |
| author={Birnbaum, Benjamin and Mathieu, Claire}, | |
| title={On-line bipartite matching made simple}, | |
| journal={ACM SIGACT News}, | |
| volume={39}, | |
| number={1}, | |
| pages={80--87}, | |
| year={2008}, | |
| } | |
| @inproceedings{goel2008online, | |
| author={Goel, Gagan and Mehta, Aranyak}, | |
| title={Online budgeted matching in random input models with applications to adwords}, | |
| booktitle = proc # {19th} # soda, | |
| pages={982--991}, | |
| year=2008 | |
| } | |
| @incollection{aggarwal2008sponsored, | |
| author={Aggarwal, Gagan and Feldman, Jon and Muthukrishnan, S and P{\'a}l, Martin}, | |
| title={Sponsored search auctions with markovian users}, | |
| booktitle = proc # {4th} # wine, | |
| pages={621--628}, | |
| year=2008 | |
| } | |
| @inproceedings{devanur2009adwords, | |
| author={Devanur, Nikhil R and Hayes, Thomas P}, | |
| title={The adwords problem: online keyword matching with budgeted bidders under random permutations}, | |
| booktitle = proc # {10th} # ecold, | |
| booktitle={Proceedings of the 10th ACM conference on Electronic commerce}, | |
| pages={71--78}, | |
| year=2009 | |
| } | |
| @inproceedings{feldman2009online, | |
| author={Feldman, Jon and Mehta, Aranyak and Mirrokni, Vahab and Muthukrishnan, S}, | |
| title={Online stochastic matching: Beating 1-1/e}, | |
| booktitle = proc # {50th} # focs, | |
| pages={117--126}, | |
| year=2009 | |
| } | |
| @inproceedings{feldman2009online2, | |
| author={Feldman, Jon and Korula, Nitish and Mirrokni, Vahab and Muthukrishnan, S and P{\'a}l, Martin}, | |
| title={Online ad assignment with free disposal}, | |
| booktitle = proc # {5th} # wine, | |
| pages={374--385}, | |
| year=2009 | |
| } | |
| @article{buchbinder2009design, | |
| author={Buchbinder, Niv and Naor, Joseph (Seffi)}, | |
| title={The design of competitive online algorithms via a primal: dual approach}, | |
| journal={Foundations and Trends{\textregistered} in Theoretical Computer Science (TCS)}, | |
| volume={3}, | |
| number={2--3}, | |
| pages={93--263}, | |
| year={2009}, | |
| publisher={Now Publishers Inc.} | |
| } | |
| @inproceedings{mirrokni2012simultaneous, | |
| author={Mirrokni, Vahab S and Gharan, Shayan Oveis and Zadimoghaddam, Morteza}, | |
| title={Simultaneous approximations for adversarial and stochastic online budgeted allocation}, | |
| booktitle = proc # {23rd} # soda, | |
| pages={1690--1701}, | |
| year=2012 | |
| } | |
| @incollection{bahmani2010improved, | |
| author={Bahmani, Bahman and Kapralov, Michael}, | |
| title={Improved bounds for online stochastic matching}, | |
| booktitle = proc # {18th} # esa, | |
| pages={170--181}, | |
| year=2010 | |
| } | |
| @incollection{feldman2010online, | |
| author={Feldman, Jon and Henzinger, Monika and Korula, Nitish and Mirrokni, Vahab S and Stein, Cliff}, | |
| title={Online stochastic packing applied to display ad allocation}, | |
| booktitle = proc # {18th} # esa, | |
| pages={182--194}, | |
| year=2010 | |
| } | |
| @inproceedings{karande2011online, | |
| author={Karande, Chinmay and Mehta, Aranyak and Tripathi, Pushkar}, | |
| title={Online bipartite matching with unknown distributions}, | |
| booktitle = proc # {43rd} # stoc, | |
| pages={587--596}, | |
| year=2011 | |
| } | |
| @incollection{bansal2010lp, | |
| author={Bansal, Nikhil and Gupta, Anupam and Li, Jian and Mestre, Juli{\'a}n and Nagarajan, Viswanath and Rudra, Atri}, | |
| title={When lp is the cure for your matching woes: Improved bounds for stochastic matchings}, | |
| booktitle = proc # {18th} # esa, | |
| pages={218--229}, | |
| year=2010 | |
| } | |
| @inproceedings{mahdian2011online, | |
| author={Mahdian, Mohammad and Yan, Qiqi}, | |
| title={Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps}, | |
| booktitle = proc # {43rd} # stoc, | |
| pages={597--606}, | |
| year=2011 | |
| } | |
| @incollection{haeupler2011online, | |
| title={Online stochastic weighted matching: Improved approximation algorithms}, | |
| author={Haeupler, Bernhard and Mirrokni, Vahab S and Zadimoghaddam, Morteza}, | |
| booktitle = proc # {7th} # wine, | |
| pages={170--181}, | |
| year=2011 | |
| } | |
| @inproceedings{aggarwal2011online, | |
| author={Aggarwal, Gagan and Goel, Gagan and Karande, Chinmay and Mehta, Aranyak}, | |
| title={Online vertex-weighted bipartite matching and single-bid budgeted allocations}, | |
| booktitle = proc # {22nd} # soda, | |
| pages={1253--1264}, | |
| year=2011 | |
| } | |
| @article{devanur2011online, | |
| author={Devanur, Nikhil R}, | |
| title={Online algorithms with stochastic input}, | |
| journal={ACM SIGecom Exchanges}, | |
| volume={10}, | |
| number={2}, | |
| pages={40--49}, | |
| year={2011}, | |
| } | |
| @article{mehta2012online, | |
| author={Mehta, Aranyak}, | |
| title={Online Matching and Ad Allocation}, | |
| journal={Theoretical Computer Science (TCS)}, | |
| volume={8}, | |
| number={4}, | |
| pages={265--368}, | |
| year={2012} | |
| } | |
| @article{manshadi2012online, | |
| author={Manshadi, Vahideh H and Gharan, Shayan Oveis and Saberi, Amin}, | |
| title={Online stochastic matching: Online actions based on offline statistics}, | |
| journal={Mathematics of Operations Research}, | |
| volume={37}, | |
| number={4}, | |
| pages={559--573}, | |
| year={2012}, | |
| publisher={INFORMS} | |
| } | |
| @inproceedings{devanur2012asymptotically, | |
| author={Devanur, Nikhil R and Sivan, Balasubramanian and Azar, Yossi}, | |
| title={Asymptotically optimal algorithm for stochastic adwords}, | |
| booktitle = proc # {13th} # ecold, | |
| pages={388--404}, | |
| year=2012 | |
| } | |
| @inproceedings{devanur2013randomized, | |
| author={Devanur, Nikhil R and Jain, Kamal and Kleinberg, Robert D}, | |
| title={Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching}, | |
| booktitle = proc # {24th} # soda, | |
| pages={101--107}, | |
| year=2013 | |
| } | |
| @article{jaillet2013online, | |
| title={Online stochastic matching: New algorithms with better bounds}, | |
| author={Jaillet, Patrick and Lu, Xin}, | |
| journal={Mathematics of Operations Research}, | |
| year={2013}, | |
| publisher={INFORMS} | |
| } | |
| @article{fiat1991competitive, | |
| title={Competitive paging algorithms}, | |
| author={Fiat, Amos and Karp, Richard M and Luby, Michael and McGeoch, Lyle A and Sleator, Daniel D and Young, Neal E}, | |
| journal={Journal of Algorithms}, | |
| volume={12}, | |
| number={4}, | |
| pages={685--699}, | |
| year={1991}, | |
| } | |
| @inproceedings{naor2015near, | |
| author={Naor, Joseph (Seffi) and Wajc, David}, | |
| title={Near-optimum online ad allocation for targeted advertising}, | |
| booktitle = proc # {16th} # ec, | |
| pages={131--148}, | |
| year=2015 | |
| } | |
| @inproceedings{epstein2013improved, | |
| author={Epstein, Leah and Levin, Asaf and Segev, Danny and Weimann, Oren}, | |
| title={Improved Bounds for Online Preemptive Matching}, | |
| booktitle = proc # {30th} # stacs, | |
| pages={389}, | |
| year=2013 | |
| } | |
| @inproceedings{wang2015two, | |
| author={Wang, Yajun and Wong, Sam Chiu-wai}, | |
| title={Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm}, | |
| booktitle = proc # {42nd} # icalp, | |
| pages={1070--1081}, | |
| year=2015 | |
| } | |
| @inproceedings{azar2017online, | |
| author={Azar, Yossi and Cohen, Ilan Reuven and Roytman, Alan}, | |
| title={Online Lower Bounds via Duality}, | |
| booktitle = proc # {28th} # soda, | |
| pages={1038--1050}, | |
| year=2017 | |
| } | |
| @article{arora2012multiplicative, | |
| author={Arora, Sanjeev and Hazan, Elad and Kale, Satyen}, | |
| title={The Multiplicative Weights Update Method: a Meta-Algorithm and Applications.}, | |
| journal={Theory of Computing}, | |
| volume={8}, | |
| number={1}, | |
| pages={121--164}, | |
| year={2012} | |
| } | |
| @article{konig1916graphen, | |
| title={{\"U}ber graphen und ihre anwendung auf determinantentheorie und mengenlehre}, | |
| author={K{\"o}nig, D{\'e}nes}, | |
| journal={Mathematische Annalen}, | |
| volume={77}, | |
| number={4}, | |
| pages={453--465}, | |
| year=1916 | |
| } | |
| @article{egervary1931matrixok, | |
| author={Egerv{\'a}ry, Jeno}, | |
| title={Matrixok kombinatorius tulajdons{\'a}gair{\'o}l}, | |
| journal={Matematikai {\'e}s Fizikai Lapok}, | |
| volume={38}, | |
| number={1931}, | |
| pages={16--28}, | |
| year=1931 | |
| } | |
| @article{konig1931graphen, | |
| author={K{\"o}nig, D{\'e}nes}, | |
| title={Gr{\'a}fok {\'e}s m{\'a}trixok}, | |
| journal={Matematikai {\'e}s Fizikai Lapok}, | |
| volume={38}, | |
| number={1931}, | |
| pages={116--119}, | |
| year=1931 | |
| } | |
| @article{hall1935representatives, | |
| title={On representatives of subsets}, | |
| author={Hall, Philip}, | |
| journal={Journal of the London Mathematical Society}, | |
| volume={1}, | |
| number={1}, | |
| pages={26--30}, | |
| year=1935 | |
| } | |
| @inproceedings{brubach2016new, | |
| author = {Brian Brubach and Karthik Abinav Sankararaman and Aravind Srinivasan and Pan Xu}, | |
| title = {New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching}, | |
| booktitle = proc # {24th} # esa, | |
| pages = {24:1--24:16}, | |
| year = 2016 | |
| } | |
| @article{peleg2000near, | |
| author = {Peleg, David and Rubinovich, Vitaly}, | |
| title = {A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction}, | |
| journal = sicomp, | |
| issue_date = {2000}, | |
| volume = {30}, | |
| number = {5}, | |
| month = may, | |
| pages = {1427--1442}, | |
| year = 2000 | |
| } | |
| @inproceedings{pandurangan2017time, | |
| author={Pandurangan, Gopal and Robinson, Peter and Scquizzato, Michele}, | |
| title={A time- and message-optimal distributed algorithm for minimum spanning trees}, | |
| booktitle = proc # {49th} # stoc, | |
| pages={743--756}, | |
| year=2017 | |
| } | |
| @article{awerbuch1990tradeoff, | |
| author = {Awerbuch, Baruch and Goldreich, Oded and Vainish, Ronen and Peleg, David}, | |
| title = {A Trade-off Between Information and Communication in Broadcast Protocols}, | |
| journal=jacm, | |
| volume = {37}, | |
| number = {2}, | |
| pages = {238--256}, | |
| year = 1990 | |
| } | |
| @article{elkin2017simple, | |
| author = {Elkin, Michael}, | |
| title = {A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities}, | |
| booktitle = proc # {36th} # podc, | |
| year = 2017 | |
| } | |
| @inproceedings{haeupler2016low, | |
| author={Haeupler, Bernhard and Izumi, Taisuke and Zuzic, Goran}, | |
| title={Low-congestion shortcuts without embedding}, | |
| booktitle = proc # {35th} # podc, | |
| pages={451--460}, | |
| year=2016 | |
| } | |
| @article {haeupler2016lowconference, | |
| AUTHOR = {Haeupler, Bernhard and Izumi, Taisuke and Zuzic, Goran}, | |
| TITLE = {Low-{C}ongestion shortcuts without embedding}, | |
| JOURNAL = {Distrib. Comput.}, | |
| FJOURNAL = {Distributed Computing}, | |
| VOLUME = {34}, | |
| YEAR = {2021}, | |
| NUMBER = {1}, | |
| PAGES = {79--90}, | |
| ISSN = {0178-2770}, | |
| MRCLASS = {68W15}, | |
| MRNUMBER = {4207470}, | |
| DOI = {10.1007/s00446-020-00383-2}, | |
| URL = {https://doi.org/10.1007/s00446-020-00383-2}, | |
| } | |
| @inproceedings{ghaffari2016distributed, | |
| author = {Ghaffari, Mohsen and Haeupler, Bernhard}, | |
| title = {Distributed Algorithms for Planar Networks {II}: Low-congestion Shortcuts, MST, and Min-Cut}, | |
| booktitle = proc # {27th} # soda, | |
| pages = {202--219}, | |
| year = 2016 | |
| } | |
| @article{cole1986deterministic, | |
| author={Cole, Richard and Vishkin, Uzi}, | |
| title={Deterministic coin tossing with applications to optimal parallel list ranking}, | |
| journal={Information and Control}, | |
| volume={70}, | |
| number={1}, | |
| pages={32--53}, | |
| year=1986 | |
| } | |
| @article{panconesi2001some, | |
| author={Panconesi, Alessandro and Rizzi, Romeo}, | |
| title={Some simple distributed algorithms for sparse networks}, | |
| journal={Distributed computing}, | |
| volume={14}, | |
| number={2}, | |
| pages={97--100}, | |
| year=2001 | |
| } | |
| @article{sleator1983data, | |
| author={Sleator, Daniel D and Tarjan, Robert Endre}, | |
| title={A data structure for dynamic trees}, | |
| journal={Journal of Computer and System Sciences}, | |
| volume={26}, | |
| number={3}, | |
| pages={362--391}, | |
| year=1983 | |
| } | |
| @inproceedings{haeupler2016near, | |
| title={Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs}, | |
| author={Haeupler, Bernhard and Izumi, Taisuke and Zuzic, Goran}, | |
| booktitle = proc # {30th} # disc, | |
| pages={158--172}, | |
| year={2016}, | |
| } | |
| @article{nesetril2001otakar, | |
| author = "Jaroslav Nešetřil and Eva Milková and Helena Nešetřilová", | |
| title = "Otakar Borůvka on Minimum Spanning Tree Problem Translation of Both the 1926 Papers, Comments, History", | |
| journal = "Discrete Mathematics", | |
| volume = {233}, | |
| number = {1}, | |
| pages = {3--36}, | |
| year = 2001 | |
| } | |
| @book{peleg2000distributed, | |
| title={Distributed computing}, | |
| author={Peleg, David}, | |
| journal={SIAM Monographs on discrete mathematics and applications}, | |
| volume={5}, | |
| year={2000} | |
| } | |
| @article{gallager1983distributed, | |
| author={Gallager, Robert G. and Humblet, Pierre A. and Spira, Philip M.}, | |
| title={A distributed algorithm for minimum-weight spanning trees}, | |
| journal={ACM Transactions on Programming Languages and Systems}, | |
| volume={5}, | |
| number={1}, | |
| pages={66--77}, | |
| year=1983 | |
| } | |
| @article{garay1998sublinear, | |
| title={A sublinear time distributed algorithm for minimum-weight spanning trees}, | |
| author={Garay, Juan A and Kutten, Shay and Peleg, David}, | |
| journal={SIAM Journal on Computing}, | |
| volume={27}, | |
| number={1}, | |
| pages={302--316}, | |
| year={1998}, | |
| publisher={SIAM} | |
| } | |
| @inproceedings{garay1993sublinear, | |
| author={Garay, Juan A and Kutten, Shay and Peleg, David}, | |
| title={A sublinear time distributed algorithm for minimum-weight spanning trees}, | |
| booktitle = proc # {34th} # focs, | |
| year=1993 | |
| } | |
| @inproceedings{kutten1995fast, | |
| author={Kutten, Shay and Peleg, David}, | |
| title={Fast distributed construction of k-dominating sets and applications}, | |
| booktitle = proc # {14th} # podc, | |
| pages={238--251}, | |
| year=1995 | |
| } | |
| @article{elkin2006faster, | |
| author={Elkin, Michael}, | |
| title={A faster distributed protocol for constructing a minimum spanning tree}, | |
| journal={Journal of Computer and System Sciences}, | |
| volume={72}, | |
| number={8}, | |
| pages={1282--1308}, | |
| year=2006 | |
| } | |
| @article{dassarma2012distributed, | |
| author={Das Sarma, Atish and Holzer, Stephan and Kor, Liah and Korman, Amos and Nanongkai, Danupon and Pandurangan, Gopal and Peleg, David and Wattenhofer, Roger}, | |
| title={Distributed verification and hardness of distributed approximation}, | |
| journal={SIAM Journal on Computing (SICOMP)}, | |
| volume={41}, | |
| number={5}, | |
| pages={1235--1265}, | |
| year=2012 | |
| } | |
| @inproceedings{ghaffari2013distributed, | |
| author={Ghaffari, Mohsen and Kuhn, Fabian}, | |
| title={Distributed minimum cut approximation}, | |
| booktitle = proc # {27th} # disc, | |
| pages={1--15}, | |
| year=2013 | |
| } | |
| @inproceedings{nanongkai2014almost, | |
| author={Nanongkai, Danupon and Su, Hsin-Hao}, | |
| title={Almost-tight distributed minimum cut algorithms}, | |
| booktitle = proc # {28th} # disc, | |
| pages={439--453}, | |
| year=2014 | |
| } | |
| @inproceedings{ghaffari2014near, | |
| author={Ghaffari, Mohsen}, | |
| title={Near-optimal distributed approximation of minimum-weight connected dominating set}, | |
| booktitle = proc # {41nd} # icalp, | |
| pages={483--494}, | |
| year=2014 | |
| } | |
| @inproceedings{khan2006fast, | |
| author={Khan, Maleq and Pandurangan, Gopal}, | |
| title={A fast distributed approximation algorithm for minimum spanning trees}, | |
| booktitle = proc # {20th} # disc, | |
| pages={355--369}, | |
| year=2006 | |
| } | |
| @inproceedings{nanongkai2014distributed, | |
| author={Nanongkai, Danupon}, | |
| title={Distributed approximation algorithms for weighted shortest paths}, | |
| booktitle = proc # {46th} # stoc, | |
| pages={565--573}, | |
| year=2014 | |
| } | |
| @inproceedings{frischknecht2012networks, | |
| author={Frischknecht, Silvio and Holzer, Stephan and Wattenhofer, Roger}, | |
| title={Networks cannot compute their diameter in sublinear time}, | |
| booktitle = proc # {23rd} # soda, | |
| pages={1150--1162}, | |
| year=2012 | |
| } | |
| @inproceedings{holzer2012optimal, | |
| author={Holzer, Stephan and Wattenhofer, Roger}, | |
| title={Optimal distributed all pairs shortest paths and applications}, | |
| booktitle = proc # {31st} # podc, | |
| pages={355--364}, | |
| year=2012 | |
| } | |
| @inproceedings{lenzen2013efficient, | |
| author={Lenzen, Christoph and Peleg, David}, | |
| title={Efficient distributed source detection with limited bandwidth}, | |
| booktitle = proc # {32nd} # podc, | |
| pages={375--382}, | |
| year=2013 | |
| } | |
| @inproceedings{lenzen2015fast, | |
| author={Lenzen, Christoph and Patt-Shamir, Boaz}, | |
| title={Fast partial distance estimation and applications}, | |
| booktitle = proc # {34th} # podc, | |
| pages={153--162}, | |
| year=2015 | |
| } | |
| @inproceedings{izumi2014time, | |
| author={Izumi, Taisuke and Wattenhofer, Roger}, | |
| title={Time Lower Bounds for Distributed Distance Oracles}, | |
| booktitle={International Conference on Principles of Distributed Systems (OPODIS)}, | |
| pages={60--75}, | |
| year=2014 | |
| } | |
| @article{elkin2006unconditional, | |
| author={Elkin, Michael}, | |
| title={An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem}, | |
| journal=sicomp, | |
| volume={36}, | |
| number={2}, | |
| pages={433--456}, | |
| year=2006 | |
| } | |
| @article{kutten2015complexity, | |
| author={Kutten, Shay and Pandurangan, Gopal and Peleg, David and Robinson, Peter and Trehan, Amitabh}, | |
| title={On the complexity of universal leader election}, | |
| journal=jacm, | |
| volume={62}, | |
| number={1}, | |
| pages={7}, | |
| year=2015 | |
| } | |
| @inproceedings{ivkovic1993fully, | |
| title={Fully Dynamic Maintenance of Vertex Cover}, | |
| author={Ivkovic, Zoran and Lloyd, Errol L}, | |
| booktitle={Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science}, | |
| pages={99--111}, | |
| year={1993} | |
| } | |
| @inproceedings{sankowski2007faster, | |
| title={Faster dynamic matchings and vertex connectivity}, | |
| author={Sankowski, Piotr}, | |
| booktitle = proc # {18th} # soda, | |
| pages={118--126}, | |
| year={2007} | |
| } | |
| @inproceedings{onak2010maintaining, | |
| title={Maintaining a large matching and a small vertex cover}, | |
| author={Onak, Krzysztof and Rubinfeld, Ronitt}, | |
| booktitle = proc # {42nd} # stoc, | |
| pages={457--464}, | |
| year={2010} | |
| } | |
| @incollection{brodal1999dynamic, | |
| title={Dynamic representations of sparse graphs}, | |
| author={Brodal, Gerth St{\o}lting and Fagerberg, Rolf}, | |
| booktitle={Workshop on Algorithms and Data Structures}, | |
| pages={342--351}, | |
| year={1999} | |
| } | |
| @inproceedings{baswana2011fully, | |
| title={Fully dynamic maximal matching in ${O} (\log n)$ update time}, | |
| author={Baswana, Surender and Gupta, Manoj and Sen, Sandeep}, | |
| booktitle = proc # {52nd} # focs, | |
| pages={383--392}, | |
| year={2011} | |
| } | |
| @article{baswana2015fully, | |
| title={Fully Dynamic Maximal Matching in ${O}(\log n)$ Update Time}, | |
| author={Baswana, Surender and Gupta, Manoj and Sen, Sandeep}, | |
| journal=sicomp, | |
| volume={44}, | |
| number={1}, | |
| pages={88--113}, | |
| year={2015} | |
| } | |
| @inproceedings{gupta2013fully, | |
| title={Fully dynamic $(1+\eps)$-approximate matchings}, | |
| author={Gupta, Manoj and Peng, Richard}, | |
| booktitle = proc # {54th} # focs, | |
| pages={548--557}, | |
| year={2013} | |
| } | |
| @incollection{KKPS13, | |
| title={Orienting fully dynamic graphs with worst-case time bounds}, | |
| author={Kopelowitz, Tsvi and Krauthgamer, Robert and Porat, Ely and Solomon, Shay}, | |
| booktitle = proc # {41st} # icalp, | |
| pages={532--543}, | |
| year={2014} | |
| } | |
| @inproceedings{neiman2013simple, | |
| title={Simple deterministic algorithms for fully dynamic maximal matching}, | |
| author={Neiman, Ofer and Solomon, Shay}, | |
| booktitle = proc # {45th} # stoc, | |
| pages={745--754}, | |
| year={2013} | |
| } | |
| @article{neiman2016simple, | |
| title={Simple deterministic algorithms for fully dynamic maximal matching}, | |
| author={Neiman, Ofer and Solomon, Shay}, | |
| journal={ACM Transactions on Algorithms (TALG)}, | |
| volume={12}, | |
| number={1}, | |
| pages={7}, | |
| year={2016} | |
| } | |
| @inproceedings{gupta2014maintaining, | |
| title={Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time}, | |
| author={Gupta, Manoj and Raman, Venkatesh and Suresh, SP}, | |
| booktitle={Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS)}, | |
| volume={29}, | |
| pages={227--239}, | |
| year={2014} | |
| } | |
| @inproceedings{abboud2014popular, | |
| title={Popular conjectures imply strong lower bounds for dynamic problems}, | |
| author={Abboud, Amir and Vassilevska Williams, Virginia}, | |
| booktitle = proc # {55th} # focs, | |
| pages={434--443}, | |
| year={2014} | |
| } | |
| @inproceedings{bosek2014online, | |
| title={Online bipartite matching in offline time}, | |
| author={Bosek, Bartlomiej and Leniowski, Dariusz and Sankowski, Piotr and Zych, Anna}, | |
| booktitle = proc # {55th} # focs, | |
| pages={384--393}, | |
| year={2014} | |
| } | |
| @inproceedings{bhattacharya2015deterministic, | |
| title={Deterministic fully dynamic data structures for vertex cover and matching}, | |
| author={Bhattacharya, Sayan and Henzinger, Monika and Italiano, Giuseppe F}, | |
| booktitle = proc # {26th} # soda, | |
| pages={785--804}, | |
| year={2015} | |
| } | |
| @inproceedings{bhattacharya2016new, | |
| title={New deterministic approximation algorithms for fully dynamic matching}, | |
| author={Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon}, | |
| booktitle = proc # {48th} # stoc, | |
| pages={398--411}, | |
| year={2016} | |
| } | |
| @article{bhattacharya2016new2, | |
| author = {Sayan Bhattacharya and | |
| Monika Henzinger and | |
| Danupon Nanongkai}, | |
| title = {New Deterministic Approximation Algorithms for Fully Dynamic Matching}, | |
| journal = {CoRR}, | |
| volume = {abs/1604.05765}, | |
| year = {2016}, | |
| } | |
| @article{lund1999paging, | |
| author = {Carsten Lund and | |
| Steven Phillips and | |
| Nick Reingold}, | |
| title = {Paging Against a Distribution and {IP} Networking}, | |
| journal = {Journal of Computer and System Sciences}, | |
| volume = {58}, | |
| number = {1}, | |
| pages = {222--232}, | |
| year = {1999}, | |
| } | |
| @article{karlin2000markov, | |
| author = {Anna R. Karlin and | |
| Steven J. Phillips and | |
| Prabhakar Raghavan}, | |
| title = {Markov Paging}, | |
| journal = sicomp, | |
| volume = {30}, | |
| number = {3}, | |
| pages = {906--922}, | |
| year = {2000} | |
| } | |
| @inproceedings{brach2016algorithmic, | |
| author = {Pawel Brach and Marek Cygan and Jakub Lacki and Piotr Sankowski}, | |
| title = {Algorithmic Complexity of Power Law Networks}, | |
| booktitle = proc # {27th} # soda, | |
| pages = {1306--1325}, | |
| year = {2016} | |
| } | |
| @inproceedings{mirrokni2012simultaneous, | |
| author = {Vahab S. Mirrokni and | |
| Shayan Oveis Gharan and | |
| Morteza Zadimoghaddam}, | |
| title = {Simultaneous approximations for adversarial and stochastic online | |
| budgeted allocation}, | |
| booktitle = proc # {23rd} # soda, | |
| pages = {1690--1701}, | |
| year = {2012}, | |
| } | |
| @inproceedings{essfandiari2015online, | |
| author = {Hossein Esfandiari and | |
| Nitish Korula and | |
| Vahab S. Mirrokni}, | |
| title = {Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic | |
| Models}, | |
| booktitle = proc # {16th} # ec, | |
| pages = {169--186}, | |
| year = {2015} | |
| } | |
| @inproceedings{solomon2016fully, | |
| title={Fully dynamic maximal matching in constant update time}, | |
| author={Solomon, Shay}, | |
| booktitle = proc # {57th} # focs, | |
| pages={325--334}, | |
| year={2016} | |
| } | |
| @inproceedings{peleg2016dynamic, | |
| title={Dynamic $(1+ \epsilon)$-approximate matchings: a density-sensitive approach}, | |
| author={Peleg, David and Solomon, Shay}, | |
| booktitle = proc # {27th} # soda, | |
| pages={712--729}, | |
| year={2016} | |
| } | |
| @inproceedings{micali1980v, | |
| title={An ${O}(\sqrt{|{V}|}\cdot|{E}|)$ algoithm for finding maximum matching in general graphs}, | |
| author={Micali, Silvio and Vazirani, Vijay V}, | |
| booktitle = proc # {21st} # focs, | |
| pages={17--27}, | |
| year={1980} | |
| } | |
| @inproceedings{bhattacharya2017fully, | |
| title={Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in ${O} (\log^3 n)$ Worst Case Update Time}, | |
| author={Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon}, | |
| booktitle = proc # {28th} # soda, | |
| pages={470--489}, | |
| year={2017} | |
| } | |
| @article{bhattacharya2017fullyfully, | |
| author = {Sayan Bhattacharya and | |
| Monika Henzinger and | |
| Danupon Nanongkai}, | |
| title = {Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover | |
| in ${O} (\log^3 n)$ Worst Case Update Time}, | |
| journal = {CoRR}, | |
| volume = {abs/1704.02844}, | |
| year = {2017} | |
| } | |
| @inproceedings{bernstein2015fully, | |
| title={Fully Dynamic Matching in Bipartite Graphs}, | |
| author={Bernstein, Aaron and Stein, Cliff}, | |
| booktitle = proc # {42nd} # icalp, | |
| pages={167--179}, | |
| year={2015} | |
| } | |
| @inproceedings{bernstein2016faster, | |
| title={Faster fully dynamic matchings with small approximation ratios}, | |
| author={Bernstein, Aaron and Stein, Cliff}, | |
| booktitle = proc # {27th} # soda, | |
| pages={692--711}, | |
| year={2016} | |
| } | |
| @inproceedings{bhattacharya2017deterministic, | |
| author = {Sayan Bhattacharya and | |
| Deeparnab Chakrabarty and | |
| Monika Henzinger}, | |
| title = {Deterministic Fully Dynamic Approximate Vertex Cover and Fractional | |
| Matching in {$O(1)$} Amortized Update Time}, | |
| booktitle = proc # {19th} # ipco, | |
| pages = {86--98}, | |
| year = {2017} | |
| } | |
| @inproceedings{williams2012multiplying, | |
| title={Multiplying matrices faster than Coppersmith-Winograd}, | |
| author={Williams, Virginia Vassilevska}, | |
| booktitle = proc # {44th} # stoc, | |
| pages={887--898}, | |
| year={2012} | |
| } | |
| @inproceedings{mucha2004maximum, | |
| title={Maximum matchings via Gaussian elimination}, | |
| author={Mucha, Marcin and Sankowski, Piotr}, | |
| booktitle = proc # {45th} # focs, | |
| pages={248--255}, | |
| year={2004} | |
| } | |
| @inproceedings{abboud2014popular, | |
| title={Popular conjectures imply strong lower bounds for dynamic problems}, | |
| author={Abboud, Amir and Williams, Virginia Vassilevska}, | |
| booktitle = proc # {55th} # focs, | |
| pages={434--443}, | |
| year={2014} | |
| } | |
| @inproceedings{abboud2016popular, | |
| title={Popular conjectures as a barrier for dynamic planar graph algorithms}, | |
| author={Abboud, Amir and Dahlgaard, S{\o}ren}, | |
| booktitle = proc # {57th} # focs, | |
| pages={477--486}, | |
| year={2016} | |
| } | |
| @inproceedings{kopelowitz2016higher, | |
| title={Higher lower bounds from the 3SUM conjecture}, | |
| author={Kopelowitz, Tsvi and Pettie, Seth and Porat, Ely}, | |
| booktitle = proc # {27th} # soda, | |
| pages={1272--1287}, | |
| year={2016} | |
| } | |
| @inproceedings{stubbs2017metatheorems, | |
| title={Metatheorems for dynamic weighted matching}, | |
| author={Stubbs, Daniel and Vassilevska Williams, Virginia}, | |
| booktitle = proc # {8th} # itcs, | |
| year={2017} | |
| } | |
| @inproceedings{abraham2017fully, | |
| author = {Abraham, Ittai and Chechik, Shiri and Krinninger, Sebastian}, | |
| title = {Fully Dynamic All-pairs Shortest Paths with Worst-case Update-time Revisited}, | |
| booktitle = proc # {28th} # soda, | |
| year = {2017}, | |
| pages = {440--452}, | |
| } | |
| @inproceedings{abraham2016dynamic, | |
| author = {Abraham, Ittai and Chechik, Shiri and Delling, Daniel and Goldberg, Andrew V. and Werneck, Renato F.}, | |
| title = {On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-case Costs}, | |
| booktitle = proc # {27th} # soda, | |
| year = {2016}, | |
| pages = {740--753}, | |
| } | |
| @inproceedings{grandoni2012improved, | |
| author = {Grandoni, Fabrizio and Williams, Virginia Vassilevska}, | |
| title = {Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths}, | |
| booktitle = proc # {53rd} # focs, | |
| year = {2012}, | |
| pages = {748--757}, | |
| } | |
| @inproceedings{charikar2018fully, | |
| title={Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds}, | |
| author={Charikar, Moses and Solomon, Shay}, | |
| booktitle = proc # {45th} # icalp, | |
| year={2018} | |
| } | |
| @article{arar2017dynamic, | |
| title={Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}, | |
| author={Arar, Moab and Chechik, Shiri and Cohen, Sarel and Stein, Cliff and Wajc, David}, | |
| journal={arXiv preprint arXiv:1711.06625}, | |
| year={2017} | |
| } | |
| @article{edmonds1972theoretical, | |
| title={Theoretical improvements in algorithmic efficiency for network flow problems}, | |
| author={Edmonds, Jack and Karp, Richard M}, | |
| journal=jacm, | |
| volume={19}, | |
| number={2}, | |
| pages={248--264}, | |
| year={1972} | |
| } | |
| @article{fredman1987fibonacci, | |
| title={Fibonacci heaps and their uses in improved network optimization algorithms}, | |
| author={Fredman, Michael L and Tarjan, Robert Endre}, | |
| journal=jacm, | |
| volume={34}, | |
| number={3}, | |
| pages={596--615}, | |
| year={1987} | |
| } | |
| @inproceedings{gabow1990data, | |
| title={Data structures for weighted matching and nearest common ancestors with linking}, | |
| author={Gabow, Harold N}, | |
| booktitle = proc # {1st} # soda, | |
| pages={434--443}, | |
| year={1990} | |
| } | |
| @article{pettie2012simple, | |
| title={A simple reduction from maximum weight matching to maximum cardinality matching}, | |
| author={Pettie, Seth}, | |
| journal={Information Processing Letters (IPL)}, | |
| volume={112}, | |
| number={23}, | |
| pages={893--898}, | |
| year={2012}, | |
| } | |
| @article{gabow1989faster, | |
| title={Faster scaling algorithms for network problems}, | |
| author={Gabow, Harold N and Tarjan, Robert E}, | |
| journal=sicomp, | |
| volume={18}, | |
| number={5}, | |
| pages={1013--1036}, | |
| year={1989} | |
| } | |
| @article{sankowski2009maximum, | |
| title={Maximum weight bipartite matching in matrix multiplication time}, | |
| author={Sankowski, Piotr}, | |
| journal={Theoretical Computer Science (TCS)}, | |
| volume={410}, | |
| number={44}, | |
| pages={4480--4488}, | |
| year={2009} | |
| } | |
| @inproceedings{cohen2017negative, | |
| title={Negative-weight shortest paths and unit capacity minimum cost flow in $\tilde{O} (m^{10/7} \log {W})$ time}, | |
| author={Cohen, Michael B and M{\k{a}}dry, Aleksander and Sankowski, Piotr and Vladu, Adrian}, | |
| booktitle = proc # {28th} # soda, | |
| pages={752--771}, | |
| year={2017} | |
| } | |
| @article{duan2014linear, | |
| title={Linear-time approximation for maximum weight matching}, | |
| author={Duan, Ran and Pettie, Seth}, | |
| journal=jacm, | |
| volume={61}, | |
| number={1}, | |
| pages={1}, | |
| year={2014} | |
| } | |
| @inproceedings{crouch2014improved, | |
| title={Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching}, | |
| author={Crouch, Michael and Stubbs, Daniel M}, | |
| booktitle = proc # {17th} # approx, | |
| pages={96}, | |
| year={2014} | |
| } | |
| @article{vizing1964estimate, | |
| title={On an estimate of the chromatic class of a p-graph}, | |
| author={Vizing, Vadim G}, | |
| journal={Diskret analiz}, | |
| volume={3}, | |
| pages={25--30}, | |
| year={1964} | |
| } | |
| @article{ausiello1991incremental, | |
| author = {Giorgio Ausiello and | |
| Giuseppe F. Italiano and | |
| Alberto Marchetti-Spaccamela and | |
| Umberto Nanni}, | |
| title = {Incremental Algorithms for Minimal Length Paths}, | |
| journal = {Journal of Algorithms}, | |
| volume = {12}, | |
| number = {4}, | |
| year = {1991}, | |
| pages = {615-638} | |
| } | |
| @inproceedings{king1999fully, | |
| author = {King, Valerie}, | |
| title = {Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs}, | |
| booktitle = proc # {40th} # focs, | |
| year = {1999}, | |
| pages = {81-91}, | |
| } | |
| @article{henzinger2001maintaining, | |
| author = {Monika Rauch Henzinger and | |
| Valerie King}, | |
| title = {Maintaining Minimum Spanning Forests in Dynamic Graphs}, | |
| journal = sicomp, | |
| volume = {31}, | |
| number = {2}, | |
| pages = {364--374}, | |
| year = {2001}, | |
| } | |
| @article{demetrescu2004new, | |
| author = {Camil Demetrescu and | |
| Giuseppe F. Italiano}, | |
| title = {A new approach to dynamic all pairs shortest paths}, | |
| journal = jacm, | |
| volume = {51}, | |
| number = {6}, | |
| year = {2004}, | |
| pages = {968-992}, | |
| } | |
| @article{demetrescu2006fully, | |
| author = {Camil Demetrescu and | |
| Giuseppe F. Italiano}, | |
| title = {Fully dynamic all pairs shortest paths with real edge weights}, | |
| journal={Journal of Computer and System Sciences}, | |
| volume = {72}, | |
| number = {5}, | |
| year = {2006}, | |
| pages = {813-837} | |
| } | |
| @inproceedings{thorup2004fully, | |
| author = {Mikkel Thorup}, | |
| title = {Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing | |
| Negative Cycles}, | |
| booktitle = proc # {9th} # swat, | |
| year = {2004}, | |
| pages = {384-396} | |
| } | |
| @inproceedings{thorup2005worst, | |
| author = {Thorup, Mikkel}, | |
| title = {Worst-case Update Times for Fully-dynamic All-pairs Shortest Paths}, | |
| booktitle = proc # {37th} # stoc, | |
| year = {2005}, | |
| pages = {112--119} | |
| } | |
| @article{baswana2007improved, | |
| author = {Surender Baswana and | |
| Ramesh Hariharan and | |
| Sandeep Sen}, | |
| title = {Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths}, | |
| journal = {Journal of Algorithms}, | |
| volume = {62}, | |
| number = {2}, | |
| year = {2007}, | |
| pages = {74--92}, | |
| } | |
| @inproceedings{henzinger2013dynamic, | |
| author = {Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, | |
| title = {Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization}, | |
| booktitle = proc # {54th} # focs, | |
| year = {2013}, | |
| pages = {538--547} | |
| } | |
| @article{abraham2013dynamic, | |
| author = {Ittai Abraham and | |
| Shiri Chechik}, | |
| title = {Dynamic Decremental Approximate Distance Oracles with $(1+\epsilon,2)$ stretch}, | |
| journal = {CoRR}, | |
| volume = {abs/1307.1516}, | |
| year = {2013}, | |
| } | |
| @inproceedings{henzinger2014subquadratic, | |
| author = {Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, | |
| title = {A Subquadratic-time Algorithm for Decremental Single-source Shortest Paths}, | |
| booktitle = proc # {25th} # soda, | |
| year = {2014}, | |
| pages = {1053--1072} | |
| } | |
| @inproceedings{henzinger2014decremental, | |
| author = {Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, | |
| title = {Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time}, | |
| booktitle = proc # {55th} # focs, | |
| year = {2014}, | |
| pages = {146--155}, | |
| } | |
| @inproceedings{henzinger2014sublinear, | |
| author = {Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, | |
| title = {Sublinear-time Decremental Algorithms for Single-source Reachability and Shortest Paths on Directed Graphs}, | |
| booktitle = proc # {46th} # stoc, | |
| year = {2014}, | |
| pages = {674--683} | |
| } | |
| @inproceedings{henzinger2015improved, | |
| author = {Monika Henzinger and | |
| Sebastian Krinninger and | |
| Danupon Nanongkai}, | |
| title = {Improved Algorithms for Decremental Single-Source Reachability on | |
| Directed Graphs}, | |
| booktitle = proc # {42nd} # icalp, | |
| pages = {725--736}, | |
| year = {2015} | |
| } | |
| @article{thorup2007fully, | |
| author = {Thorup, Mikkel}, | |
| title = {Fully-Dynamic Min-Cut}, | |
| journal = {Combinatorica}, | |
| volume = {27}, | |
| number = {1}, | |
| pages = {91--127}, | |
| year = 2007 | |
| } | |
| @inproceedings{karger1994random, | |
| author = {Karger, David R.}, | |
| title = {Random Sampling in Cut, Flow, and Network Design Problems}, | |
| booktitle = proc # {26th} # stoc, | |
| pages = {648--657}, | |
| year = 1994 | |
| } | |
| @inproceedings{haeupler2007beating, | |
| author = {Haeupler, Bernhard and Li, Jason}, | |
| title = {Beating $\mathcal{O}(\sqrt{n} + D)$ for Distributed Shortest Path Approximations via Shortcuts}, | |
| } | |
| @book{hochbaum1996approximation, | |
| title={Approximation algorithms for NP-hard problems}, | |
| author={Hochbaum, Dorit S}, | |
| year={1996}, | |
| publisher={PWS Publishing Co.} | |
| } | |
| @incollection{coffman2013bin, | |
| title={Bin packing approximation algorithms: survey and classification}, | |
| author={Coffman Jr, Edward G and Csirik, J{\'a}nos and Galambos, G{\'a}bor and Martello, Silvano and Vigo, Daniele}, | |
| booktitle={Handbook of Combinatorial Optimization}, | |
| pages={455--531}, | |
| year={2013} | |
| } | |
| @article{de1981bin, | |
| title={Bin packing can be solved within 1+ $\varepsilon$ in linear time}, | |
| author={De La Vega, W Fernandez and Lueker, George S.}, | |
| journal={Combinatorica}, | |
| volume={1}, | |
| number={4}, | |
| pages={349--355}, | |
| year={1981} | |
| } | |
| @inproceedings{karmarkar1982efficient, | |
| title={An efficient approximation scheme for the one-dimensional bin-packing problem}, | |
| author={Karmarkar, Narendra and Karp, Richard M}, | |
| journal=proc # {23rd} # focs, | |
| pages={312--320}, | |
| year={1982} | |
| } | |
| @article{rothvoss2016better, | |
| title={Better Bin Packing Approximations via Discrepancy Theory}, | |
| author={Rothvoss, Thomas}, | |
| journal=sicomp, | |
| volume={45}, | |
| number={3}, | |
| pages={930--946}, | |
| year={2016} | |
| } | |
| @inproceedings{hoberg2017logarithmic, | |
| title={A logarithmic additive integrality gap for bin packing}, | |
| author={Hoberg, Rebecca and Rothvoss, Thomas}, | |
| journal=proc # {28th} # soda, | |
| pages={2616--2625}, | |
| year={2017}, | |
| organization={SIAM} | |
| } | |
| @article{berndt2015fully, | |
| title={Fully Dynamic Bin Packing Revisited}, | |
| author={Berndt, Sebastian and Jansen, Klaus and Klein, Kim-Manuel}, | |
| journal=proc # {18th} # approx, | |
| volume={33}, | |
| pages={135--151}, | |
| year={2015} | |
| } | |
| @inproceedings{jansen2013robust, | |
| title={A robust AFPTAS for online bin packing with polynomial migration}, | |
| author={Jansen, Klaus and Klein, Kim-Manuel}, | |
| booktitle = proc # {40th} # icalp, | |
| pages={589--600}, | |
| year={2013} | |
| } | |
| @article{epstein2009robust, | |
| title={A robust APTAS for the classical bin packing problem}, | |
| author={Epstein, Leah and Levin, Asaf}, | |
| journal={Mathematical programming}, | |
| volume={119}, | |
| number={1}, | |
| pages={33--49}, | |
| year={2009} | |
| } | |
| @inproceedings{gambosi1990new, | |
| title={New algorithms for on-line bin packing}, | |
| author={Gambosi, Giorgio and Postiglione, Alberto and Talamo, Maurizio}, | |
| booktitle={Algorithms and Complexity, Proceedings of the First Italian Conference}, | |
| pages={44--59}, | |
| year={1990} | |
| } | |
| @article{gambosi2000algorithms, | |
| title={Algorithms for the relaxed online bin-packing model}, | |
| author={Gambosi, Giorgio and Postiglione, Alberto and Talamo, Maurizio}, | |
| journal=sicomp, | |
| volume={30}, | |
| number={5}, | |
| pages={1532--1551}, | |
| year={2000} | |
| } | |
| @article{ivkovic1998fully, | |
| title={Fully dynamic algorithms for bin packing: Being (mostly) myopic helps}, | |
| author={Ivkovic, Zoran and Lloyd, Errol L}, | |
| journal=sicomp, | |
| volume={28}, | |
| number={2}, | |
| pages={574--611}, | |
| year={1998} | |
| } | |
| @article{sanders2009online, | |
| title={Online scheduling with bounded migration}, | |
| author={Sanders, Peter and Sivadasan, Naveen and Skutella, Martin}, | |
| journal={Mathematics of Operations Research}, | |
| volume={34}, | |
| number={2}, | |
| pages={481--498}, | |
| year={2009} | |
| } | |
| @article{lee1985simple, | |
| title={A simple on-line bin-packing algorithm}, | |
| author={Lee, Chan C and Lee, Der-Tsai}, | |
| journal=jacm, | |
| volume={32}, | |
| number={3}, | |
| pages={562--572}, | |
| year={1985} | |
| } | |
| @article{sylvester1880point, | |
| title={On a point in the theory of vulgar fractions}, | |
| author={Sylvester, James J}, | |
| journal={American Journal of Mathematics}, | |
| volume={3}, | |
| number={4}, | |
| pages={332--335}, | |
| year={1880} | |
| } | |
| %%%%%%%%%%%%%%%%%% ONLINE BIN PACKING %%%%%%%%%%%%%%%% | |
| @book{ullman1971performance, | |
| title={The performance of a memory allocation algorithm}, | |
| author={Ullman, JD}, | |
| year={1971} | |
| } | |
| @article{johnson1974worst, | |
| title={Worst-case performance bounds for simple one-dimensional packing algorithms}, | |
| author={Johnson, David S. and Demers, Alan and Ullman, Jeffrey D. and Garey, Michael R and Graham, Ronald L.}, | |
| journal=sicomp, | |
| volume={3}, | |
| number={4}, | |
| pages={299--325}, | |
| year={1974} | |
| } | |
| @article{yao1980new, | |
| title={New algorithms for bin packing}, | |
| author={Yao, Andrew Chi-Chih}, | |
| journal=jacm, | |
| volume={27}, | |
| number={2}, | |
| pages={207--227}, | |
| year={1980} | |
| } | |
| @article{woeginger1993improved, | |
| title={Improved space for bounded-space, on-line bin-packing}, | |
| author={Woeginger, Gerhard}, | |
| journal={SIAM Journal on Discrete Mathematics}, | |
| volume={6}, | |
| number={4}, | |
| pages={575--581}, | |
| year={1993} | |
| } | |
| @article{ramanan1989line, | |
| title={On-line bin packing in linear time}, | |
| author={Ramanan, Prakash and Brown, Donna J and Lee, Chung-Chieh and Lee, Der-Tsai}, | |
| journal={Journal of Algorithms}, | |
| volume={10}, | |
| number={3}, | |
| pages={305--326}, | |
| year={1989} | |
| } | |
| @book{van1995lower, | |
| title={Lower and Upper Bounds for On-line Bin Packing and Scheduling Heuristics: Onder-en Bovengrenzen Voor On-line Bin Packing en Scheduling Heuristieken}, | |
| author={van Vliet, Andr{\'e}}, | |
| year={1995}, | |
| publisher={Thesis Publ.} | |
| } | |
| @article{balogh2012new, | |
| title={New lower bounds for certain classes of bin packing algorithms}, | |
| author={Balogh, J{\'a}nos and B{\'e}k{\'e}si, J{\'o}zsef and Galambos, G{\'a}bor}, | |
| journal={Theoretical Computer Science (TCS)}, | |
| volume={440}, | |
| pages={1--13}, | |
| year={2012} | |
| } | |
| @article{richey1991improved, | |
| title={Improved bounds for harmonic-based bin packing algorithms}, | |
| author={Richey, Michael B}, | |
| journal={Discrete Applied Mathematics}, | |
| volume={34}, | |
| number={1-3}, | |
| pages={203--227}, | |
| year={1991} | |
| } | |
| @article{seiden2002online, | |
| title={On the online bin packing problem}, | |
| author={Seiden, Steven S}, | |
| journal=jacm, | |
| volume={49}, | |
| number={5}, | |
| pages={640--671}, | |
| year={2002} | |
| } | |
| @inproceedings{heydrich2016beating, | |
| title={Beating the Harmonic Lower Bound for Online Bin Packing}, | |
| author={Heydrich, Sandy and van Stee, Rob}, | |
| booktitle = proc # {43rd} # icalp, | |
| year={2016}, | |
| pages = {41:1--41:14}, | |
| } | |
| @article{balogh2014line, | |
| title={On-line bin packing with restricted repacking}, | |
| author={Balogh, J{\'a}nos and B{\'e}k{\'e}si, J{\'o}zsef and Galambos, G{\'a}bor and Reinelt, Gerhard}, | |
| journal={Journal of Combinatorial Optimization}, | |
| volume={27}, | |
| number={1}, | |
| pages={115--131}, | |
| year={2014} | |
| } | |
| @article{balogh2008lower, | |
| title={Lower bound for the online bin packing problem with restricted repacking}, | |
| author={Balogh, J{\'a}nos and B{\'e}k{\'e}si, J{\'o}zsef and Galambos, G{\'a}bor and Reinelt, Gerhard}, | |
| journal=sicomp, | |
| volume={38}, | |
| number={1}, | |
| pages={398--410}, | |
| year={2008} | |
| } | |
| @article{ivkovic1996fundamental, | |
| title={A fundamental restriction on fully dynamic maintenance of bin packing}, | |
| author={Ivkovi{\'c}, Zoran and Lloyd, Errol L}, | |
| journal={Information Processing Letters (IPL)}, | |
| volume={59}, | |
| number={4}, | |
| pages={229--232}, | |
| year={1996} | |
| } | |
| @article{sanders2009online, | |
| title={Online scheduling with bounded migration}, | |
| author={Sanders, Peter and Sivadasan, Naveen and Skutella, Martin}, | |
| journal={Mathematics of Operations Research}, | |
| volume={34}, | |
| number={2}, | |
| pages={481--498}, | |
| year={2009}, | |
| publisher={INFORMS} | |
| } | |
| @inproceedings{skutella2010robust, | |
| title={A robust PTAS for machine covering and packing}, | |
| author={Skutella, Martin and Verschae, Jos{\'e}}, | |
| booktitle = proc # {18th} # esa, | |
| pages={36--47}, | |
| year={2010} | |
| } | |
| @article{epstein2014robust, | |
| title={Robust algorithms for preemptive scheduling}, | |
| author={Epstein, Leah and Levin, Asaf}, | |
| journal={Algorithmica}, | |
| volume={69}, | |
| number={1}, | |
| pages={26--57}, | |
| year={2014} | |
| } | |
| @inproceedings{albers2012value, | |
| title={On the value of job migration in online makespan minimization}, | |
| author={Albers, Susanne and Hellwig, Matthias}, | |
| booktitle = proc # {20th} # esa, | |
| pages={84--95}, | |
| year={2012} | |
| } | |
| @article{ivkovic1997partially, | |
| title={Partially dynamic bin packing can be solved within 1+ $\varepsilon$ in (amortized) polylogarithmic time}, | |
| author={Ivkovi{\'c}, Zoran and Lloyd, Errol L}, | |
| journal={Information processing letters}, | |
| volume={63}, | |
| number={1}, | |
| pages={45--50}, | |
| year={1997} | |
| } | |
| @article{corless1996lambertw, | |
| title={On the {L}ambert-{$W$} function}, | |
| author={Corless, Robert M and Gonnet, Gaston H and Hare, D EG and Jeffrey, David J and Knuth, Donald E}, | |
| journal={Advances in Computational mathematics}, | |
| volume={5}, | |
| number={1}, | |
| pages={329--359}, | |
| year={1996} | |
| } | |
| @article{balogh2017new, | |
| title={A new and improved algorithm for online bin packing}, | |
| author={Balogh, J{\'a}nos and B{\'e}k{\'e}si, J{\'o}zsef and D{\'o}sa, Gy{\"o}rgy and Epstein, Leah and Levin, Asaf}, | |
| journal={arXiv preprint arXiv:1707.01728}, | |
| year={2017} | |
| } | |
| @article{feldkord2017tight, | |
| title={A Tight Approximation for Fully Dynamic Bin Packing without Bundling}, | |
| author={Feldkord, Bj\"orn and Feldotto, Matthias and Riechers S\"oren}, | |
| journal={arXiv preprint arXiv:1711.01231}, | |
| year={2017} | |
| } | |
| @inproceedings{miller2013parallel, | |
| title={Parallel graph decompositions using random shifts}, | |
| author={Miller, Gary L and Peng, Richard and Xu, Shen Chen}, | |
| booktitle = proc # {25th} # spaa, | |
| pages={196--203}, | |
| year={2013} | |
| } | |
| @article{awerbuch1985complexity, | |
| title={Complexity of network synchronization}, | |
| author={Awerbuch, Baruch}, | |
| journal=jacm, | |
| volume={32}, | |
| number={4}, | |
| pages={804--823}, | |
| year={1985} | |
| } | |
| @inproceedings{bartal1996probabilistic, | |
| title={Probabilistic approximation of metric spaces and its algorithmic applications}, | |
| author={Bartal, Yair}, | |
| booktitle = proc # {37th} # focs, | |
| pages={184--193}, | |
| year={1996} | |
| } | |
| @article{cohen1998fast, | |
| title={Fast algorithms for constructing t-spanners and paths with stretch t}, | |
| author={Cohen, Edith}, | |
| journal=sicomp, | |
| volume={28}, | |
| number={1}, | |
| pages={210--236}, | |
| year={1998} | |
| } | |
| @article{linial1993low, | |
| title={Low diameter graph decompositions}, | |
| author={Linial, Nathan and Saks, Michael}, | |
| journal={Combinatorica}, | |
| volume={13}, | |
| number={4}, | |
| pages={441--454}, | |
| year={1993} | |
| } | |
| @inproceedings{awerbuch1992low, | |
| title={Low-diameter graph decomposition is in NC}, | |
| author={Awerbuch, Baruch and Berger, Bonnie and Cowen, Lenore and Peleg, David}, | |
| booktitle = proc # {3rd} # swat, | |
| pages={83--93}, | |
| year={1992} | |
| } | |
| @article{awerbuch1996fast, | |
| title={Fast distributed network decompositions and covers}, | |
| author={Awerbuch, Baruch and Berger, Bonnie and Cowen, Lenore and Peleg, David}, | |
| journal={Journal of Parallel and Distributed Computing}, | |
| volume={39}, | |
| number={2}, | |
| pages={105--114}, | |
| year={1996} | |
| } | |
| @inproceedings{klein1993excluded, | |
| title={Excluded minors, network decomposition, and multicommodity flow}, | |
| author={Klein, Philip and Plotkin, Serge A and Rao, Satish}, | |
| booktitle = proc # {25th} # stoc, | |
| pages={682--690}, | |
| year={1993} | |
| } | |
| @inproceedings{fakcharoenphol2003tight, | |
| title={A tight bound on approximating arbitrary metrics by tree metrics}, | |
| author={Fakcharoenphol, Jittat and Rao, Satish and Talwar, Kunal}, | |
| booktitle = proc # {35th} # stoc, | |
| pages={448--455}, | |
| year={2003} | |
| } | |
| @article{blelloch2014nearly, | |
| title={Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs}, | |
| author={Blelloch, Guy E and Gupta, Anupam and Koutis, Ioannis and Miller, Gary L and Peng, Richard and Tangwongsan, Kanat}, | |
| journal={Theory of Computing Systems}, | |
| volume={55}, | |
| number={3}, | |
| pages={521--554}, | |
| year={2014} | |
| } | |
| @inproceedings{azar2017polylogarithmic, | |
| title={Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays}, | |
| author={Azar, Yossi and Chiplunkar, Ashish and Kaplan, Haim}, | |
| booktitle = proc # {28th} # soda, | |
| pages={1051--1061}, | |
| year={2017} | |
| } | |
| @inproceedings{awerbuch1990sparse, | |
| title={Sparse partitions}, | |
| author={Awerbuch, Baruch and Peleg, David}, | |
| booktitle = proc # {31st} # focs, | |
| pages={503--513}, | |
| year={1990} | |
| } | |
| @article{even2000divide, | |
| title={Divide-and-conquer approximation algorithms via spreading metrics}, | |
| author={Even, Guy and Naor, Joseph Seffi and Rao, Satish and Schieber, Baruch}, | |
| journal=jacm, | |
| volume={47}, | |
| number={4}, | |
| pages={585--616}, | |
| year={2000} | |
| } | |
| @inproceedings{charikar1998approximating, | |
| title={Approximating a finite metric by a small number of tree metrics}, | |
| author={Charikar, Moses and Chekuri, Chandra and Goel, Ashish and Guha, Sudipto and Plotkin, Serge}, | |
| booktitle = proc # {39th} # focs, | |
| pages={379--388}, | |
| year={1998} | |
| } | |
| @inproceedings{daitch2008faster, | |
| title={Faster approximate lossy generalized flow via interior point algorithms}, | |
| author={Daitch, Samuel I and Spielman, Daniel A}, | |
| booktitle = proc # {40th} # stoc, | |
| pages={451--460}, | |
| year={2008} | |
| } | |
| @inproceedings{madry2013navigating, | |
| title={Navigating central path with electrical flows: From flows to matchings, and back}, | |
| author={Madry, Aleksander}, | |
| booktitle = proc # {54th} # focs, | |
| pages={253--262}, | |
| year={2013} | |
| } | |
| @inproceedings{christiano2011electrical, | |
| title={Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs}, | |
| author={Christiano, Paul and Kelner, Jonathan A and Madry, Aleksander and Spielman, Daniel A and Teng, Shang-Hua}, | |
| booktitle = proc # {43rd} # stoc, | |
| pages={273--282}, | |
| year={2011} | |
| } | |
| @inproceedings{abraham2014cops, | |
| title={Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs}, | |
| author={Abraham, Ittai and Gavoille, Cyril and Gupta, Anupam and Neiman, Ofer and Talwar, Kunal}, | |
| booktitle = proc # {46th} # stoc, | |
| pages={79--88}, | |
| year={2014} | |
| } | |
| @incollection{fakcharoenphol2003improved, | |
| title={An improved decomposition theorem for graphs excluding a fixed minor}, | |
| author={Fakcharoenphol, Jittat and Talwar, Kunal}, | |
| booktitle = proc # {6th} # approx, | |
| pages={36--46}, | |
| year={2003} | |
| } | |
| @inproceedings{abraham2007strong, | |
| title={Strong-diameter decompositions of minor free graphs}, | |
| author={Abraham, Ittai and Gavoille, Cyril and Malkhi, Dahlia and Wieder, Udi}, | |
| booktitle = proc # {19th} # spaa, | |
| pages={16--24}, | |
| year={2007} | |
| } | |
| @inproceedings{indyk2007probabilistic, | |
| title={Probabilistic embeddings of bounded genus graphs into planar graphs}, | |
| author={Indyk, Piotr and Sidiropoulos, Anastasios}, | |
| booktitle = proc # {23rd} # socg, | |
| booktitle={Proceedings of the twenty-third annual symposium on Computational geometry}, | |
| pages={204--209}, | |
| year={2007} | |
| } | |
| @inproceedings{lee2010genus, | |
| title={Genus and the geometry of the cut graph:[extended abstract]}, | |
| author={Lee, James R and Sidiropoulos, Anastasios}, | |
| booktitle = proc # {21st} # soda, | |
| pages={193--201}, | |
| year={2010} | |
| } | |
| @article{borradaile2010randomly, | |
| title={Randomly removing g handles at once}, | |
| author={Borradaile, Glencora and Lee, James R and Sidiropoulos, Anastasios}, | |
| journal={Computational Geometry}, | |
| volume={43}, | |
| number={8}, | |
| pages={655--662}, | |
| year={2010} | |
| } | |
| @inproceedings{sidiropoulos2010optimal, | |
| title={Optimal stochastic planarization}, | |
| author={Sidiropoulos, Anastasios}, | |
| booktitle = proc # {51st} # focs, | |
| pages={163--170}, | |
| year={2010} | |
| } | |
| @inproceedings{awerbuch1997buy, | |
| title={Buy-at-bulk network design}, | |
| author={Awerbuch, Baruch and Azar, Yossi}, | |
| booktitle = proc # {38th} # focs, | |
| pages={542--547}, | |
| year={1997} | |
| } | |
| @article{ford1956maximal, | |
| title={Maximal flow through a network}, | |
| author={Ford, Lester R. and Fulkerson, Delbert R.}, | |
| journal={Canadian journal of Mathematics}, | |
| volume={8}, | |
| number={3}, | |
| pages={399--404}, | |
| year={1956} | |
| } | |
| @incollection{dantzig1956max, | |
| author = {Dantzig, George and Fulkerson, Delbert R.}, | |
| title = {On the Max-Flow Min-Cut Theorem of Networks}, | |
| editor = {Kuhn, Harold W. and Tucker, Albert W.}, | |
| booktitle = {Linear inequalities and related systems}, | |
| publisher = {Princeton university press}, | |
| year = {1956}, | |
| pages = {215--223}, | |
| chapter = {12} | |
| } | |
| @article{elias1956note, | |
| title={A note on the maximum flow through a network}, | |
| author={Elias, Peter and Feinstein, Amiel and Shannon, Claude}, | |
| journal={IRE Transactions on Information Theory}, | |
| volume={2}, | |
| number={4}, | |
| pages={117--119}, | |
| year={1956} | |
| } | |
| @article{leighton1999multicommodity, | |
| title={Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms}, | |
| author={Leighton, Tom and Rao, Satish}, | |
| journal= jacm, | |
| volume={46}, | |
| number={6}, | |
| pages={787--832}, | |
| year={1999} | |
| } | |
| @inproceedings{leighton1988approximate, | |
| title={An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms}, | |
| author={Leighton, Tom and Rao, Satish}, | |
| booktitle = proc # {29th} # focs, | |
| pages={422--431}, | |
| year={1988} | |
| } | |
| @article{klein1997approximation, | |
| title={Approximation algorithms for Steiner and directed multicuts}, | |
| author={Klein, Philip N and Plotkin, Serge A and Rao, Satish and Tardos, Eva}, | |
| journal={Journal of Algorithms}, | |
| volume={22}, | |
| number={2}, | |
| pages={241--269}, | |
| year={1997}, | |
| } | |
| @article{klein1994faster, | |
| title={Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts}, | |
| author={Klein, Philip and Plotkin, Serge and Stein, Clifford and Tardos, Eva}, | |
| journal=sicomp, | |
| volume={23}, | |
| number={3}, | |
| pages={466--487}, | |
| year={1994}, | |
| } | |
| @article{klein1995approximate, | |
| title={An approximate max-flow min-cut relation for undirected multicommodity flow, with applications}, | |
| author={Klein, Philip and Rao, Satish and Agrawal, Ajit and Ravi, R}, | |
| journal={Combinatorica}, | |
| volume={15}, | |
| number={2}, | |
| pages={187--202}, | |
| year={1995}, | |
| } | |
| @article{plotkin1995improved, | |
| title={Improved bounds on the max-flow min-cut ratio for multicommodity flows}, | |
| author={Plotkin, Serge and Tardos, {\'E}va}, | |
| journal={Combinatorica}, | |
| volume={15}, | |
| number={3}, | |
| pages={425--434}, | |
| year={1995}, | |
| } | |
| @article{garg1996approximate, | |
| title={Approximate max-flow min-(multi) cut theorems and their applications}, | |
| author={Garg, Naveen and Vazirani, Vijay V and Yannakakis, Mihalis}, | |
| journal=sicomp, | |
| volume={25}, | |
| number={2}, | |
| pages={235--251}, | |
| year={1996}, | |
| } | |
| @article{linial1995geometry, | |
| title={The geometry of graphs and some of its algorithmic applications}, | |
| author={Linial, Nathan and London, Eran and Rabinovich, Yuri}, | |
| journal={Combinatorica}, | |
| volume={15}, | |
| number={2}, | |
| pages={215--245}, | |
| year={1995}, | |
| } | |
| @article{aumann1998log, | |
| title={An O (log k) approximate min-cut max-flow theorem and approximation algorithm}, | |
| author={Aumann, Yonatan and Rabani, Yuval}, | |
| journal=sicomp, | |
| volume={27}, | |
| number={1}, | |
| pages={291--301}, | |
| year={1998} | |
| } | |
| @phdthesis{tragoudas1990vlsi, | |
| title={VLSI partitioning approximation algorithms based on multicommodity flow and other techniques}, | |
| author={Tragoudas, Spyros}, | |
| year={1990}, | |
| school={University of Texas at Dallas} | |
| } | |
| @article{even1998approximating, | |
| title={Approximating minimum feedback sets and multicuts in directed graphs}, | |
| author={Even, Guy and Naor, J Seffi and Schieber, Baruch and Sudan, Madhu}, | |
| journal={Algorithmica}, | |
| volume={20}, | |
| number={2}, | |
| pages={151--174}, | |
| year={1998} | |
| } | |
| @article{chuzhoy2009polynomial, | |
| title={Polynomial flow-cut gaps and hardness of directed cut problems}, | |
| author={Chuzhoy, Julia and Khanna, Sanjeev}, | |
| journal=jacm, | |
| volume={56}, | |
| number={2}, | |
| pages={6}, | |
| year={2009} | |
| } | |
| @inproceedings{cheriyan2001approximating, | |
| title={Approximating directed multicuts}, | |
| author={Cheriyan, Joseph and Karloff, Howard and Rabani, Yuval}, | |
| booktitle = proc # {42nd} # focs, | |
| pages={320--328}, | |
| year={2001} | |
| } | |
| @inproceedings{gupta2003improved, | |
| title={Improved Results for Directed Multicut}, | |
| author={Gupta, Anupam}, | |
| booktitle = proc # {14th} # soda, | |
| pages={454}, | |
| year={2003} | |
| } | |
| @article{kortsarts2005greedy, | |
| title={Greedy approximation algorithms for directed multicuts}, | |
| author={Kortsarts, Yana and Kortsarz, Guy and Nutov, Zeev}, | |
| journal={Networks}, | |
| volume={45}, | |
| number={4}, | |
| pages={214--217}, | |
| year={2005} | |
| } | |
| @inproceedings{agarwal2007improved, | |
| title={Improved approximation for directed cut problems}, | |
| author={Agarwal, Amit and Alon, Noga and Charikar, Moses S}, | |
| booktitle = proc # {39th} # stoc, | |
| pages={671--680}, | |
| year={2007} | |
| } | |
| @inproceedings{cohen2018randomized, | |
| title={Randomized Online Matching in Regular Graphs}, | |
| author={Cohen, Ilan Reuven and Wajc, David}, | |
| booktitle = proc # {29th} # soda, | |
| pages={960--979}, | |
| year={2018} | |
| } | |
| @inproceedings{arar2018dynamic, | |
| title={Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}, | |
| author={Arar, Moab and Chechik, Shiri and Cohen, Sarel and Stein, Cliff and Wajc, David}, | |
| booktitle = proc # {45th} # icalp, | |
| pages=ta, | |
| year={2018} | |
| } | |
| @inproceedings{feldkord2018fully, | |
| title={Fully-Dynamic Bin Packing with Little Repacking}, | |
| author={Feldkord, Bj\"{o}rn and Feldotto, Matthias and Gupta, Anupam and Guruganesh, Guru and Kumar, Amit and Riechers, S\"{o}ren and Wajc, David}, | |
| booktitle = proc # {45th} # icalp, | |
| pages=ta, | |
| year={2018} | |
| } | |
| @inproceedings{raghvendra2016robust, | |
| author={Raghvendra, Sharath}, | |
| title={A robust and optimal online algorithm for minimum metric bipartite matching}, | |
| booktitle = proc # {19th} # approx, | |
| volume={60}, | |
| year={2016}, | |
| page={18:1–18:16} | |
| } | |
| @article{khuller1994line, | |
| author={Khuller, Samir and Mitchell, Stephen G and Vazirani, Vijay V}, | |
| title={On-line algorithms for weighted bipartite matching and stable marriages}, | |
| journal={Theoretical Computer Science (TCS)}, | |
| volume={127}, | |
| number={2}, | |
| pages={255--267}, | |
| year={1994} | |
| } | |
| @article{kalyanasundaram1993online, | |
| title={Online weighted matching}, | |
| author={Kalyanasundaram, Bala and Pruhs, Kirk}, | |
| journal={Journal of Algorithms}, | |
| volume={14}, | |
| number={3}, | |
| pages={478--488}, | |
| year={1993} | |
| } | |
| @inproceedings{meyerson2006randomized, | |
| author={Meyerson, Adam and Nanavati, Akash and Poplawski, Laura}, | |
| title={Randomized online algorithms for minimum metric bipartite matching}, | |
| booktitle = proc # {17th} # soda, | |
| pages={954--959}, | |
| year={2006} | |
| } | |
| @article{berend2013sharp, | |
| title={A sharp estimate of the binomial mean absolute deviation with applications}, | |
| author={Berend, Daniel and Kontorovich, Aryeh}, | |
| journal={Statistics \& Probability Letters}, | |
| volume={83}, | |
| number={4}, | |
| pages={1254--1259}, | |
| year={2013} | |
| } | |
| @article{blyth1980expected, | |
| title={Expected absolute error of the usual estimator of the binomial parameter}, | |
| author={Blyth, Colin R}, | |
| journal={The American Statistician}, | |
| volume={34}, | |
| number={3}, | |
| pages={155--157}, | |
| year={1980}, | |
| publisher={Taylor \& Francis} | |
| } | |
| @inproceedings{nayyar2017input, | |
| title={An input sensitive online algorithm for the metric bipartite matching problem}, | |
| author={Nayyar, Krati and Raghvendra, Sharath}, | |
| booktitle = proc # {58th} # focs, | |
| pages={505--515}, | |
| year={2017} | |
| } | |
| @inproceedings{gupta2012online, | |
| title={The online metric matching problem for doubling metrics}, | |
| author={Gupta, Anupam and Lewi, Kevin}, | |
| booktitle = proc # {39th} # icalp, | |
| pages={424--435}, | |
| year={2012} | |
| } | |
| @inproceedings{koutsoupias2003online, | |
| title={The online matching problem on a line}, | |
| author={Koutsoupias, Elias and Nanavati, Akash}, | |
| booktitle = proc # {1st} # waoa, | |
| pages={179--191}, | |
| year={2003} | |
| } | |
| @inproceedings{antoniadis2014n, | |
| title={A $o (n)$-Competitive Deterministic Algorithm for Online Matching on a Line}, | |
| author={Antoniadis, Antonios and Barcelo, Neal and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele}, | |
| booktitle = proc # {12th} # waoa, | |
| pages={11--22}, | |
| year={2014} | |
| } | |
| @inproceedings{bansal2007log, | |
| title={An ${O}(log^2 k)$-competitive algorithm for metric bipartite matching}, | |
| author={Bansal, Nikhil and Buchbinder, Niv and Gupta, Anupam and Naor, Joseph Seffi}, | |
| booktitle = proc # {15th} # esa, pages={522--533}, | |
| year={2007} | |
| } | |
| @article{chang2018dispatch, | |
| title={DISPATCH: An Optimal Algorithm for Online Perfect Bipartite Matching with iid Arrivals}, | |
| author={Chang, Minjun and Hochbaum, Dorit S and Spaen, Quico and Velednitsky, Mark}, | |
| journal={arXiv preprint arXiv:1805.02014}, | |
| year={2018} | |
| } | |
| @article{fuchs2005online, | |
| title={Online matching on a line}, | |
| author={Fuchs, Bernhard and Hochst{\"a}ttler, Winfried and Kern, Walter}, | |
| journal={Theoretical Computer Science (TCS)}, | |
| volume={332}, | |
| number={1-3}, | |
| pages={251--264}, | |
| year={2005} | |
| } | |
| @article{bar1992greedy, | |
| title={The greedy algorithm is optimal for on-line edge coloring}, | |
| author={Bar-Noy, Amotz and Motwani, Rajeev and Naor, Joseph}, | |
| journal={Information Processing Letters (IPL)}, | |
| volume={44}, | |
| number={5}, | |
| pages={251--253}, | |
| year={1992} | |
| } | |
| @article{bahmani2012online, | |
| title={Online Graph Edge-Coloring in the Random-Order Arrival Model.}, | |
| author={Bahmani, Bahman and Mehta, Aranyak and Motwani, Rajeev}, | |
| journal={Theory of Computing}, | |
| volume={8}, | |
| number={1}, | |
| pages={567--595}, | |
| year={2012} | |
| } | |
| @inproceedings{aggarwal2003switch, | |
| title={Switch scheduling via randomized edge coloring}, | |
| author={Aggarwal, Gagan and Motwani, Rajeev and Shah, Devavrat and Zhu, An}, | |
| booktitle=proc # {44th} # focs, | |
| pages={502--512}, | |
| year={2003} | |
| } | |
| @article{shannon1949theorem, | |
| title={A theorem on coloring the lines of a network}, | |
| author={Shannon, Claude E}, | |
| journal={Journal of Mathematics and Physics}, | |
| volume={28}, | |
| number={1-4}, | |
| pages={148--152}, | |
| year={1949} | |
| } | |
| @article{holyer1981np, | |
| title={The NP-completeness of edge-coloring}, | |
| author={Holyer, Ian}, | |
| journal=sicomp, | |
| volume={10}, | |
| number={4}, | |
| pages={718--720}, | |
| year={1981} | |
| } | |
| @article{gabow1976using, | |
| title={Using Euler partitions to edge color bipartite multigraphs}, | |
| author={Gabow, Harold N.}, | |
| journal={International Journal of Computer \& Information Sciences}, | |
| volume={5}, | |
| number={4}, | |
| pages={345--355}, | |
| year={1976} | |
| } | |
| @inproceedings{misra1992constructive, | |
| title={A constructive proof of Vizing’s theorem}, | |
| author={Misra, Jayadev and Gries, David}, | |
| booktitle={Information Processing Letters (IPL)}, | |
| year={1992} | |
| } | |
| @article{berger1991simulating, | |
| title={Simulating $(\log^cn)$-wise independence in NC}, | |
| author={Berger, Bonnie and Rompel, John}, | |
| journal=jacm, | |
| volume={38}, | |
| number={4}, | |
| pages={1026--1046}, | |
| year={1991} | |
| } | |
| @article{motwani1994probabilistic, | |
| title={The probabilistic method yields deterministic parallel algorithms}, | |
| author={Motwani, Rajeev and Naor, Joseph Seffi and Naor, Moni}, | |
| journal={Journal of Computer and System Sciences}, | |
| volume={49}, | |
| number={3}, | |
| pages={478--516}, | |
| year={1994} | |
| } | |
| @inproceedings{panconesi1992improved, | |
| title={Improved distributed algorithms for coloring and network decomposition problems}, | |
| author={Panconesi, Alessandro and Srinivasan, Aravind}, | |
| booktitle={Proceedings of the twenty-fourth annual ACM symposium on Theory of computing}, | |
| pages={581--592}, | |
| year={1992}, | |
| organization={ACM} | |
| } | |
| @article{lev1981fast, | |
| title={A fast parallel algorithm for routing in permutation networks}, | |
| author={Lev, Gavriela Freund and Pippenger, Nicholas and Valiant, Leslie G}, | |
| journal={IEEE transactions on Computers}, | |
| number={2}, | |
| pages={93--100}, | |
| year={1981} | |
| } | |
| @article{karloff1987efficient, | |
| title={Efficient parallel algorithms for edge coloring problems}, | |
| author={Karloff, Howard J. and Shmoys, David B.}, | |
| journal={J. Algorithms}, | |
| volume={8}, | |
| number={1}, | |
| pages={39--52}, | |
| year={1987} | |
| } | |
| @inproceedings{huang2018match, | |
| title={How to match when all vertices arrive online}, | |
| author={Huang, Zhiyi and Kang, Ning and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao and Zhu, Xue}, | |
| booktitle=proc # {50th} # stoc, | |
| pages={17--29}, | |
| year={2018} | |
| } | |
| @inproceedings{huang2018online, | |
| author={Zhiyi Huang and Zhihao Gavin Tang and Xiaowei Wu and Yuhao Zhang}, | |
| title={Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random | |
| Arrivals}, | |
| booktitle = proc # {45th} # icalp, | |
| pages={1070--1081}, | |
| year=2018 | |
| } | |
| @inproceedings{azar2016packing, | |
| title={Packing small vectors}, | |
| author={Azar, Yossi and Cohen, Ilan Reuven and Fiat, Amos and Roytman, Alan}, | |
| booktitle=proc # {27th} # soda, | |
| pages={1511--1525}, | |
| year={2016} | |
| } | |
| @article{tassiulas1992stability, | |
| title={Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks}, | |
| author={Tassiulas, Leandros and Ephremides, Anthony}, | |
| journal={IEEE transactions on automatic control}, | |
| volume={37}, | |
| number={12}, | |
| pages={1936--1948}, | |
| year={1992} | |
| } | |
| @article{rasala2005strictly, | |
| title={Strictly nonblocking WDM cross-connects}, | |
| author={Rasala, April and Wilfong, Gordon}, | |
| journal=sicomp, | |
| volume={35}, | |
| number={2}, | |
| pages={449--485}, | |
| year={2005} | |
| } | |
| @article{gandham2008link, | |
| title={Link scheduling in wireless sensor networks: Distributed edge-coloring revisited}, | |
| author={Gandham, Shashidhar and Dawande, Milind and Prakash, Ravi}, | |
| journal={Journal of Parallel and Distributed Computing}, | |
| volume={68}, | |
| number={8}, | |
| pages={1122--1134}, | |
| year={2008} | |
| } | |
| @article{leighton1994packet, | |
| title={Packet routing and job-shop scheduling in ${O}$(congestion+ dilation) steps}, | |
| author={Leighton, Frank Thomson and Maggs, Bruce M and Rao, Satish B}, | |
| journal={Combinatorica}, | |
| volume={14}, | |
| number={2}, | |
| pages={167--186}, | |
| year={1994} | |
| } | |
| @article{carr2002randomized, | |
| title={Randomized metarounding}, | |
| author={Carr, Robert and Vempala, Santosh}, | |
| journal={Random Structures \& Algorithms}, | |
| volume={20}, | |
| number={3}, | |
| pages={343--352}, | |
| year={2002} | |
| } | |
| @inproceedings{miller2015improved, | |
| title={Improved parallel algorithms for spanners and hopsets}, | |
| author={Miller, Gary L and Peng, Richard and Vladu, Adrian and Xu, Shen Chen}, | |
| booktitle=proc # {27th} # spaa, | |
| pages={192--201}, | |
| year={2015} | |
| } | |
| @inproceedings{gupta2003bounded, | |
| title={Bounded geometries, fractals, and low-distortion embeddings}, | |
| author={Gupta, Anupam and Krauthgamer, Robert and Lee, James R}, | |
| booktitle=proc # {44th} # focs, | |
| pages={534}, | |
| year={2003} | |
| } | |
| @inproceedings{lovett2014linear, | |
| title={Linear codes cannot approximate the network capacity within any constant factor.}, | |
| author={Lovett, Shachar}, | |
| booktitle={Electronic Colloquium on Computational Complexity (ECCC)}, | |
| volume={21}, | |
| pages={141}, | |
| year={2014} | |
| } | |
| @inproceedings{farhadi2019lower, | |
| title={Lower Bounds for External Memory Integer Sorting via Network Coding}, | |
| author={Farhadi, Alireza and Hajiaghayi, MohammadTaghi and Larsen, Kasper Green and Shi, Elaine}, | |
| booktitle = proc # {51st} # stoc, | |
| year={2019}, | |
| pages=ta, | |
| } | |
| @inproceedings{afshani2019lower, | |
| title={Lower Bounds for Multiplication via Network Coding}, | |
| author={Afshani, Peyman and Freksen, Casper Benjamin and Kamma, Lior and Larsen, Kasper Green}, | |
| booktitle = proc # {46th} # icalp, | |
| pages={10:1--10:12}, | |
| year={2019} | |
| } | |
| @article{okamura1981multicommodity, | |
| title={Multicommodity flows in planar graphs}, | |
| author={Okamura, Haruko and Seymour, Paul D}, | |
| journal={Journal of Combinatorial Theory, Series B}, | |
| volume={31}, | |
| number={1}, | |
| pages={75--81}, | |
| year={1981} | |
| } | |
| @article{hu1963multi, | |
| title={Multi-commodity network flows}, | |
| author={Hu, T Chiang}, | |
| journal={Operations research}, | |
| volume={11}, | |
| number={3}, | |
| pages={344--360}, | |
| year={1963} | |
| } | |
| @article{harvey2019polynomial, | |
| title={Polynomial multiplication over finite fields in time ${O} (n \log n)$}, | |
| author={Harvey, David and Van Der Hoeven, Joris}, | |
| year={2019}, | |
| journal={HAL preprint hal-02070816} | |
| } | |
| @inproceedings{becker2016near, | |
| title={Near-optimal approximate shortest paths and transshipment in distributed and streaming models}, | |
| author={Becker, Ruben and Karrenbauer, Andreas and Krinninger, Sebastian and Lenzen, Christoph}, | |
| booktitle=proc # {31st} # disc, | |
| year={2016} | |
| } | |
| @inproceedings{ghaffari2015near, | |
| title={Near-optimal distributed maximum flow}, | |
| author={Ghaffari, Mohsen and Karrenbauer, Andreas and Kuhn, Fabian and Lenzen, Christoph and Patt-Shamir, Boaz}, | |
| booktitle=proc # {34th} # podc, | |
| pages={81--90}, | |
| year={2015}, | |
| organization={ACM} | |
| } | |
| @inproceedings{haeupler2018minor, | |
| title={Minor excluded network families admit fast distributed algorithms}, | |
| author={Haeupler, Bernhard and Li, Jason and Zuzic, Goran}, | |
| booktitle=proc # {37th} # podc, | |
| pages={465--474}, | |
| year={2018}, | |
| organization={ACM} | |
| } | |
| @inproceedings{racke2009survey, | |
| title={Survey on oblivious routing strategies}, | |
| author={R{\"a}cke, Harald}, | |
| booktitle={5th} # cie, | |
| pages={419--429}, | |
| year={2009}, | |
| organization={Springer} | |
| } | |
| @inproceedings{haeupler2019network, | |
| title={Network Coding Gaps for Completion Times of Multiple Unicasts}, | |
| author={Haeupler, Bernhard and Wajc, David and Zuzic, Goran}, | |
| booktitle=proc # {61st} # focs, | |
| year={2020} | |
| } | |
| @inproceedings{censor2017broadcasting, | |
| title={Broadcasting in Noisy Radio Networks}, | |
| author={Censor-Hillel, Keren and Haeupler, Bernhard and Hershkowitz, D Ellis and Zuzic, Goran}, | |
| booktitle=proc # {36th} # podc, | |
| pages={33--42}, | |
| year={2017}, | |
| organization={ACM} | |
| } | |
| @inproceedings{censor2018erasure, | |
| title={Erasure Correction for Noisy Radio Networks}, | |
| author={Censor-Hillel, Keren and Haeupler, Bernhard and Hershkowitz, D Ellis and Zuzic, Goran}, | |
| booktitle=proc # {34th} # disc, | |
| year={2019} | |
| } | |
| @inproceedings{bradac2019robust, | |
| title={Robust Algorithms for the Secretary Problem}, | |
| author={Bradac, Domagoj and Gupta, Anupam and Singla, Sahil and Zuzic, Goran}, | |
| booktitle=proc # {11th} # itcs, | |
| year={2020} | |
| } | |
| @inproceedings{bradac2019near, | |
| title={Near Optimal Adaptivity Gaps for Stochastic Multi-Value Probing}, | |
| author={Bradac, Domagoj and Singla, Sahil and Zuzic, Goran}, | |
| booktitle=proc # {23rd} # random, | |
| year={2019} | |
| } | |
| @inproceedings{alon2014broadcast, | |
| title={Broadcast throughput in radio networks: routing vs. network coding}, | |
| author={Alon, Noga and Ghaffari, Mohsen and Haeupler, Bernhard and Khabbazian, Majid}, | |
| booktitle=proc # {25th} # soda, | |
| pages={1831--1843}, | |
| year={2014}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{efremenko2019noisy, | |
| title={Radio Network Coding Requires Logarithmic Overhead}, | |
| author={Efremenko, Klim and Kol, Gillat and Saxena, Raghuvansh}, | |
| booktitle=proc # {60th} # focs, | |
| year={2019} | |
| } | |
| @inproceedings{gasieniec2005faster, | |
| title={Faster communication in known topology radio networks}, | |
| author={Gasieniec, Leszek and Peleg, David and Xin, Qin}, | |
| booktitle=proc # {24th} # podc, | |
| pages={129--137}, | |
| year={2005}, | |
| organization={ACM} | |
| } | |
| @inproceedings{razborov1990distributional, | |
| title={On the distributional complexity of disjointness}, | |
| author={Razborov, Alexander A}, | |
| booktitle=proc # {17th} # icalp, | |
| pages={249--253}, | |
| year={1990}, | |
| organization={Springer} | |
| } | |
| @inproceedings{ghaffari2016one, | |
| title={Distributed algorithms for planar networks I: Planar embedding}, | |
| author={Ghaffari, Mohsen and Haeupler, Bernhard}, | |
| booktitle=proc # {35th} # podc, | |
| pages={29--38}, | |
| year={2016} | |
| } | |
| @inproceedings{haeupler2018round, | |
| title={Round-and message-optimal distributed graph algorithms}, | |
| author={Haeupler, Bernhard and Hershkowitz, D Ellis and Wajc, David}, | |
| booktitle=proc # {37th} # podc, | |
| pages={119--128}, | |
| year={2018} | |
| } | |
| @InProceedings{haeupler2018faster, | |
| author = {Bernhard Haeupler and Jason Li}, | |
| title = {{Faster Distributed Shortest Path Approximations via Shortcuts}}, | |
| booktitle = proc # {32nd} # disc, | |
| pages = {33:1--33:14}, | |
| year = {2018}, | |
| } | |
| @InProceedings{ghaffari2018new, | |
| author = {Mohsen Ghaffari and Jason Li}, | |
| title = {{New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms}}, | |
| booktitle = proc # {32nd} # disc, | |
| pages = {31:1--31:16}, | |
| year = {2018}, | |
| } | |
| @inproceedings{lenzen2013fast, | |
| title={Fast routing table construction using small messages}, | |
| author={Lenzen, Christoph and Patt-Shamir, Boaz}, | |
| booktitle=proc # {45th} # stoc, | |
| pages={381--390}, | |
| year={2013} | |
| } | |
| @inproceedings{eppstein2003dynamic, | |
| title={Dynamic generators of topologically embedded graphs}, | |
| author={Eppstein, David}, | |
| booktitle=proc # {14th} # soda, | |
| pages={599--608}, | |
| year={2003}, | |
| organization={Society for Industrial and Applied Mathematics} | |
| } | |
| @article{gruber2010balanced, | |
| title={On balanced separators, treewidth, and cycle rank}, | |
| author={Gruber, Hermann}, | |
| journal={arXiv preprint arXiv:1012.1344}, | |
| year={2010} | |
| } | |
| @inproceedings{lenzen2008can, | |
| title={What can be approximated locally? Case study: Dominating sets in planar graphs}, | |
| author={Lenzen, Christoph and Oswald, Yvonne Anne and Wattenhofer, Roger}, | |
| booktitle=proc # {20th} # spaa, | |
| pages={46--54}, | |
| year={2008} | |
| } | |
| @inproceedings{kuhn2005local, | |
| title={Local approximation schemes for ad hoc and sensor networks}, | |
| author={Kuhn, Fabian and Nieberg, Tim and Moscibroda, Thomas and Wattenhofer, Rogert}, | |
| booktitle=proc # {1st} # fomc, | |
| pages={97--103}, | |
| year={2005} | |
| } | |
| @article{bodlaender1998parallel, | |
| title={Parallel algorithms with optimal speedup for bounded treewidth}, | |
| author={Bodlaender, Hans L and Hagerup, Torben}, | |
| journal=sicomp, | |
| volume={27}, | |
| number={6}, | |
| pages={1725--1746}, | |
| year={1998}, | |
| } | |
| @book{white2012hadoop, | |
| title={Hadoop: The definitive guide}, | |
| author={White, Tom}, | |
| year={2012}, | |
| publisher={" O'Reilly Media, Inc."} | |
| } | |
| @article{zaharia2010spark, | |
| title={Spark: Cluster computing with working sets.}, | |
| author={Zaharia, Matei and Chowdhury, Mosharaf and Franklin, Michael J and Shenker, Scott and Stoica, Ion}, | |
| journal={HotCloud}, | |
| volume={10}, | |
| number={10-10}, | |
| pages={95}, | |
| year={2010} | |
| } | |
| @article{kannan2013multi, | |
| title={Multi-session function computation and multicasting in undirected graphs}, | |
| author={Kannan, Sreeram and Viswanath, Pramod}, | |
| journal={IEEE Journal on Selected Areas in Communications}, | |
| volume={31}, | |
| number={4}, | |
| pages={702--713}, | |
| year={2013}, | |
| publisher={IEEE} | |
| } | |
| @inproceedings{awerbuch1987optimal, | |
| title={Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems}, | |
| author={Awerbuch, Baruch}, | |
| booktitle=proc # {19th} # stoc, | |
| pages={230--240}, | |
| year={1987} | |
| } | |
| @inproceedings{henzinger2016almost, | |
| title={An almost-tight distributed algorithm for computing single-source shortest paths}, | |
| author={Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, | |
| booktitle=proc # {48th} # stoc, | |
| year={2016} | |
| } | |
| @inproceedings{elkin2017distributed, | |
| title={Distributed exact shortest paths in sublinear time}, | |
| author={Elkin, Michael}, | |
| booktitle=proc # {49th} # stoc, | |
| pages={757--770}, | |
| year={2017} | |
| } | |
| @inproceedings{huang2017distributed, | |
| title={Distributed Exact Weighted All-Pairs Shortest Paths in {\~O} (n\^{}$\{$5/4$\}$) Rounds}, | |
| author={Huang, Chien-Chung and Nanongkai, Danupon and Saranurak, Thatchaphol}, | |
| booktitle=proc # {58th} # focs, | |
| pages={168--179}, | |
| year={2017}, | |
| organization={IEEE} | |
| } | |
| @inproceedings{king2015construction, | |
| title={Construction and impromptu repair of an MST in a distributed network with o (m) communication}, | |
| author={King, Valerie and Kutten, Shay and Thorup, Mikkel}, | |
| booktitle=proc # {34th} # podc, | |
| pages={71--80}, | |
| year={2015} | |
| } | |
| @InProceedings{gmyr2018, | |
| author = {Robert Gmyr and Gopal Pandurangan}, | |
| title = {{Time-Message Trade-Offs in Distributed Algorithms}}, | |
| booktitle = proc # {32nd} # disc, | |
| pages = {32:1--32:18}, | |
| year = {2018}, | |
| volume = {121} | |
| } | |
| @inproceedings{li2004network, | |
| title={Network coding: The case of multiple unicast sessions}, | |
| author={Li, Zongpeng and Li, Baochun}, | |
| booktitle=proc # {40th} # allerton, | |
| volume={16}, | |
| pages={8}, | |
| year={2004} | |
| } | |
| @article{ACLY, | |
| title={Network information flow}, | |
| author={Ahlswede, Rudolf and Cai, Ning and Li, S-YR and Yeung, Raymond W}, | |
| journal=isit, | |
| volume={46}, | |
| number={4}, | |
| pages={1204--1216}, | |
| year={2000} | |
| } | |
| @inproceedings{blasiak2011lexicographic, | |
| title={Lexicographic products and the power of non-linear network coding}, | |
| author={Blasiak, Anna and Kleinberg, Robert and Lubetzky, Eyal}, | |
| booktitle=proc # {52nd} # focs, | |
| pages={609--618}, | |
| year={2011} | |
| } | |
| @inproceedings{alon1990separator1, | |
| title={A separator theorem for graphs with an excluded minor and its applications}, | |
| author={Alon, Noga and Seymour, Paul and Thomas, Robin}, | |
| booktitle= proc # {22nd} # stoc, | |
| pages={293--299}, | |
| year={1990}, | |
| } | |
| @article{alon1990separator2, | |
| title={A separator theorem for nonplanar graphs}, | |
| author={Alon, Noga and Seymour, Paul and Thomas, Robin}, | |
| journal={Journal of the American Mathematical Society}, | |
| volume={3}, | |
| number={4}, | |
| pages={801--808}, | |
| year={1990} | |
| } | |
| @InProceedings{ghaffari2017near, | |
| author = {Mohsen Ghaffari and Merav Parter}, | |
| title = {{Near-Optimal Distributed DFS in Planar Graphs}}, | |
| booktitle = proc # {31st} # disc, | |
| pages = {21:1--21:16}, | |
| year = {2017}, | |
| } | |
| @inproceedings{rothvoss2013simpler, | |
| title={A Simpler Proof for ${O} ({C}ongestion + {D}ilation)$ Packet Routing}, | |
| author={Rothvo{\ss}, Thomas}, | |
| booktitle=proc # {16th} # ipco, | |
| pages={336--348}, | |
| year={2013} | |
| } | |
| @inproceedings{peis2011universal, | |
| title={Universal packet routing with arbitrary bandwidths and transit times}, | |
| author={Peis, Britta and Wiese, Andreas}, | |
| booktitle = proc # {13th} # ipco, | |
| pages={362--375}, | |
| year={2011} | |
| } | |
| @article{srinivasan2001constant, | |
| title={A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria}, | |
| author={Srinivasan, Aravind and Teo, Chung-Piaw}, | |
| journal=sicomp, | |
| volume={30}, | |
| number={6}, | |
| pages={2051--2068}, | |
| year={2001}, | |
| publisher={SIAM} | |
| } | |
| @article{bertsimas1999asymptotically, | |
| title={Asymptotically optimal algorithms for job shop scheduling and packet routing}, | |
| author={Bertsimas, Dimitris and Gamarnik, David}, | |
| journal={Journal of Algorithms}, | |
| volume={33}, | |
| number={2}, | |
| pages={296--318}, | |
| year={1999}, | |
| publisher={Elsevier} | |
| } | |
| @incollection{koch2009real, | |
| title={Real-time message routing and scheduling}, | |
| author={Koch, Ronald and Peis, Britta and Skutella, Martin and Wiese, Andreas}, | |
| booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques}, | |
| pages={217--230}, | |
| year={2009}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{busch2004direct, | |
| title={Direct routing: Algorithms and complexity}, | |
| author={Busch, Costas and Magdon-Ismail, Malik and Mavronicolas, Marios and Spirakis, Paul}, | |
| booktitle = proc # {12th} # esa, | |
| pages={134--145}, | |
| year={2004} | |
| } | |
| @inproceedings{peis2009packet, | |
| title={Packet routing: Complexity and algorithms}, | |
| author={Peis, Britta and Skutella, Martin and Wiese, Andreas}, | |
| booktitle=proc # {7th} # waoa, | |
| pages={217--228}, | |
| year={2009} | |
| } | |
| @inproceedings{rabani1996distributed, | |
| title={Distributed packet switching in arbitrary networks}, | |
| author={Rabani, Yuval and Tardos, {\'E}va}, | |
| booktitle = proc # {28th} # stoc, | |
| volume={96}, | |
| pages={366--375}, | |
| year={1996} | |
| } | |
| @inproceedings{ostrovsky1997universal, | |
| title={Universal ${O} (congestion+ dilation+ \log^{1+\epsilon}N)$ Local Control Packet Switching Algorithms}, | |
| author={Ostrovsky, Rafail and Rabani, Yuval}, | |
| booktitle = proc # {29th} # stoc, | |
| volume={29}, | |
| pages={644--653}, | |
| year={1997} | |
| } | |
| @article{auf1999shortest, | |
| title={Shortest-path routing in arbitrary networks}, | |
| author={auf der Heide, Friedhelm Meyer and V{\"o}cking, Berthold}, | |
| journal={Journal of Algorithms}, | |
| volume={31}, | |
| number={1}, | |
| pages={105--131}, | |
| year={1999} | |
| } | |
| @article{leighton1999fast, | |
| title={Fast algorithms for finding O (congestion+ dilation) packet routing schedules}, | |
| author={Leighton, Tom and Maggs, Bruce and Richa, Andrea W}, | |
| journal={Combinatorica}, | |
| volume={19}, | |
| number={3}, | |
| pages={375--401}, | |
| year={1999} | |
| } | |
| @book{scheideler2006universal, | |
| title={Universal routing strategies for interconnection networks}, | |
| author={Scheideler, Christian}, | |
| volume={1390}, | |
| year={2006}, | |
| publisher={Springer} | |
| } | |
| @article{haeupler2015simple, | |
| title={Simple, fast and deterministic gossip and rumor spreading}, | |
| author={Haeupler, Bernhard}, | |
| journal=jacm, | |
| volume={62}, | |
| number={6}, | |
| pages={47}, | |
| year={2015} | |
| } | |
| @article{jain2006capacity, | |
| title={On the capacity of multiple unicast sessions in undirected graphs}, | |
| author={Jain, Kamal and Vazirani, Vijay V and Yeung, Raymond and Yuval, Gideon}, | |
| journal=ton, | |
| volume={14}, | |
| number={SI}, | |
| pages={2805--2809}, | |
| year={2006} | |
| } | |
| @inproceedings{huang2013space, | |
| title={On space information flow: Single multicast}, | |
| author={Huang, Jiaqing and Yin, Xunrui and Zhang, Xiaoxi and Du, Xu and Li, Zongpeng}, | |
| booktitle={2013 International Symposium on Network Coding (NetCod)}, | |
| pages={1--6}, | |
| year={2013}, | |
| organization={IEEE} | |
| } | |
| @article{arora2009expander, | |
| title={Expander flows, geometric embeddings and graph partitioning}, | |
| author={Arora, Sanjeev and Rao, Satish and Vazirani, Umesh}, | |
| journal={Journal of the ACM (JACM)}, | |
| volume={56}, | |
| number={2}, | |
| pages={5}, | |
| year={2009}, | |
| publisher={ACM} | |
| } | |
| @article{kramer2006edge, | |
| title={Edge-cut bounds on network coding rates}, | |
| author={Kramer, Gerhard and Savari, Serap A}, | |
| journal={Journal of Network and Systems Management}, | |
| volume={14}, | |
| number={1}, | |
| pages={49}, | |
| year={2006}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{al2008k, | |
| title={On the k-pairs problem}, | |
| author={Al-Bashabsheh, Ali and Yonga{\c{c}}oglu, Abbas}, | |
| booktitle=proc # isit, | |
| pages={1828--1832}, | |
| year={2008} | |
| } | |
| @article{harvey2006capacity, | |
| title={On the capacity of information networks}, | |
| author={Harvey, Nicholas JA and Kleinberg, Robert and Lehman, April Rasala}, | |
| journal=ton, | |
| volume={14}, | |
| number={SI}, | |
| pages={2345--2364}, | |
| year={2006} | |
| } | |
| @inproceedings{adler2006capacity, | |
| title={On the capacity of information networks}, | |
| author={Adler, Micah and Harvey, Nicholas JA and Jain, Kamal and Kleinberg, Robert and Lehman, April Rasala}, | |
| booktitle={Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm}, | |
| pages={241--250}, | |
| year={2006}, | |
| organization={Society for Industrial and Applied Mathematics} | |
| } | |
| @article{chekuri2013flow, | |
| title={Flow-cut gaps for integer and fractional multiflows}, | |
| author={Chekuri, Chandra and Shepherd, F Bruce and Weibel, Christophe}, | |
| journal={Journal of Combinatorial Theory, Series B}, | |
| volume={103}, | |
| number={2}, | |
| pages={248--273}, | |
| year={2013} | |
| } | |
| @article{deb2006algebraic, | |
| title={Algebraic gossip: A network coding approach to optimal multiple rumor mongering}, | |
| author={Deb, Supratim and M{\'e}dard, Muriel and Choute, Clifford}, | |
| journal={IEEE/ACM Transactions on Networking (TON)}, | |
| volume={14}, | |
| number={SI}, | |
| pages={2486--2507}, | |
| year={2006} | |
| } | |
| @article{fragouli2008efficient, | |
| title={Efficient broadcasting using network coding}, | |
| author={Fragouli, Christina and Widmer, J{\"o}rg and Le Boudec, Jean-Yves}, | |
| journal={IEEE/ACM Transactions on Networking (TON)}, | |
| volume={16}, | |
| number={2}, | |
| pages={450--463}, | |
| year={2008}, | |
| publisher={IEEE Press} | |
| } | |
| @inproceedings{li2004network2, | |
| title={Network coding in undirected networks}, | |
| author={Li, Zongpeng and Li, Baochun}, | |
| year={2004}, | |
| booktitle={Conference on Information Systems and Sciences (CISS)} | |
| } | |
| @article{ahlswede2000network, | |
| title={Network information flow}, | |
| author={Ahlswede, Rudolf and Cai, Ning and Li, S-YR and Yeung, Raymond W}, | |
| journal={IEEE Transactions on Information Theory}, | |
| volume={46}, | |
| number={4}, | |
| pages={1204--1216}, | |
| year={2000} | |
| } | |
| @inproceedings{katti2006xors, | |
| title={XORs in the air: Practical wireless network coding}, | |
| author={Katti, Sachin and Rahul, Hariharan and Hu, Wenjun and Katabi, Dina and M{\'e}dard, Muriel and Crowcroft, Jon}, | |
| booktitle={ACM SIGCOMM computer communication review}, | |
| volume={36}, | |
| pages={243--254}, | |
| year={2006}, | |
| organization={ACM} | |
| } | |
| @inproceedings{jaggi2003low, | |
| title={Low complexity algebraic multicast network codes}, | |
| author={Jaggi, Sidharth and Chou, Philip A. and Jain, Kamal}, | |
| booktitle=proc # isit, | |
| pages={368--368}, | |
| year = {2003} | |
| } | |
| @inproceedings{agarwal2004advantage, | |
| title={On the advantage of network coding for improving network throughput}, | |
| author={Agarwal, Amit and Charikar, Moses}, | |
| booktitle={Information Theory Workshop}, | |
| pages={247--249}, | |
| year={2004} | |
| } | |
| @article{yin2018reduction, | |
| title={A reduction approach to the multiple-unicast conjecture in network coding}, | |
| author={Yin, Xunrui and Li, Zongpeng and Liu, Yaduo and Wang, Xin}, | |
| journal={IEEE Transactions on Information Theory}, | |
| volume={64}, | |
| number={6}, | |
| pages={4530--4539}, | |
| year={2018} | |
| } | |
| @inproceedings{langberg2009multiple, | |
| title={On the multiple unicast network coding, conjecture}, | |
| author={Langberg, Michael and M{\'e}dard, Muriel}, | |
| booktitle={47th Annual Allerton Conference on Communication, Control, and Computing}, | |
| pages={222--227}, | |
| year={2009} | |
| } | |
| @inproceedings{krauthgamer2019flow, | |
| title={Flow-cut gaps and face covers in planar graphs}, | |
| author={Krauthgamer, Robert and Lee, James R and Rika, Havana}, | |
| booktitle=proc # {30th} # soda, | |
| pages={525--534}, | |
| year={2019} | |
| } | |
| @article{ho2006random, | |
| title={A random linear network coding approach to multicast}, | |
| author={Ho, Tracey and M{\'e}dard, Muriel and Koetter, Ralf and Karger, David R and Effros, Michelle and Shi, Jun and Leong, Ben}, | |
| journal={IEEE Transactions on Information Theory}, | |
| volume={52}, | |
| number={10}, | |
| pages={4413--4430}, | |
| year={2006}, | |
| publisher={IEEE} | |
| } | |
| @article{li2009constant, | |
| title={A constant bound on throughput improvement of multicast network coding in undirected networks}, | |
| author={Li, Zongpeng and Li, Baochun and Lau, Lap Chi}, | |
| journal={IEEE Transactions on Information Theory}, | |
| volume={55}, | |
| number={3}, | |
| pages={1016--1026}, | |
| year={2009} | |
| } | |
| @article{haeupler2016analyzing, | |
| title={Analyzing network coding (gossip) made easy}, | |
| author={Haeupler, Bernhard}, | |
| journal=jacm, | |
| volume={63}, | |
| number={3}, | |
| pages={26}, | |
| year={2016} | |
| } | |
| @techreport{harvey2004comparing, | |
| title={Comparing network coding with multicommodity flow for the k-pairs communication problem}, | |
| author={Harvey, Nicholas J and Kleinberg, Robert D and Lehman, April Rasala}, | |
| year={2004}, | |
| institution = {MIT, CSAIL}, | |
| } | |
| @inproceedings{braverman2017coding, | |
| title={Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All}, | |
| author={Braverman, Mark and Garg, Sumegha and Schvartzman, Ariel}, | |
| booktitle = proc # {8th} # itcs, | |
| year={2017}, | |
| pages = {18:1--18:18} | |
| } | |
| @article{xiahou2014geometric, | |
| title={A geometric perspective to multiple-unicast network coding}, | |
| author={Xiahou, Tang and Li, Zongpeng and Wu, Chuan and Huang, Jiaqing}, | |
| journal={IEEE Transactions on Information Theory}, | |
| volume={60}, | |
| number={5}, | |
| pages={2884--2895}, | |
| year={2014} | |
| } | |
| @inproceedings{chekuri2015delay, | |
| title={Delay-constrained unicast and the triangle-cast problem}, | |
| author={Chekuri, Chandra and Kamath, Sudeep and Kannan, Sreeram and Viswanath, Pramod}, | |
| booktitle={2015 IEEE International Symposium on Information Theory (ISIT)}, | |
| pages={804--808}, | |
| year={2015}, | |
| organization={IEEE} | |
| } | |
| @article{abraham2019cops, | |
| title={Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs}, | |
| author={Abraham, Ittai and Gavoille, Cyril and Gupta, Anupam and Neiman, Ofer and Talwar, Kunal}, | |
| journal=sicomp, | |
| volume={48}, | |
| number={3}, | |
| pages={1120--1145}, | |
| year={2019} | |
| } | |
| @inproceedings{goel2008network, | |
| title={On the network coding advantage for wireless multicast in euclidean space}, | |
| author={Goel, Ashish and Khanna, Sanjeev}, | |
| booktitle={Proceedings of the 7th international conference on Information processing in sensor networks}, | |
| pages={64--69}, | |
| year={2008}, | |
| organization={IEEE Computer Society} | |
| } | |
| @article{wang2016sending, | |
| title={Sending perishable information: Coding improves delay-constrained throughput even for single unicast}, | |
| author={Wang, Chih-Chun and Chen, Minghua}, | |
| journal={IEEE Transactions on Information Theory}, | |
| volume={63}, | |
| number={1}, | |
| pages={252--279}, | |
| year={2016}, | |
| publisher={IEEE} | |
| } | |
| @inproceedings{chekuri2005multicommodity, | |
| title={Multicommodity flow, well-linked terminals, and routing problems}, | |
| author={Chekuri, Chandra and Khanna, Sanjeev and Shepherd, F Bruce}, | |
| booktitle=proc # {37th} # stoc, | |
| pages={183--192}, | |
| year={2005} | |
| } | |
| @inproceedings{rao1999small, | |
| title={Small distortion and volume preserving embeddings for planar and Euclidean metrics}, | |
| author={Rao, Satish}, | |
| booktitle=proc # {15th} # socg, | |
| pages={300--306}, | |
| year={1999} | |
| } | |
| @article{chekuri2006embedding, | |
| title={Embedding k-outerplanar graphs into l1}, | |
| author={Chekuri, Chandra and Gupta, Anupam and Newman, Ilan and Rabinovich, Yuri and Sinclair, Alistair}, | |
| journal={SIAM Journal on Discrete Mathematics}, | |
| volume={20}, | |
| number={1}, | |
| pages={119--136}, | |
| year={2006} | |
| } | |
| @inproceedings{zosin2002directed, | |
| title={On directed Steiner trees}, | |
| author={Zosin, Leonid and Khuller, Samir}, | |
| booktitle=proc # {13th} # soda, | |
| pages={59--63}, | |
| year={2002} | |
| } | |
| @article{wu2005minimum, | |
| title={Minimum-energy multicast in mobile ad hoc networks using network coding}, | |
| author={Wu, Yunnan and Chou, Philip A and Kung, Sun-Yuan}, | |
| journal={IEEE Transactions on communications}, | |
| volume={53}, | |
| number={11}, | |
| pages={1906--1918}, | |
| year={2005}, | |
| publisher={IEEE} | |
| } | |
| @article{halperin2007integrality, | |
| title={Integrality ratio for group Steiner trees and directed Steiner trees}, | |
| author={Halperin, Eran and Kortsarz, Guy and Krauthgamer, Robert and Srinivasan, Aravind and Wang, Nan}, | |
| journal=sicomp, | |
| volume={36}, | |
| number={5}, | |
| pages={1494--1511}, | |
| year={2007} | |
| } | |
| @inproceedings{ghaffari2015distributed, | |
| title={Distributed broadcast revisited: Towards universal optimality}, | |
| author={Ghaffari, Mohsen}, | |
| booktitle=proc # {42nd} # icalp, | |
| pages={638--649}, | |
| year={2015}, | |
| organization={Springer} | |
| } | |
| @article{ghaffari2017distributed, | |
| title={Distributed MST and routing in almost mixing time}, | |
| author={Ghaffari, Mohsen and Kuhn, Fabian and Su, Hsin-Hao}, | |
| booktitle=proc # {36th} # podc, | |
| pages={131--140}, | |
| year={2017} | |
| } | |
| @inproceedings{dwork1986knowledge, | |
| title={Knowledge and common knowledge in a Byzantine environment I: crash failures}, | |
| author={Dwork, Cynthia and Moses, Yoram}, | |
| booktitle={Theoretical Aspects of Reasoning about Knowledge}, | |
| pages={149--169}, | |
| year={1986} | |
| } | |
| @article{afshani2017instance, | |
| title={Instance-optimal geometric algorithms}, | |
| author={Afshani, Peyman and Barbay, J{\'e}r{\'e}my and Chan, Timothy M}, | |
| journal=jacm, | |
| volume={64}, | |
| number={1}, | |
| pages={1--38}, | |
| year={2017} | |
| } | |
| @article{ching2015one, | |
| title={One trillion edges: Graph processing at facebook-scale}, | |
| author={Ching, Avery and Edunov, Sergey and Kabiljo, Maja and Logothetis, Dionysios and Muthukrishnan, Sambavi}, | |
| journal={Proceedings of the VLDB Endowment}, | |
| volume={8}, | |
| number={12}, | |
| pages={1804--1815}, | |
| year={2015}, | |
| publisher={VLDB Endowment} | |
| } | |
| @article{valiant2017automatic, | |
| title={An automatic inequality prover and instance optimal identity testing}, | |
| author={Valiant, Gregory and Valiant, Paul}, | |
| journal=sicomp, | |
| volume={46}, | |
| number={1}, | |
| pages={429--455}, | |
| year={2017} | |
| } | |
| @article{lotker2003mst, | |
| title={{MST} construction in ${O}(\log \log n)$ communication rounds}, | |
| author={Lotker, Zvi and Pavlov, Elan and Patt-Shamir, Boaz and Peleg, David}, | |
| journal=sicomp, | |
| volume={35}, | |
| number={1}, | |
| pages={120--131}, | |
| year={2005} | |
| } | |
| @article{han2015giraph, | |
| title={Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems}, | |
| author={Han, Minyang and Daudjee, Khuzaima}, | |
| journal={Proceedings of the VLDB Endowment}, | |
| volume={8}, | |
| number={9}, | |
| pages={950--961}, | |
| year={2015}, | |
| publisher={VLDB Endowment} | |
| } | |
| @article{kutten1998fast, | |
| title={Fast distributed construction of smallk-dominating sets and applications}, | |
| author={Kutten, Shay and Peleg, David}, | |
| journal={Journal of Algorithms}, | |
| volume={28}, | |
| number={1}, | |
| pages={40--66}, | |
| year={1998} | |
| } | |
| @inproceedings{valiant2016instance, | |
| title={Instance optimal learning of discrete distributions}, | |
| author={Valiant, Gregory and Valiant, Paul}, | |
| booktitle=proc # {48th} # stoc, | |
| pages={142--155}, | |
| year={2016} | |
| } | |
| @article{fagin2003optimal, | |
| title={Optimal aggregation algorithms for middleware}, | |
| author={Fagin, Ronald and Lotem, Amnon and Naor, Moni}, | |
| journal={Journal of computer and system sciences}, | |
| volume={66}, | |
| number={4}, | |
| pages={614--656}, | |
| year={2003} | |
| } | |
| @inproceedings{ghaffari2016mst, | |
| title={{MST} in log-star rounds of congested clique}, | |
| author={Ghaffari, Mohsen and Parter, Merav}, | |
| booktitle=proc # {35th} # podc, | |
| pages={19--28}, | |
| year={2016} | |
| } | |
| @inproceedings{kitamura2019low, | |
| title={Low-Congestion Shortcut and Graph Parameters}, | |
| author={Kitamura, Naoki and Kitagawa, Hirotaka and Otachi, Yota and Izumi, Taisuke}, | |
| booktitle=proc # {33rd} # disc, | |
| pages={25:1--25:17}, | |
| year={2019} | |
| } | |
| @inproceedings{jurdzinski2018mst, | |
| title={{MST} in ${O}(1)$ rounds of congested clique}, | |
| author={Jurdzi{\'n}ski, Tomasz and Nowicki, Krzysztof}, | |
| booktitle=proc # {29th} # soda, | |
| pages={2620--2632}, | |
| year={2018} | |
| } | |
| @inproceedings{hegeman2015toward, | |
| title={Toward optimal bounds in the congested clique: Graph connectivity and {MST}}, | |
| author={Hegeman, James W and Pandurangan, Gopal and Pemmaraju, Sriram V and Sardeshmukh, Vivek B and Scquizzato, Michele}, | |
| booktitle=proc # {34th} # podc, | |
| pages={91--100}, | |
| year={2015} | |
| } | |
| @article{lotker2006distributed, | |
| title={Distributed {MST} for constant diameter graphs}, | |
| author={Lotker, Zvi and Patt-Shamir, Boaz and Peleg, David}, | |
| journal={Distributed Computing}, | |
| volume={18}, | |
| number={6}, | |
| pages={453--460}, | |
| year={2006} | |
| } | |
| @article{sleator1985self, | |
| title={Self-adjusting binary search trees}, | |
| author={Sleator, Daniel Dominic and Tarjan, Robert Endre}, | |
| journal=jacm, | |
| volume={32}, | |
| number={3}, | |
| pages={652--686}, | |
| year={1985} | |
| } | |
| @inproceedings{malewicz2010pregel, | |
| title={Pregel: a system for large-scale graph processing}, | |
| author={Malewicz, Grzegorz and Austern, Matthew H and Bik, Aart JC and Dehnert, James C and Horn, Ilan and Leiser, Naty and Czajkowski, Grzegorz}, | |
| booktitle={Proceedings of the 2010 ACM SIGMOD International Conference on Management of data}, | |
| pages={135--146}, | |
| year={2010} | |
| } | |
| @inproceedings{gonzalez2014graphx, | |
| title={Graphx: Graph processing in a distributed dataflow framework}, | |
| author={Gonzalez, Joseph E and Xin, Reynold S and Dave, Ankur and Crankshaw, Daniel and Franklin, Michael J and Stoica, Ion}, | |
| booktitle=proc # {11th} # osdi, | |
| pages={599--613}, | |
| year={2014} | |
| } | |
| @inproceedings{henzinger16almost, | |
| title={An almost-tight distributed algorithm for computing single-source shortest paths}, | |
| author={Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, | |
| booktitle=proc # {48th} # stoc, | |
| year={2016} | |
| } | |
| @article{harel1984fast, | |
| title={Fast algorithms for finding nearest common ancestors}, | |
| author={Harel, Dov and Tarjan, Robert Endre}, | |
| journal=sicomp, | |
| volume={13}, | |
| number={2}, | |
| pages={338--355}, | |
| year={1984}, | |
| publisher={SIAM} | |
| } | |
| @article{devos2004excluding, | |
| title={Excluding any graph as a minor allows a low tree-width 2-coloring}, | |
| author={DeVos, Matt and Ding, Guoli and Oporowski, Bogdan and Sanders, Daniel P and Reed, Bruce and Seymour, Paul and Vertigan, Dirk}, | |
| journal={Journal of Combinatorial Theory, Series B}, | |
| volume={91}, | |
| number={1}, | |
| pages={25--41}, | |
| year={2004}, | |
| publisher={Elsevier} | |
| } | |
| @article{eppstein2000diameter, | |
| title={Diameter and treewidth in minor-closed graph families}, | |
| author={Eppstein, David}, | |
| journal={Algorithmica}, | |
| volume={27}, | |
| number={3}, | |
| pages={275--291}, | |
| year={2000}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{demaine2005algorithmic, | |
| title={Algorithmic graph minor theory: Decomposition, approximation, and coloring}, | |
| author={Demaine, Erik D and Hajiaghayi, Mohammad Taghi and Kawarabayashi, Ken-ichi}, | |
| booktitle=proc # {46th} # focs, | |
| pages={637--646}, | |
| year={2005}, | |
| organization={IEEE} | |
| } | |
| @article{demaine2005subexponential, | |
| title={Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs}, | |
| author={Demaine, Erik D and Fomin, Fedor V and Hajiaghayi, Mohammadtaghi and Thilikos, Dimitrios M}, | |
| journal=jacm, | |
| volume={52}, | |
| number={6}, | |
| pages={866--893}, | |
| year={2005}, | |
| publisher={ACM} | |
| } | |
| @article{dujmovic2017layered, | |
| title={Layered separators in minor-closed graph classes with applications}, | |
| author={Dujmovi{\'c}, Vida and Morin, Pat and Wood, David R}, | |
| journal={Journal of Combinatorial Theory, Series B}, | |
| year={2017}, | |
| publisher={Elsevier} | |
| } | |
| @article{robertson1986graph, | |
| title={Graph minors. V. Excluding a planar graph}, | |
| author={Robertson, Neil and Seymour, Paul D}, | |
| journal={Journal of Combinatorial Theory, Series B}, | |
| volume={41}, | |
| number={1}, | |
| pages={92--114}, | |
| year={1986}, | |
| publisher={Elsevier} | |
| } | |
| @inproceedings{abraham2006object, | |
| title={Object location using path separators}, | |
| author={Abraham, Ittai and Gavoille, Cyril}, | |
| booktitle=proc # {25th} # podc, | |
| pages={188--197}, | |
| year={2006}, | |
| organization={ACM} | |
| } | |
| @article{robertson2003graph, | |
| title={Graph minors. XVI. Excluding a non-planar graph}, | |
| author={Robertson, Neil and Seymour, Paul D}, | |
| journal={Journal of Combinatorial Theory, Series B}, | |
| volume={89}, | |
| number={1}, | |
| pages={43--76}, | |
| year={2003}, | |
| publisher={Elsevier} | |
| } | |
| @article{flocchini2003routing, | |
| title={Routing in series parallel networks}, | |
| author={Flocchini, Paola and Luccio, Flaminia L}, | |
| journal={Theory of Computing Systems}, | |
| volume={36}, | |
| number={2}, | |
| pages={137--157}, | |
| year={2003}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{awerbuch1989randomized, | |
| title={Randomized distributed shortest paths algorithms}, | |
| author={Awerbuch, Baruch}, | |
| booktitle=proc # {21st} # stoc, | |
| pages={490--500}, | |
| year={1989}, | |
| organization={ACM} | |
| } | |
| @article{lovasz2006graph, | |
| title={Graph minor theory}, | |
| author={Lov{\'a}sz, L{\'a}szl{\'o}}, | |
| journal={Bulletin of the American Mathematical Society}, | |
| volume={43}, | |
| number={1}, | |
| pages={75--86}, | |
| year={2006} | |
| } | |
| @inproceedings{kawarabayashi2011simpler, | |
| title={A simpler algorithm and shorter proof for the graph minor decomposition}, | |
| author={Kawarabayashi, Ken-ichi and Wollan, Paul}, | |
| booktitle=proc # {43rd} # stoc, | |
| pages={451--458}, | |
| year={2011}, | |
| organization={ACM} | |
| } | |
| @article{nevsetvril2001otakar, | |
| title={Otakar Boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history}, | |
| author={Ne{\v{s}}et{\v{r}}il, Jaroslav and Milkov{\'a}, Eva and Ne{\v{s}}et{\v{r}}ilov{\'a}, Helena}, | |
| journal={Discrete mathematics}, | |
| volume={233}, | |
| number={1-3}, | |
| pages={3--36}, | |
| year={2001}, | |
| publisher={Elsevier} | |
| } | |
| @article{grohe2003local, | |
| title={Local tree-width, excluded minors, and approximation algorithms}, | |
| author={Grohe, Martin}, | |
| journal={Combinatorica}, | |
| volume={23}, | |
| number={4}, | |
| pages={613--632}, | |
| year={2003}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{bodlaender1988nc, | |
| title={NC-algorithms for graphs with small treewidth}, | |
| author={Bodlaender, Hans L}, | |
| booktitle={International Workshop on Graph-Theoretic Concepts in Computer Science}, | |
| pages={1--10}, | |
| year={1988}, | |
| organization={Springer} | |
| } | |
| @inproceedings{haeupler2020shortcuts, | |
| author={Haeupler, Bernhard and Wajc, David and Zuzic, Goran}, | |
| title={Universally-Optimal Distributed Algorithms for Known Topologies}, | |
| booktitle=proc # {53rd} # stoc, | |
| year={2021}, | |
| organization={ACM} | |
| } | |
| @inproceedings{ghaffari2020hop, | |
| title={Hop-Constrained Oblivious Routing}, | |
| author={Ghaffari, Mohsen and Haeupler, Bernhard and Zuzic, Goran}, | |
| booktitle=proc # {53rd} # stoc, | |
| year={2021}, | |
| organization={ACM} | |
| } | |
| @inproceedings{haeupler2020tree, | |
| title={Tree Embeddings for Hop-Constrained Network Design}, | |
| author={Haeupler, Bernhard and Hershkowitz, D Ellis and Zuzic, Goran}, | |
| booktitle=proc # {53rd} # stoc, | |
| year={2021}, | |
| organization={ACM} | |
| } | |
| @phdthesis{racke2003phd, | |
| title={Data Management and Routing in General Networks}, | |
| author={R{\"a}cke, Harald}, | |
| year={2003}, | |
| school={University of Paderborn} | |
| } | |
| @article{busch2008optimal, | |
| title={Optimal oblivious path selection on the mesh}, | |
| author={Busch, Costas and Magdon-Ismail, Malik and Xi, Jing}, | |
| journal={IEEE Transactions on Computers}, | |
| volume={57}, | |
| number={5}, | |
| pages={660--671}, | |
| year={2008}, | |
| publisher={IEEE} | |
| } | |
| @inproceedings{busch2005oblivious, | |
| title={Oblivious routing on geometric networks}, | |
| author={Busch, Costas and Magdon-Ismail, Malik and Xi, Jing}, | |
| booktitle=proc # {17th} # spaa, | |
| pages={316--324}, | |
| year={2005} | |
| } | |
| @article{ghaffari2020excluding, | |
| title={Low-Congestion Shortcuts for Graphs Excluding Dense Minors}, | |
| author={Ghaffari, Mohsen and Haeupler, Bernhard}, | |
| year={2020} | |
| } | |
| @INPROCEEDINGS(PSC2018-6, | |
| author = "Filip Paveti\'{c} and Ivan Katani\'{c} and Gustav Matula and Goran \v {Z}u\v {z}i\'{c} and Mile \v {S}iki\'{c}", | |
| title = "Fast and Simple Algorithms for Computing both $LCS_k${} and $LCS_{k+}${}", | |
| booktitle = "Proceedings of the Prague Stringology Conference 2018", | |
| address = "Czech Technical University in Prague, Czech Republic", | |
| editor = "Jan Holub and Jan {\v{Z}}{\v{d}}{\'{a}}rek", | |
| isbn = "978-80-01-06484-9", | |
| year = 2018, | |
| pages = "50--62", | |
| ) | |
| @inproceedings{barivsa2014nonlinear, | |
| title={Nonlinear Predictive Control of a Tower Crane Using Reference Shaping Approach}, | |
| author={Bari{\v{s}}a, Tin and Bartulovi{\'c}, Mihovil and {\v{Z}}u{\v{z}}i{\'c}, Goran and Ile{\v{s}}, {\v{S}}andor and Matu{\v{s}}ko, Jadranko and Koloni{\'c}, Fetah}, | |
| booktitle={Power Electronics and Motion Control Conference and Exposition (PEMC), 2014 16th International}, | |
| pages={872--876}, | |
| year={2014}, | |
| organization={IEEE} | |
| } | |
| @book{alon2004probabilistic, | |
| title={The probabilistic method}, | |
| author={Alon, Noga and Spencer, Joel H}, | |
| year={2004}, | |
| publisher={John Wiley \& Sons} | |
| } | |
| @article{forster2020minor, | |
| title={Minor Sparsifiers and the Distributed Laplacian Paradigm}, | |
| author={Forster, Sebastian and Goranci, Gramoz and Liu, Yang P and Peng, Richard and Sun, Xiaorui and Ye, Mingquan}, | |
| journal={arXiv preprint arXiv:2012.15675}, | |
| year={2020} | |
| } | |
| @inproceedings{dory2021distributed, | |
| title={Distributed weighted min-cut in nearly-optimal time}, | |
| author={Dory, Michal and Efron, Yuval and Mukhopadhyay, Sagnik and Nanongkai, Danupon}, | |
| booktitle=proc # {53rd} # stoc, | |
| pages={1144--1153}, | |
| year={2021} | |
| } | |
| @article{censor2020fast, | |
| title={Fast distributed approximation for TAP and 2-edge-connectivity}, | |
| author={Censor-Hillel, Keren and Dory, Michal}, | |
| journal={Distributed Computing}, | |
| volume={33}, | |
| number={2}, | |
| pages={145--168}, | |
| year={2020}, | |
| publisher={Springer} | |
| } | |
| @article{dasgupta1999elementary, | |
| title={An elementary proof of the Johnson-Lindenstrauss lemma}, | |
| author={Dasgupta, Sanjoy and Gupta, Anupam}, | |
| journal={International Computer Science Institute, Technical Report}, | |
| volume={22}, | |
| number={1}, | |
| pages={1--5}, | |
| year={1999}, | |
| publisher={Citeseer} | |
| } | |
| @inproceedings{thorup2006spanners, | |
| title={Spanners and emulators with sublinear distance errors}, | |
| author={Thorup, Mikkel and Zwick, Uri}, | |
| booktitle=proc # {17th} # soda, | |
| pages={802--809}, | |
| year={2006} | |
| } | |
| @inproceedings{lenzen2013optimal, | |
| title={Optimal deterministic routing and sorting on the congested clique}, | |
| author={Lenzen, Christoph}, | |
| booktitle=proc # {32nd} # podc, | |
| pages={42--50}, | |
| year={2013} | |
| } | |
| @inproceedings{indyk2003fast, | |
| title={Fast image retrieval via embeddings}, | |
| author={Indyk, Piotr and Thaper, Nitin}, | |
| booktitle={3rd international workshop on statistical and computational theories of vision}, | |
| volume={2}, | |
| number={3}, | |
| pages={5}, | |
| year={2003} | |
| } | |
| @inproceedings{adil2019iterative, | |
| title={Iterative refinement for $\ell_p$-norm regression}, | |
| author={Adil, Deeksha and Kyng, Rasmus and Peng, Richard and Sachdeva, Sushant}, | |
| booktitle=proc # {30th} # soda, | |
| pages={1405--1424}, | |
| year={2019}, | |
| organization={SIAM} | |
| } | |
| @article{frank1956algorithm, | |
| title={An algorithm for quadratic programming}, | |
| author={Frank, Marguerite and Wolfe, Philip and others}, | |
| journal={Naval research logistics quarterly}, | |
| volume={3}, | |
| number={1-2}, | |
| pages={95--110}, | |
| year={1956}, | |
| publisher={Wiley Subscription Services, Inc., A Wiley Company New York} | |
| } | |
| @inproceedings{ghaffari2017degree, | |
| title={Distributed degree splitting, edge coloring, and orientations}, | |
| author={Ghaffari, Mohsen and Su, Hsin-Hao}, | |
| booktitle=proc # {28th} # soda, | |
| pages={2505--2523}, | |
| year={2017}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{goranci2022universally, | |
| title={Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing}, | |
| author={Zuzic, Goran and Goranci, Goramoz and Ye, Mingquan and Haeupler, Bernhard and Sun, Xiaorui}, | |
| booktitle=proc # {33rd} # soda, | |
| year={2022}, | |
| organization={SIAM} | |
| } | |
| @article{cohen2020wor, | |
| title={WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement}, | |
| author={Cohen, Edith and Pagh, Rasmus and Woodruff, David P}, | |
| journal={arXiv preprint arXiv:2007.06744}, | |
| year={2020} | |
| } | |
| @article{agarwal2013mergeable, | |
| title={Mergeable summaries}, | |
| author={Agarwal, Pankaj K and Cormode, Graham and Huang, Zengfeng and Phillips, Jeff M and Wei, Zhewei and Yi, Ke}, | |
| journal=tods, | |
| volume={38}, | |
| number={4}, | |
| pages={1--28}, | |
| year={2013}, | |
| publisher={ACM New York, NY, USA} | |
| } | |
| @article{baswana2007simple, | |
| title={A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs}, | |
| author={Baswana, Surender and Sen, Sandeep}, | |
| journal={Random Structures \& Algorithms}, | |
| volume={30}, | |
| number={4}, | |
| pages={532--563}, | |
| year={2007}, | |
| publisher={Wiley Online Library} | |
| } | |
| @article{kogan2021low, | |
| title={Low-Congestion Shortcuts in Constant Diameter Graphs}, | |
| author={Kogan, Shimon and Parter, Merav}, | |
| journal={arXiv preprint arXiv:2106.01894}, | |
| year={2021} | |
| } | |
| @article{zuzic2021simple, | |
| title={A Simple Boosting Framework for Transshipment}, | |
| author={Zuzic, Goran}, | |
| journal={arXiv preprint arXiv:2110.11723}, | |
| year={2021} | |
| } | |
| @article{alon1995graph, | |
| title={A graph-theoretic game and its application to the k-server problem}, | |
| author={Alon, Noga and Karp, Richard M and Peleg, David and West, Douglas}, | |
| journal=sicomp, | |
| volume={24}, | |
| number={1}, | |
| pages={78--100}, | |
| year={1995}, | |
| publisher={SIAM} | |
| } | |
| @article{karger2000minimum, | |
| title={Minimum cuts in near-linear time}, | |
| author={Karger, David R}, | |
| journal=jacm, | |
| volume={47}, | |
| number={1}, | |
| pages={46--76}, | |
| year={2000}, | |
| publisher={ACM New York, NY, USA} | |
| } | |
| @InProceedings{gawrychowski_et_al:LIPIcs:2020:12464, | |
| author = {Paweł Gawrychowski and Shay Mozes and Oren Weimann}, | |
| title = {{Minimum Cut in O(m log² n) Time}}, | |
| booktitle = proc # {47th} # icalp, | |
| pages = {57:1--57:15}, | |
| series = {Leibniz International Proceedings in Informatics (LIPIcs)}, | |
| ISBN = {978-3-95977-138-2}, | |
| ISSN = {1868-8969}, | |
| year = {2020}, | |
| volume = {168}, | |
| editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli}, | |
| publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, | |
| address = {Dagstuhl, Germany}, | |
| URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12464}, | |
| URN = {urn:nbn:de:0030-drops-124646}, | |
| doi = {10.4230/LIPIcs.ICALP.2020.57}, | |
| annote = {Keywords: Minimum cut, Minimum 2-respecting cut} | |
| } | |
| @inproceedings{rozhon2022undirected, | |
| title={Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel \& Distributed Algorithms}, | |
| author={Rozhoň, Václav and Grunau, Christoph and Haeupler, Bernhard and Zuzic, Goran and Li, Jason}, | |
| % author="Václav Rozhoň and Christoph Grunau and Bernhard Haeupler and Goran Zuzic and Jason Li", % this is sometimes better if author initial are seen | |
| journal=proc # {54rd} # stoc, | |
| year={2022}, | |
| nameorder={random} | |
| } | |
| @inproceedings{gawrychowski2021note, | |
| title={A note on a recent algorithm for minimum cut}, | |
| author={Gawrychowski, Pawe{\l} and Mozes, Shay and Weimann, Oren}, | |
| booktitle=sosa, | |
| pages={74--79}, | |
| year={2021}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{ghaffari2022universally, | |
| title={Universally-Optimal Distributed Exact Min-Cut}, | |
| author={Ghaffari, Mohsen and Zuzic, Goran}, | |
| journal=proc # {41nd} # podc, | |
| year={2022} | |
| } | |
| @inproceedings{hopexpander2022, | |
| title={Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality}, | |
| author={Haeupler, Bernhard and R\"acke, Harald and Ghaffari, Mohsen}, | |
| booktitle=proc # {54rd} # stoc, | |
| year={2022}, | |
| nameorder={random} | |
| } | |
| @article{chechik2021single, | |
| title={Single-source shortest paths in the CONGEST model with improved bounds}, | |
| author={Chechik, Shiri and Mukhtar, Doron}, | |
| journal={Distributed Computing}, | |
| pages={1--18}, | |
| year={2021}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{andoni2020parallel, | |
| title={Parallel approximate undirected shortest paths via low hop emulators}, | |
| author={Andoni, Alexandr and Stein, Clifford and Zhong, Peilin}, | |
| booktitle={Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing}, | |
| pages={322--335}, | |
| year={2020} | |
| } | |
| @phdthesis{zuzic2020phd, | |
| title={Towards Universal Optimality in Distributed Optimization}, | |
| author={Zuzic, Goran}, | |
| year={2020}, | |
| school={Carnegie Mellon University} | |
| } | |
| @article{haeupler2022adaptive, | |
| title={Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings}, | |
| author={Bernhard Haeupler and D Ellis Hershkowitz and Goran Zuzic}, | |
| journal=proc # {30th} # esa, | |
| year={2022} | |
| } | |
| @article{johnson1977efficient, | |
| title={Efficient algorithms for shortest paths in sparse networks}, | |
| author={Johnson, Donald B}, | |
| journal=jacm, | |
| volume={24}, | |
| number={1}, | |
| pages={1--13}, | |
| year={1977}, | |
| publisher={ACM New York, NY, USA} | |
| } | |
| @inproceedings{abraham2010highway, | |
| title={Highway dimension, shortest paths, and provably efficient algorithms}, | |
| author={Abraham, Ittai and Fiat, Amos and Goldberg, Andrew V and Werneck, Renato F}, | |
| booktitle=proc # {21st} # soda, | |
| pages={782--793}, | |
| year={2010}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{li2020faster, | |
| title={Faster parallel algorithm for approximate shortest path}, | |
| author={Li, Jason}, | |
| booktitle=proc # {52nd} # stoc, | |
| pages={308--321}, | |
| year={2020} | |
| } | |
| @article{cohen2000polylog, | |
| title={Polylog-time and near-linear work approximation scheme for undirected shortest paths}, | |
| author={Cohen, Edith}, | |
| journal=jacm, | |
| volume={47}, | |
| number={1}, | |
| pages={132--166}, | |
| year={2000}, | |
| publisher={ACM New York, NY, USA} | |
| } | |
| @inproceedings{chechik2014approximate, | |
| title={Approximate distance oracles with constant query time}, | |
| author={Chechik, Shiri}, | |
| booktitle=proc # {46th} # stoc, | |
| pages={654--663}, | |
| year={2014} | |
| } | |
| @inproceedings{thorup1992shortcutting, | |
| title={On shortcutting digraphs}, | |
| author={Thorup, Mikkel}, | |
| booktitle={International Workshop on Graph-Theoretic Concepts in Computer Science}, | |
| pages={205--211}, | |
| year={1992}, | |
| organization={Springer} | |
| } | |
| @inproceedings{kogan2022new, | |
| title={New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier}, | |
| author={Kogan, Shimon and Parter, Merav}, | |
| booktitle=proc # {33rd} # soda, | |
| pages={1326--1341}, | |
| year={2022}, | |
| organization={SIAM} | |
| } | |
| @article{huang2021lower, | |
| title={Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts}, | |
| author={Huang, Shang-En and Pettie, Seth}, | |
| journal={SIAM Journal on Discrete Mathematics}, | |
| volume={35}, | |
| number={3}, | |
| pages={2129--2144}, | |
| year={2021}, | |
| publisher={SIAM} | |
| } | |
| @inproceedings{cao2020improved, | |
| title={Improved work span tradeoff for single source reachability and approximate shortest paths}, | |
| author={Cao, Nairen and Fineman, Jeremy T and Russell, Katina}, | |
| booktitle=proc # {32nd} # spaa, | |
| pages={511--513}, | |
| year={2020} | |
| } | |
| @article{klein1997randomized, | |
| title={A randomized parallel algorithm for single-source shortest paths}, | |
| author={Klein, Philip N and Subramanian, Sairam}, | |
| journal={Journal of Algorithms}, | |
| volume={25}, | |
| number={2}, | |
| pages={205--220}, | |
| year={1997}, | |
| publisher={Elsevier} | |
| } | |
| @inproceedings{ghaffari2018improved, | |
| title={Improved distributed algorithms for exact shortest paths}, | |
| author={Ghaffari, Mohsen and Li, Jason}, | |
| booktitle={Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing}, | |
| pages={431--444}, | |
| year={2018} | |
| } | |
| @inproceedings{cao2020efficient, | |
| title={Efficient construction of directed hopsets and parallel approximate shortest paths}, | |
| author={Cao, Nairen and Fineman, Jeremy T and Russell, Katina}, | |
| booktitle={Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing}, | |
| pages={336--349}, | |
| year={2020} | |
| } | |
| @inproceedings{jambulapati2019parallel, | |
| title={Parallel reachability in almost linear work and square root depth}, | |
| author={Jambulapati, Arun and Liu, Yang P and Sidford, Aaron}, | |
| booktitle=proc # {60th} # focs, | |
| pages={1664--1686}, | |
| year={2019}, | |
| organization={IEEE} | |
| } | |
| @inproceedings{fineman2018nearly, | |
| title={Nearly work-efficient parallel algorithm for digraph reachability}, | |
| author={Fineman, Jeremy T}, | |
| booktitle={Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing}, | |
| pages={457--470}, | |
| year={2018} | |
| } | |
| @InProceedings{kogan_et_al:LIPIcs.ICALP.2022.82, | |
| author = {Kogan, Shimon and Parter, Merav}, | |
| title = {{Beating Matrix Multiplication for $n^\{1/3\}$-Directed Shortcuts}}, | |
| booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, | |
| pages = {82:1--82:20}, | |
| series = {Leibniz International Proceedings in Informatics (LIPIcs)}, | |
| ISBN = {978-3-95977-235-8}, | |
| ISSN = {1868-8969}, | |
| year = {2022}, | |
| volume = {229}, | |
| publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, | |
| address = {Dagstuhl, Germany}, | |
| URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16423}, | |
| URN = {urn:nbn:de:0030-drops-164230}, | |
| doi = {10.4230/LIPIcs.ICALP.2022.82}, | |
| annote = {Keywords: Directed Shortcuts, Transitive Closure, Width} | |
| } | |
| @inproceedings{crauser1998parallelization, | |
| title={A parallelization of Dijkstra's shortest path algorithm}, | |
| author={Crauser, Andreas and Mehlhorn, Kurt and Meyer, Ulrich and Sanders, Peter}, | |
| booktitle={International Symposium on Mathematical Foundations of Computer Science}, | |
| pages={722--731}, | |
| year={1998}, | |
| organization={Springer} | |
| } | |
| @article{bernstein2022closing, | |
| title={Closing the Gap Between Directed Hopsets and Shortcut Sets}, | |
| author={Bernstein, Aaron and Wein, Nicole}, | |
| journal={arXiv preprint arXiv:2207.04507}, | |
| year={2022} | |
| } | |
| @book{klein1993linear, | |
| title={A linear-processor polylog-time algorithm for shortest paths in planar graphs}, | |
| author={Klein, Philip N and Subramanian, Sairam}, | |
| year={1993}, | |
| publisher={IEEE} | |
| } | |
| @article{chaudhuri1998shortest, | |
| title={Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms}, | |
| author={Chaudhuri, Shiva and Zaroliagis, Christos D}, | |
| journal={Theoretical Computer Science}, | |
| volume={203}, | |
| number={2}, | |
| pages={205--223}, | |
| year={1998}, | |
| publisher={Elsevier} | |
| } | |
| @article{kainer2019more, | |
| title={More parallelism in Dijkstra's single-source shortest path algorithm}, | |
| author={Kainer, Michael and Tr{\"a}ff, Jesper Larsson}, | |
| journal={arXiv preprint arXiv:1903.12085}, | |
| year={2019} | |
| } | |
| @article{dufoulon2022almost, | |
| title={An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}, | |
| author={Dufoulon, Fabien and Kutten, Shay and Moses Jr, William K and Pandurangan, Gopal and Peleg, David}, | |
| journal={arXiv preprint arXiv:2210.01173}, | |
| year={2022} | |
| } | |
| @personalcommunication{merav22personal, | |
| author={Parter, Merav}, | |
| year={2022}, | |
| howpublished = "unpublished" | |
| } | |
| @article{aspnes2006eight, | |
| title={Eight Open Problems in Distributed Computing.}, | |
| author={Aspnes, James and Busch, Costas and Dolev, Shlomi and Fatourou, Panagiota and Georgiou, Chryssis and Shvartsman, Alexander A and Spirakis, Paul G and Wattenhofer, Roger}, | |
| journal={Bull. EATCS}, | |
| volume={90}, | |
| pages={109--126}, | |
| year={2006} | |
| } | |
| @inproceedings{racke2008optimal, | |
| title={Optimal hierarchical decompositions for congestion minimization in networks}, | |
| author={R{\"a}cke, Harald}, | |
| booktitle=proc # {40th} # stoc, | |
| pages={255--264}, | |
| year={2008} | |
| } | |
| @inproceedings{filtser2022hop, | |
| title={Hop-constrained metric embeddings and their applications}, | |
| author={Filtser, Arnold}, | |
| booktitle=proc # {63rd} # focs, | |
| pages={492--503}, | |
| year={2022}, | |
| organization={IEEE} | |
| } | |
| @article{chen2022maximum, | |
| title={Maximum flow and minimum-cost flow in almost-linear time}, | |
| author={Chen, Li and Kyng, Rasmus and Liu, Yang P and Peng, Richard and Gutenberg, Maximilian Probst and Sachdeva, Sushant}, | |
| journal={arXiv preprint arXiv:2203.00671}, | |
| year={2022} | |
| } | |
| @inproceedings{hitron2021general, | |
| title={General CONGEST compilers against adversarial edges}, | |
| author={Hitron, Yael and Parter, Merav}, | |
| booktitle={35th International Symposium on Distributed Computing (DISC 2021)}, | |
| year={2021}, | |
| organization={Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik} | |
| } | |
| @article{augustine2022latency, | |
| title={Latency, capacity, and distributed minimum spanning trees}, | |
| author={Augustine, John and Gilbert, Seth and Kuhn, Fabian and Robinson, Peter and Sourav, Suman}, | |
| journal={Journal of Computer and System Sciences}, | |
| volume={126}, | |
| pages={1--20}, | |
| year={2022}, | |
| publisher={Elsevier} | |
| } | |
| @inproceedings{DBLP:journals/corr/abs-2109-05151, | |
| author = {Ioannis Anagnostides and Christoph Lenzen and Bernhard Haeupler and Goran Zuzic and Themis Gouleakis}, | |
| title = {Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts}, | |
| booktitle ={36th International Symposium on Distributed Computing (DISC 2022)}, | |
| pages ={6:1--6:20}, | |
| series ={Leibniz International Proceedings in Informatics (LIPIcs)}, | |
| ISBN ={978-3-95977-255-6}, | |
| ISSN ={1868-8969}, | |
| year ={2022}, | |
| volume ={246}, | |
| editor ={Scheideler, Christian}, | |
| publisher ={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, | |
| address ={Dagstuhl, Germany}, | |
| URL ={https://drops.dagstuhl.de/opus/volltexte/2022/17197}, | |
| URN ={urn:nbn:de:0030-drops-171978}, | |
| doi ={10.4230/LIPIcs.DISC.2022.6}, | |
| annote ={Keywords: Distributed algorithms, Laplacian solvers, low-congestion shortcuts}, | |
| nameorder = {random} | |
| } | |
| @article{harvey2021integer, | |
| title={Integer multiplication in time O (n log n)}, | |
| author={Harvey, David and Van Der Hoeven, Joris}, | |
| journal={Annals of Mathematics}, | |
| volume={193}, | |
| number={2}, | |
| pages={563--617}, | |
| year={2021}, | |
| publisher={JSTOR} | |
| } | |
| @inproceedings{shun2013ligra, | |
| title={Ligra: a lightweight graph processing framework for shared memory}, | |
| author={Shun, Julian and Blelloch, Guy E}, | |
| booktitle=proc # {18th} # ppopp, | |
| pages={135--146}, | |
| year={2013} | |
| } | |
| @inproceedings{madduri2007experimental, | |
| title={An experimental study of a parallel shortest path algorithm for solving large-scale graph instances}, | |
| author={Madduri, Kamesh and Bader, David A and Berry, Jonathan W and Crobak, Joseph R}, | |
| booktitle=proc # {9th} # alenex, | |
| pages={23--35}, | |
| year={2007}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{dhulipala2017julienne, | |
| title={Julienne: A framework for parallel graph algorithms using work-efficient bucketing}, | |
| author={Dhulipala, Laxman and Blelloch, Guy and Shun, Julian}, | |
| booktitle=proc # {29th} spaa, | |
| pages={293--304}, | |
| year={2017} | |
| } | |
| @article{raghavan1987randomized, | |
| title={Randomized rounding: a technique for provably good algorithms and algorithmic proofs}, | |
| author={Raghavan, Prabhakar and Tompson, Clark D}, | |
| journal={Combinatorica}, | |
| volume={7}, | |
| number={4}, | |
| pages={365--374}, | |
| year={1987}, | |
| publisher={Springer} | |
| } | |
| @inproceedings{parter2019optimal, | |
| title={Optimal short cycle decomposition in almost linear time}, | |
| author={Parter, Merav and Yogev, Eylon}, | |
| booktitle=proc # {46th} # icalp, | |
| year={2019}, | |
| organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik} | |
| } | |
| @inproceedings{sherman2017generalized, | |
| title={Generalized preconditioning and undirected minimum-cost flow}, | |
| author={Sherman, Jonah}, | |
| booktitle=proc # {28th} # soda, | |
| pages={772--780}, | |
| year={2017}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{sherman2017area, | |
| title={Area-convexity, $\ell_\infty$ regularization, and undirected multicommodity flow}, | |
| author={Sherman, Jonah}, | |
| booktitle=proc # {49th} # stoc, | |
| pages={452--460}, | |
| year={2017} | |
| } | |
| @article{harary1988survey, | |
| title={A survey of the theory of hypercube graphs}, | |
| author={Harary, Frank and Hayes, John P and Wu, Horng-Jyh}, | |
| journal={Computers \& Mathematics with Applications}, | |
| volume={15}, | |
| number={4}, | |
| pages={277--289}, | |
| year={1988}, | |
| publisher={Elsevier} | |
| } | |
| @inproceedings{spielman2004nearly, | |
| title={Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems}, | |
| author={Spielman, Daniel A and Teng, Shang-Hua}, | |
| booktitle={Proceedings of the thirty-sixth annual ACM symposium on Theory of computing}, | |
| pages={81--90}, | |
| year={2004} | |
| } | |
| @inproceedings{sherman2013nearly, | |
| title={Nearly maximum flows in nearly linear time}, | |
| author={Sherman, Jonah}, | |
| booktitle={2013 IEEE 54th Annual Symposium on Foundations of Computer Science}, | |
| pages={263--269}, | |
| year={2013}, | |
| organization={IEEE} | |
| } | |
| @inproceedings{bernstein2022negative, | |
| title={Negative-weight single-source shortest paths in near-linear time}, | |
| author={Bernstein, Aaron and Nanongkai, Danupon and Wulff-Nilsen, Christian}, | |
| booktitle={2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)}, | |
| pages={600--611}, | |
| year={2022}, | |
| organization={IEEE} | |
| } | |
| @article{cohen2021solving, | |
| title={Solving linear programs in the current matrix multiplication time}, | |
| author={Cohen, Michael B and Lee, Yin Tat and Song, Zhao}, | |
| journal={Journal of the ACM (JACM)}, | |
| volume={68}, | |
| number={1}, | |
| pages={1--39}, | |
| year={2021}, | |
| publisher={ACM New York, NY, USA} | |
| } | |
| @inproceedings{li2020faster, | |
| title={Faster parallel algorithm for approximate shortest path}, | |
| author={Li, Jason}, | |
| booktitle={Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing}, | |
| pages={308--321}, | |
| year={2020} | |
| } | |
| @inproceedings{kelner2014almost, | |
| title={An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations}, | |
| author={Kelner, Jonathan A and Lee, Yin Tat and Orecchia, Lorenzo and Sidford, Aaron}, | |
| booktitle={Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms}, | |
| pages={217--226}, | |
| year={2014}, | |
| organization={SIAM} | |
| } | |
| @inproceedings{rozhovn2022parallel, | |
| title={Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances}, | |
| author={Rozho{\v{n}}, V{\'a}clav and Haeupler, Bernhard and Martinsson, Anders and Grunau, Christoph and Zuzic, Goran}, | |
| booktitle=proc # {55th} # stoc, | |
| year={2023} | |
| } | |
| @inproceedings{cao2023parallel, | |
| title={Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth}, | |
| author={Cao, Nairen and Fineman, Jeremy T}, | |
| booktitle=proc # {34th} # soda, | |
| pages={4354--4372}, | |
| year={2023}, | |
| organization={SIAM} | |
| } | |
| @article{abraham2020ramsey, | |
| title={Ramsey spanning trees and their applications}, | |
| author={Abraham, Ittai and Chechik, Shiri and Elkin, Michael and Filtser, Arnold and Neiman, Ofer}, | |
| journal={ACM Transactions on Algorithms (TALG)}, | |
| volume={16}, | |
| number={2}, | |
| pages={1--21}, | |
| year={2020}, | |
| publisher={ACM New York, NY, USA} | |
| } | |
| @inproceedings{assadi2022semi, | |
| title={Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space∗}, | |
| author={Assadi, Sepehr and Jambulapati, Arun and Jin, Yujia and Sidford, Aaron and Tian, Kevin}, | |
| booktitle=proc # {33rd} # soda, | |
| pages={627--669}, | |
| year={2022}, | |
| organization={SIAM} | |
| } | |
| @article{forster2022laplacian, | |
| title={The laplacian paradigm in the broadcast congested clique}, | |
| author={Forster, Sebastian and De Vos, Tijn}, | |
| journal={arXiv preprint arXiv:2205.12059}, | |
| year={2022} | |
| } | |
| @inproceedings{alman2020algorithms, | |
| title={Algorithms and hardness for linear algebra on geometric graphs}, | |
| author={Alman, Josh and Chu, Timothy and Schild, Aaron and Song, Zhao}, | |
| booktitle={2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)}, | |
| pages={541--552}, | |
| year={2020}, | |
| organization={IEEE} | |
| } | |
| @inproceedings{abboud2022hardness, | |
| title={Hardness of approximation in p via short cycle removal: Cycle detection, distance oracles, and beyond}, | |
| author={Abboud, Amir and Bringmann, Karl and Khoury, Seri and Zamir, Or}, | |
| booktitle={Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing}, | |
| pages={1487--1500}, | |
| year={2022} | |
| } | |
| @inproceedings{anagnostides2021almost, | |
| title={Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts}, | |
| author={Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis}, | |
| booktitle = proc # {36th} # disc, | |
| year={2022} | |
| } | |
| @inproceedings{cypher1990deterministic, | |
| title={Deterministic sorting in nearly logarithmic time on the hypercube and related computers}, | |
| author={Cypher, Robert and Plaxton, C Greg}, | |
| booktitle={Proceedings of the twenty-second annual ACM symposium on Theory of Computing}, | |
| pages={193--203}, | |
| year={1990} | |
| } | |
| @inproceedings{batcher1968sorting, | |
| title={Sorting networks and their applications}, | |
| author={Batcher, Kenneth E}, | |
| booktitle={Proceedings of the April 30--May 2, 1968, spring joint computer conference}, | |
| pages={307--314}, | |
| year={1968} | |
| } | |
| @inproceedings{ghaffari2023faster, | |
| title={Faster Deterministic Distributed MIS and Approximate Matching}, | |
| author={Ghaffari, Mohsen and Grunau, Christoph}, | |
| booktitle={Proceedings of the 55th Annual ACM Symposium on Theory of Computing}, | |
| pages={1777--1790}, | |
| year={2023} | |
| } | |
| @article{anagnostides2021deterministic, | |
| title={Deterministic distributed algorithms and lower bounds in the hybrid model}, | |
| author={Anagnostides, Ioannis and Gouleakis, Themis}, | |
| journal={arXiv preprint arXiv:2108.01740}, | |
| year={2021} | |
| } | |
| @inproceedings{ghaffari2020network, | |
| title={Network Decomposition and Distributed Derandomization}, | |
| author={Ghaffari, Mohsen}, | |
| booktitle={International Colloquium on Structural Information and Communication Complexity}, | |
| pages={3--18}, | |
| year={2020}, | |
| organization={Springer} | |
| } | |
| @article{panconesi1996complexity, | |
| title={On the complexity of distributed network decomposition}, | |
| author={Panconesi, Alessandro and Srinivasan, Aravind}, | |
| journal={Journal of Algorithms}, | |
| volume={20}, | |
| number={2}, | |
| pages={356--374}, | |
| year={1996}, | |
| publisher={Elsevier} | |
| } | |
| @article{chang2019time, | |
| title={A time hierarchy theorem for the LOCAL model}, | |
| author={Chang, Yi-Jun and Pettie, Seth}, | |
| journal={SIAM Journal on Computing}, | |
| volume={48}, | |
| number={1}, | |
| pages={33--69}, | |
| year={2019}, | |
| publisher={SIAM} | |
| } | |
| @article{chen2016distributed, | |
| title={Distributed greedy coding-aware deterministic routing for multi-flow in wireless networks}, | |
| author={Chen, Jing and He, Kun and Yuan, Quan and Du, Ruiying and Wang, Lina and Wu, Jie}, | |
| journal={Computer Networks}, | |
| volume={105}, | |
| pages={194--206}, | |
| year={2016}, | |
| publisher={Elsevier} | |
| } | |
| @inproceedings{gerla1973deterministic, | |
| title={Deterministic and adaptive routing policies in packet-switched computer networks}, | |
| author={Gerla, Mario}, | |
| booktitle={Proceedings of the third ACM symposium on Data communications and Data networks: Analysis and design}, | |
| pages={23--28}, | |
| year={1973} | |
| } | |
| @article{leighton1998hypercubic, | |
| title={Hypercubic sorting networks}, | |
| author={Leighton, Tom and Plaxton, C Greg}, | |
| journal={SIAM Journal on Computing}, | |
| volume={27}, | |
| number={1}, | |
| pages={1--47}, | |
| year={1998}, | |
| publisher={SIAM} | |
| } | |
| @inproceedings{ajtai19830, | |
| title={An O(n log n) sorting network}, | |
| author={Ajtai, Mikl{\'o}s and Koml{\'o}s, J{\'a}nos and Szemer{\'e}di, Endre}, | |
| booktitle={Proceedings of the fifteenth annual ACM symposium on Theory of computing}, | |
| pages={1--9}, | |
| year={1983} | |
| } | |
| @inproceedings{chang2020deterministic, | |
| title={Deterministic distributed expander decomposition and routing with applications in distributed derandomization}, | |
| author={Chang, Yi-Jun and Saranurak, Thatchaphol}, | |
| booktitle={2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)}, | |
| pages={377--388}, | |
| year={2020}, | |
| organization={IEEE} | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment