@book{shapiro2009lectures, title={Lectures on stochastic programming: modeling and theory}, author={Shapiro, Alexander and Dentcheva, Darinka and Ruszczy{\'n}ski, Andrzej}, volume={9}, year={2009}, publisher={Society for Industrial Mathematics} } @article{feld1991, title={Why your friends have more friends than you do}, author={Feld, Scott L}, journal={American Journal of Sociology}, pages={1464--1477}, year={1991}, publisher={JSTOR} } @Article{NWF78, author = {G. L. Nemhauser and L. A. Wolsey and M. L. Fisher}, title = {An analysis of approximations for maximizing submodular set functions II}, journal = {Math. Programming Study 8}, year = {1978}, OPTkey = {}, OPTvolume = {8}, pages = {73--87}, } @article{GMC, title={The generalized maximum coverage problem}, author={Cohen, Reuven and Katzir, Liran}, journal={Information Processing Letters}, volume={108}, number={1}, pages={15--22}, year={2008}, publisher={Elsevier} } @article{holley1975ergodic, title={Ergodic theorems for weakly interacting infinite systems and the voter model}, author={Holley, Richard A and Liggett, Thomas M}, journal={The annals of probability}, pages={643--663}, year={1975}, publisher={JSTOR} } @article{Voter, author = {Eyal Even-Dar and Asaf Shapira}, title = {A note on maximizing the spread of influence in social networks}, journal = {Inf. Process. Lett.}, volume = {111}, number = {4}, year = {2011}, pages = {184-187}, ee = {http://dx.doi.org/10.1016/j.ipl.2010.11.015}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{feige1998threshold, title={A threshold of ln n for approximating set cover}, author={Feige, Uriel}, journal={Journal of the ACM (JACM)}, volume={45}, number={4}, pages={634--652}, year={1998}, publisher={ACM} } @MISC{StochProg, author = {Maarten H. {van der Vlerk}}, title = {Stochastic Programming Bibliography}, year = {1996-2007}, howpublished = {World Wide Web, \url{http://www.eco.rug.nl/mally/spbib.html}} } @article{SampleAverage, title={The sample average approximation method for stochastic discrete optimization}, author={Kleywegt, Anton J and Shapiro, Alexander and Homem-de-Mello, Tito}, journal={SIAM Journal on Optimization}, volume={12}, number={2}, pages={479--502}, year={2002}, publisher={SIAM} } @inproceedings{immorlica2004costs, title={On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems}, author={Immorlica, Nicole and Karger, David and Minkoff, Maria and Mirrokni, Vahab S}, booktitle={Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms}, pages={691--700}, year={2004}, organization={Society for Industrial and Applied Mathematics} } @incollection{ravi2004hedging, title={Hedging uncertainty: Approximation algorithms for stochastic optimization problems}, author={Ravi, R and Sinha, Amitabh}, booktitle={Integer programming and combinatorial optimization}, pages={101--115}, year={2004}, publisher={Springer} } @inproceedings{gupta2004boosted, title={Boosted sampling: approximation algorithms for stochastic optimization}, author={Gupta, Anupam and P{\'a}l, Martin and Ravi, R and Sinha, Amitabh}, booktitle={Proceedings of the thirty-sixth annual ACM symposium on Theory of computing}, pages={417--426}, year={2004}, organization={ACM} } @incollection{gupta2005wednesday, title={What about wednesday? approximation algorithms for multistage stochastic optimization}, author={Gupta, Anupam and P{\'a}l, Martin and Ravi, Ramamoorthi and Sinha, Amitabh}, booktitle={Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques}, pages={86--98}, year={2005}, publisher={Springer} } @inproceedings{shmoys2004stochastic, title={Stochastic optimization is (almost) as easy as deterministic optimization}, author={Shmoys, David B and Swamy, Chaitanya}, booktitle={Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on}, pages={228--237}, year={2004}, organization={IEEE} } @article{shmoys2006approximation, title={An approximation scheme for stochastic linear programming and its application to stochastic integer programs}, author={Shmoys, David B and Swamy, Chaitanya}, journal={Journal of the ACM (JACM)}, volume={53}, number={6}, pages={978--1012}, year={2006}, publisher={ACM} } @inproceedings{swamy2005sampling, title={Sampling-based approximation algorithms for multi-stage stochastic optimization}, author={Swamy, Chaitanya and Shmoys, David B}, booktitle={Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on}, pages={357--366}, year={2005}, organization={IEEE} } @inproceedings{srinivasan2007approximation, title={Approximation algorithms for stochastic and risk-averse optimization}, author={Srinivasan, Aravind}, booktitle={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms}, pages={1305--1313}, year={2007}, organization={Society for Industrial and Applied Mathematics} } @article{kleinberg2000allocating, title={Allocating bandwidth for bursty connections}, author={Kleinberg, Jon and Rabani, Yuval and Tardos, {\'E}va}, journal={SIAM Journal on Computing}, volume={30}, number={1}, pages={191--217}, year={2000}, publisher={SIAM} } @inproceedings{dean2004approximating, title={Approximating the stochastic knapsack problem: The benefit of adaptivity}, author={Dean, Brian C and Goemans, Michel X and Vondrdk, J}, booktitle={Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on}, pages={208--217}, year={2004}, organization={IEEE} } @inproceedings{gupta2012approximation, title={Approximation algorithms for stochastic orienteering}, author={Gupta, Anupam and Krishnaswamy, Ravishankar and Nagarajan, Viswanath and Ravi, R}, booktitle={Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms}, pages={1522--1538}, year={2012}, organization={SIAM} } @article{golovin2011adaptive, title={Adaptive submodularity: Theory and applications in active learning and stochastic optimization}, author={Golovin, Daniel and Krause, Andreas}, journal={Journal of Artificial Intelligence Research}, volume={42}, number={1}, pages={427--486}, year={2011}, publisher={AI Access Foundation} } @inproceedings{kempe2003maximizing, title={Maximizing the spread of influence through a social network}, author={Kempe, David and Kleinberg, Jon and Tardos, {\'E}va}, booktitle={Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining}, pages={137--146}, year={2003}, organization={ACM} } @incollection{asadpour2008stochastic, title={Stochastic submodular maximization}, author={Asadpour, Arash and Nazerzadeh, Hamid and Saberi, Amin}, booktitle={Internet and Network Economics}, pages={477--489}, year={2008}, publisher={Springer} } @inproceedings{mturk, title = {Mechanical Turk}, booktitle = {https://www.mturk.com/}, } @inproceedings{SM11, author = {Yaron Singer and Manas Mittal}, title = {Mechanisms for Online Labor Markets}, booktitle = {Workshop on Human Computation }, year = {2011}, } @inproceedings{GR11, author = {Arpita Ghosh and Aaron Roth}, title = {Selling privacy at auction}, booktitle = {ACM Conference on Electronic Commerce}, year = {2011}, pages = {199-208}, } @inproceedings{KDD11, author = {Michael Mathioudakis and Francesco Bonchi and Carlos Castillo and Aristides Gionis and Antti Ukkonen}, title = {Sparsi�cation of Influence Networks}, booktitle = {KDD}, year = {2011}, } @inproceedings{HIMM11, author = {Nima Haghpanah and Nicole Immorlica and Vahab S. Mirrokni and Kamesh Munagala}, title = {Optimal auctions with positive network externalities}, booktitle = {ACM Conference on Electronic Commerce}, year = {2011}, pages = {11-20}, ee = {http://doi.acm.org/10.1145/1993574.1993577}, crossref = {DBLP:conf/sigecom/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{DPS11, author = {Shahar Dobzinski and Christos Papadimitriou and Yaron Singer}, title = {Mechanisms for Complement-Free Procurement}, booktitle = {EC}, year = {2011}, } @inproceedings{BHMW11, author = {Eytan Bakshy and Jake M. Hofman and Winter A. Mason and Duncan J. Watts}, title = {Everyone's an influencer: quantifying influence on twitter}, booktitle = {WSDM}, year = {2011}, } @inproceedings{S10, author = {Yaron Singer}, title = {Budget Feasible Mechanisms}, booktitle = {FOCS}, year = {2010}, pages = {765-774}, ee = {http://dx.doi.org/10.1109/FOCS.2010.78}, crossref = {DBLP:conf/focs/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{GBL10, author = {Amit Goyal and Francesco Bonchi and Laks V. S. Lakshmanan}, title = {Learning influence probabilities in social networks}, booktitle = {WSDM}, year = {2010}, pages = {241-250}, ee = {http://doi.acm.org/10.1145/1718487.1718518}, crossref = {DBLP:conf/wsdm/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{YC10, author = {Jiang Yang and Scott Counts}, title = {Predicting the Speed, Scale, and Range of Information Diffusion in Twitter}, booktitle = {ICWSM}, year = {2010}, } @inproceedings{LKGFVG07, author = {Jure Leskovec and Andreas Krause and Carlos Guestrin and Christos Faloutsos and Jeanne M. VanBriesen and Natalie S. Glance}, title = {Cost-effective outbreak detection in networks}, booktitle = {KDD}, year = {2007}, pages = {420-429}, ee = {http://doi.acm.org/10.1145/1281192.1281239}, crossref = {DBLP:conf/kdd/2007}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{ES11, author = {Eyal Even-Dar and Asaf Shapira}, title = {A note on maximizing the spread of influence in social networks}, journal = {Inf. Process. Lett.}, volume = {111}, number = {4}, year = {2011}, pages = {184-187}, ee = {http://dx.doi.org/10.1016/j.ipl.2010.11.015}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{MS10, author = {Elchanan Mossel and Grant Schoenebeck}, title = {Reaching Consensus on Social Networks}, booktitle = {ICS}, year = {2010}, pages = {214-229}, ee = {http://conference.itcs.tsinghua.edu.cn/ICS2010/content/papers/18.html}, crossref = {DBLP:conf/innovations/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{MR07, author = {Elchanan Mossel and S{\'e}bastien Roch}, title = {On the submodularity of influence in social networks}, booktitle = {STOC}, year = {2007}, pages = {128-134}, } @INPROCEEDINGS{KR05, author = {Jon Kleinberg and Prabhakar Raghavan}, title = {Query Incentive Networks}, booktitle = {Proc. 46th IEEE Symposium on Foundations of Computer Science}, year = {2005}, pages = {132--141} } @inproceedings{RD02, author = {Matthew Richardson and Pedro Domingos}, title = {Mining knowledge-sharing sites for viral marketing}, booktitle = {KDD}, year = {2002}, pages = {61-70}, } @inproceedings{DR01, author = {Pedro Domingos and Matthew Richardson}, title = {Mining the network value of customers}, booktitle = {KDD}, year = {2001}, pages = {57-66}, } @inproceedings{RLK10, author = {Manuel Gomez-Rodriguez and Jure Leskovec and Andreas Krause}, title = {Inferring networks of diffusion and influence}, booktitle = {KDD}, year = {2010}, pages = {1019-1028}, } @inproceedings{LAH06, author = {Jure Leskovec and Lada A. Adamic and Bernardo A. Huberman}, title = {The dynamics of viral marketing}, booktitle = {ACM Conference on Electronic Commerce}, year = {2006}, pages = {228-237}, } @inproceedings{CKT10, author = {Flavio Chierichetti and Ravi Kumar and Andrew Tomkins}, title = {Max-cover in map-reduce}, booktitle = {WWW}, year = {2010}, pages = {231-240}, ee = {http://doi.acm.org/10.1145/1772690.1772715}, crossref = {DBLP:conf/www/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{CGL11, author = {Ning Chen and Nick Gravin and Pinyan Lu}, title = {On the Approximability of Budget Feasible Mechanisms}, booktitle = {SODA}, year = {2011}, } @inproceedings{fbdata, author= {Minas Gjoka and Maciej Kurant and Carter T. Butts and Athina Markopoulou}, title= { {Walking in Facebook: A Case Study of Unbiased Sampling of OSNs} }, booktitle = {Proceedings of IEEE INFOCOM '10}, address = {San Diego, CA}, month = {March}, year = {2010} } @inproceedings{ADL09, author = {Itai Ashlagi and Shahar Dobzinski and Ron Lavi}, title = {An optimal lower bound for anonymous scheduling mechanisms}, booktitle = {ACM Conference on Electronic Commerce}, year = {2009}, pages = {169-176}, } @inproceedings{C08, author = {Ning Chen}, title = {On the approximability of influence in social networks}, booktitle = {SODA}, year = {2008}, pages = {1029-1037} } @inproceedings{DS08, author = {Shahar Dobzinski and Mukund Sundararajan}, title = {On characterizations of truthful mechanisms for combinatorial auctions and scheduling}, booktitle = {ACM Conference on Electronic Commerce}, year = {2008}, pages = {38-47}, ee = {http://doi.acm.org/10.1145/1386790.1386798}, crossref = {DBLP:conf/sigecom/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{AG08, author = {Yossi Azar and Iftah Gamzu}, title = {Truthful Unification Framework for Packing Integer Programs with Choices}, booktitle = {ICALP (1)}, year = {2008}, pages = {833-844}, } @article{BLM08, author = {Jeremy Bulow and Jonathan Levin and Paul Milgrom}, title = {Winning Play in Spectrum Auctions}, journal = {Working Paper}, } @InProceedings{PSS08, author = {Christos H. Papadimitriou and Michael Schapira and Yaron Singer}, title = {On the Hardness of Being Truthful}, booktitle = {FOCS}, year = {2008} } @inproceedings{DLN08, author = {Shahar Dobzinski and Ron Lavi and Noam Nisan}, title = {Multi-unit Auctions with Budget Limits}, booktitle = {FOCS}, year = {2008}, pages = {260-269}, } @inproceedings{CFHK08, author = {Matthew Cary and Abraham D. Flaxman and Jason D. Hartline and Anna R. Karlin}, title = {Auctions for structured procurement}, booktitle = {SODA}, year = {2008}, pages = {304-313}, } @inproceedings{MSV08, author = {Vahab S. Mirrokni and Michael Schapira and Jan Vondr{\'a}k}, title = {Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions}, booktitle = {ACM Conference on Electronic Commerce}, year = {2008}, pages = {70-77}, } @article{Google08, author = {Gagan Aggarwal and Nir Ailon and Florin Constantin and Eyal Even-Dar and Jon Feldman and Gereon Frahling and Monika Rauch Henzinger and S. Muthukrishnan and Noam Nisan and Martin P{\'a}l and Mark Sandler and Anastasios Sidiropoulos}, title = {Theory research at Google}, journal = {SIGACT News}, volume = {39}, number = {2}, year = {2008}, pages = {10-28}, } @article{MN08, author = {Ahuva Mu'alem and Noam Nisan}, title = {Truthful Approximation Mechanisms for Restricted Combinatorial Auctions}, journal = {Games and Economic Behavior}, year = {2008}, pages = {612--631}, volume = {64}, number = {2} } @article{JY07, author = {Matthew O. Jackson and Leeat Yariv}, title = {Diffusion of Behavior and Equilibrium Properties in Network Games}, journal = {American Economic Review}, year = {2007} } @inproceedings{MR07, author = {Elchanan Mossel and S{\'e}bastien Roch}, title = {On the submodularity of influence in social networks}, booktitle = {STOC}, year = {2007}, pages = {128-134}, } @inproceedings{B07, author = {Liad Blumrosen}, title = {Implementing the Maximum of Monotone Algorithms}, booktitle = {AAAI}, year = {2007}, pages = {30-35}, } @inproceedings{JM07, author = {Kamal Jain and Mohammad Mahdian}, title = {Cost Sharing}, booktitle = {Algorithmic Game Theory}, editor = {Nisan, Noam and Roughgarden, Tim and Tardos, Eva and Vazirani, Vijay V.}, publisher = {Cambridge University Press}, year = {2007} } @inproceedings{FMPS07, author = {Jon Feldman and S. Muthukrishnan and Martin P{\'a}l and Clifford Stein}, title = {Budget optimization in search-based advertising auctions}, booktitle = {ACM Conference on Electronic Commerce}, year = {2007}, pages = {40-49}, } @inproceedings{MS07, author = {Ahuva Mu'alem and Michael Schapira}, title = {Setting lower bounds on truthfulness: extended abstract}, booktitle = {SODA}, year = {2007}, pages = {1143-1152}, } @article{AT07, author = {Aaron Archer and {\'E}va Tardos}, title = {Frugal path mechanisms}, journal = {ACM Transactions on Algorithms}, volume = {3}, number = {1}, year = {2007}, } @inproceedings{KKT05, author = {Anna R. Karlin and David Kempe and Tami Tamir}, title = {Beyond {VCG}: Frugality of Truthful Mechanisms}, booktitle = {FOCS}, year = {2005}, pages = {615-626}, } @inproceedings{LS05, author = {Ron Lavi and Chaitanya Swamy}, title = {Truthful and Near-Optimal Mechanism Design via Linear Programming}, booktitle = {FOCS}, year = {2005}, pages = {595-604}, } @inproceedings{BN05, author = {Liad Blumrosen and Noam Nisan}, title = {On the computational power of iterative auctions}, booktitle = {ACM Conference on Electronic Commerce}, year = {2005}, pages = {29-43}, } @inproceedings{BCIMS05, author = {Christian Borgs and Jennifer T. Chayes and Nicole Immorlica and Mohammad Mahdian and Amin Saberi}, title = {Multi-unit auctions with budget-constrained bidders}, booktitle = {ACM Conference on Electronic Commerce}, year = {2005}, pages = {44-51}, } @inproceedings{FMT04, author = {Christos Faloutsos and Kevin S. McCurley and Andrew Tomkins}, title = {Fast discovery of connection subgraphs}, booktitle = {KDD}, year = {2004}, pages = {118-127}, } @inproceedings{WINE10, author = {David Arthur and Rajeev Motwani and Aneesh Sharma and Ying Xu 0002}, title = {Pricing Strategies for Viral Marketing on Social Networks}, booktitle = {WINE}, year = {2009}, pages = {101-112}, ee = {http://dx.doi.org/10.1007/978-3-642-10841-9_11}, crossref = {DBLP:conf/wine/2009}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{WWW10, author = {Paul D{\"u}tting and Monika Henzinger and Ingmar Weber}, title = {How much is your personal recommendation worth?}, booktitle = {WWW}, year = {2010}, pages = {1085-1086}, ee = {http://doi.acm.org/10.1145/1772690.1772816}, crossref = {DBLP:conf/www/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{KG05, author = {Andreas Krause and Carlos Guestrin}, title = {A Note on the Budgeted Maximization of Submodular Functions}, booktitle = {Technical Report}, year = {2005}, pages = {CMU- CALD- 0 5 - 1 0 3 }, } @inproceedings{HMS08, author = {Jason D. Hartline and Vahab S. Mirrokni and Mukund Sundararajan}, title = {Optimal marketing strategies over social networks}, booktitle = {WWW}, year = {2008}, pages = {189-198}, ee = {http://doi.acm.org/10.1145/1367497.1367524}, crossref = {DBLP:conf/www/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{ESS04, author = {Edith Elkind and Amit Sahai and Kenneth Steiglitz}, title = {Frugality in path auctions}, booktitle = {SODA}, year = {2004}, pages = {701-709}, } @article{AS04, author = {Alexander A. Ageev and Maxim Sviridenko}, title = {Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee}, journal = {J. Comb. Optim.}, volume = {8}, number = {3}, year = {2004}, pages = {307-328}, } @inproceedings{T03, author = {Kunal Talwar}, title = {The Price of Truth: Frugality in Truthful Mechanisms}, booktitle = {STACS}, year = {2003}, pages = {608-619}, } @article{MARS03, author = {Hohner, Gail and Rich, John and Ng, Ed and Reid, Grant and Davenport, Andrew J. and Kalagnanam, Jayant R. and Lee, Ho Soo and An, Chae}, title = {Combinatorial and quantity-discount procurement auctions benefit {M}ars, incorporated and its suppliers}, journal = {Interfaces}, volume = {33}, number = {1}, year = {2003}, publisher = {INFORMS}, } @inproceedings{KKT03, author = {David Kempe and Jon M. Kleinberg and {\'E}va Tardos}, title = {Maximizing the spread of influence through a social network}, booktitle = {KDD}, year = {2003}, pages = {137-146}, } @inproceedings{FPSS02, author = {Joan Feigenbaum and Christos H. Papadimitriou and Rahul Sami and Scott Shenker}, title = {A BGP-based mechanism for lowest-cost routing}, booktitle = {PODC}, year = {2002}, pages = {173-182}, ee = {http://doi.acm.org/10.1145/571825.571856}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{M02, author={Moulin, Herve}, editor={K. J. Arrow and A. K. Sen and K. Suzumura}, title={Axiomatic cost and surplus sharing}, booktitle={Handbook of Social Choice and Welfare}}, publisher={Elsevier}, year=2002, month={}, volume={1}, number={}, edition={}, chapter={6}, pages={289-357}, url={http://ideas.repec.org/h/eee/socchp/1-06.html} } @inproceedings{LLN01, author = {Benny Lehmann and Daniel Lehmann and Noam Nisan}, title = {Combinatorial Auctions With Decreasing Marginal Utilities}, booktitle={ACM conference on electronic commerce}, year = {2001} } @inproceedings{GHW01, author = {Andrew V. Goldberg and Jason D. Hartline and Andrew Wright}, title = {Competitive auctions and digital goods}, booktitle = {SODA}, year = {2001}, pages = {735-744}, } @article{NR01, author = {Noam Nisan and Amir Ronen}, title = {Algorithmic Mechanism Design}, journal = {Games and Economic Behaviour}, year = 2001, volume = 35, pages = {166 -- 196}, note = {A preliminary version appeared in STOC 1999}, } @inproceedings{FPS00, author = {Joan Feigenbaum and Christos H. Papadimitriou and Scott Shenker}, title = {Sharing the cost of muliticast transmissions (preliminary version)}, booktitle = {STOC}, year = {2000}, pages = {218-227}, } @article{KMN99, author = {Khuller,, Samir and Moss,, Anna and Naor,, Joseph (Seffi)}, title = {The budgeted maximum coverage problem}, journal = {Inf. Process. Lett.}, volume = {70}, number = {1}, year = {1999}, issn = {0020-0190}, pages = {39--45}, doi = {http://dx.doi.org/10.1016/S0020-0190(99)00031-9}, publisher = {Elsevier North-Holland, Inc.}, address = {Amsterdam, The Netherlands, The Netherlands}, } @article{F98, author = "Uriel Feige", title = "A Threshold of ln n for Approximating Set Cover", journal = "Journal of the ACM", volume = "45", number = "4", pages = "634-652", year = "1998", } @article{M81, author = {Myerson, R. }, citeulike-article-id = {161188}, journal = {Mathematics of Operations Research}, keywords = {economics, gametheory, markets}, number = {1}, title = {Optimal auction design}, volume = {6}, year = {1981} } @article(R79, AUTHOR = "Kevin Roberts", TITLE = "The Characterization of Implementable Choice Rules", BOOKTITLE = "Aggregation and Revelation of Preferences. Papers presented at the 1st European Summer Workshop of the Econometric Society", EDITOR = "Jean-Jacques Laffont", PAGES = "321-349", PUBLISHER = "North-Holland", YEAR = 1979) @Article{FNW78, author = {G. L. Nemhauser and L. A. Wolsey and M. L. Fisher}, title = {An analysis of approximations for maximizing submodular set functions II}, journal = {Math. Programming Study 8}, year = {1978}, OPTkey = {}, OPTvolume = {8}, pages = {73--87}, } @article{V61, author = {Vickrey, William }, citeulike-article-id = {143671}, journal = {The Journal of Finance}, number = {1}, pages = {8--37}, posted-at = {2005-03-31 20:19:14}, priority = {4}, title = {Counterspeculation, Auctions, and Competitive Sealed Tenders}, url = {http://www.jstor.org/stable/2977633}, volume = {16}, year = {1961} } @inproceedings{LLDM08, author = {Jure Leskovec and Kevin J. Lang and Anirban Dasgupta and Michael W. Mahoney}, title = {Statistical properties of community structure in large social and information networks}, booktitle = {WWW}, year = {2008}, pages = {695-704}, ee = {http://doi.acm.org/10.1145/1367497.1367591}, crossref = {DBLP:conf/www/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{fb, author = {Johan Ugander and Brian Karrer and Lars Backstrom and Cameron Marlow}, title = {The Anatomy of the Facebook Social Graph}, journal = {CoRR}, volume = {abs/1111.4503}, year = {2011}, ee = {http://arxiv.org/abs/1111.4503}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{ls, author = { Silvio Lattanzi and Yaron Singer }, title = {The power of sampling neighbors in social networks}, journal = {Working paper}, } @article{borgs2012influence, title={Influence Maximization in Social Networks: Towards an Optimal Algorithmic Solution}, author={Borgs, Christian and Brautbar, Michael and Chayes, Jennifer and Lucier, Brendan}, journal={arXiv preprint arXiv:1212.0884}, year={2012} } @inproceedings{HIMM11, author = {Nima Haghpanah and Nicole Immorlica and Vahab S. Mirrokni and Kamesh Munagala}, title = {Optimal auctions with positive network externalities}, booktitle = {ACM Conference on Electronic Commerce}, year = {2011}, pages = {11-20}, ee = {http://doi.acm.org/10.1145/1993574.1993577}, crossref = {DBLP:conf/sigecom/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{W82, title={Maximising real-valued submodular functions: Primal and dual heuristics for location problems}, author={Wolsey, Laurence A}, journal={Mathematics of Operations Research}, volume={7}, number={3}, pages={410--425}, year={1982}, publisher={INFORMS} } @article{fb, author = {Johan Ugander and Brian Karrer and Lars Backstrom and Cameron Marlow}, title = {The Anatomy of the Facebook Social Graph}, journal = {CoRR}, volume = {abs/1111.4503}, year = {2011}, ee = {http://arxiv.org/abs/1111.4503}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{ACKS13, author = {Ittai Abraham and Shiri Chechik and David Kempe and Aleksandrs Slivkins}, title = {Low-distortion Inference of Latent Similarities from a Multiplex Social Network}, booktitle = {SODA}, year = {2013}, pages = {1853-1872}, ee = {http://knowledgecenter.siam.org/0236-000019/}, crossref = {DBLP:conf/soda/2013}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{KKT05, author = {David Kempe and Jon M. Kleinberg and {\'E}va Tardos}, title = {Influential Nodes in a Diffusion Model for Social Networks}, booktitle = {ICALP}, year = {2005}, pages = {1127-1138}, ee = {http://dx.doi.org/10.1007/11523468_91}, crossref = {DBLP:conf/icalp/2005}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{HMS08, author = {Jason D. Hartline and Vahab S. Mirrokni and Mukund Sundararajan}, title = {Optimal marketing strategies over social networks}, booktitle = {WWW}, year = {2008}, pages = {189-198}, ee = {http://doi.acm.org/10.1145/1367497.1367524}, crossref = {DBLP:conf/www/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} }