path: root/paper/adaptive_sseding.bib

@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}
}