Add paper

1 files changed, 1122 insertions, 0 deletions

diff --git a/paper/adaptive_sseding.bib b/paper/adaptive_sseding.bib
new file mode 100644
index 0000000..e08486e
--- /dev/null
+++ b/paper/adaptive_sseding.bib
@@ -0,0 +1,1122 @@
+@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}
+}
\ No newline at end of file