Publications

 

   Some Working Papers


  1. ■On the Implications of Lookahead Search in Game Playing,  Joint with N. Thain, and A. Vetta.


  1. ■Online Ad Allocation with Smooth Delivery, Joint with A. Balghat, J. Feldman, 7th Workshop on Ad Auctions, EC 2011.


  1. ■ Diversity Maximization under Matroid Constraints Joint with Z. Abbassi, and M. Thakur.

  2. ■ Page-based Ad Allocation and the submodular welfare maximization with online bidders, Joint with N. Korula, Q. Yan.

  3. ■PASS Approximations: A New Framework for Analyzing Heuristics, Joint with U. Feige, N. Immorlica, and H. Nazerzadeh, Extended Abstract appeared in Approximation Algorithms and Combinatorial Optimization (APPROX), 2009. Journal Version Accepted to Algorithmica [ PDF File ]


    1. ■Budget Optimization for Online Advertising Campaigns with Carryover Effects, Joint with N. Archak and S. Muthukrishnan, 6th Workshop on Ad Auctions, Harvard, 2010.

       Refereed Conferences and Journals


    2. ■Polyhedral Clinching Auctions and the AdWords Polytope,

    1. Joint with G. Goel and R. Paes Leme
      Symposium on Theory of Computing (STOC), 2012.

    3. ■Simultaneous Approximations of Adversarial and Stochastic Budgeted Allocation Problems,

    4. Joint with S. OveisGharan and M. ZadiMoghaddam
      Symposium on Discrete Algorithms (SODA), 2012.

    1.  

    2. ■ Overlapping Clustering for Distributed Computation

    1. Joint with R. Andersen and D. Gleich
      ACM Conference on Web Search and Data Mining (WSDM), 2012. .

    2. ■ On the Non-Progressive Spread of Influence over Social Networks

    3. Joint with M. Fazli, M. Ghodsi, J. Habib, P. Jalaly, S. Sadeghian.
      8th Latin American Theoretical Informatics (LATIN), 2012. .

    4. ■ On the advantages of overlapping vs. non-overlapping clustering for minimizing conductance,

    5. Joint with R. Khandekar, G. Kortsarz,
      8th Latin American Theoretical Informatics (LATIN), 2012. .

    6. ■ Online Stochastic (Weighted) Matching: Improved Approximation Algorithms,

    7. Joint with B. Haeupler, M. ZadiMoghaddam
      Workshop of Networks and Internet Economics (WINE), 2011. .

    8. ■Inner Products for MinSum Coordination Mechanisms,

    9.    Joint with R. Cole, J. Correa, V. Gkatzelis, N. Olver
               Symposium on Theory of Computing (STOC), 2011.

    10. ■Yield Optimization of Display Advertising with Ad Exchange

    11.     Joint with S. Belsairo, J. Feldman, S. Muthukrishnan, 

    12.     ACM Conference on Electronic Commerce (EC), 2011.

    13. ■Optimal Auctions with Positive Network Externalities

    14.     Joint with N. Haghpanah, N. Immorlica, and K. Munagala,

    15.     ACM Conference on Electronic Commerce (EC), 2011.

    16. ■Auctions with Intermediaries,

    17.    Joint with J. Feldman, S. Muthukrishnan, M. Pai
         ACM Conference on Electronic Commerce (EC), 2010.

    18. ■Online Stochastic Packing applied to Display Ad Allocation,

    19.    Joint with J. Feldman, M. Henzinger, N. Korula, and C. Stein,

    20.    European Symposium on Algorithms (ESA), 2010.

    21. ■Mining Advertiser-Specific User Behaviour Using AdFactors,

    22.    Joint with N. Archak and S. Muthukrishnan
        World Wide Web Conference (WWW), 2010.

    23. ■Quasi-proportional Mechanisms: Prior-free Revenue Maximization,

    24.     Joint with S. Muthukrishnan and U. Nadav
          (LATIN), 2010.

    25. ■Iterative Pricing Over Social Networks,

    26.    Joint with H. Akhlaghpour, M. Ghodsi, N. Haghpanah, H. Mahini, A. Nikzad.

    27.    Workshop of Internet Economics (WINE) 2010. 5th Workshop on Ad Auctions, Stanford, 2009.

    28. ■Equilirbium Pricing with Positive Network Externalities,

    29.    Joint with H. Anari, A. Ehsani, M. Ghodsi, N. Haghpanah, N. Immorlica, H. Mahini.

    30.    Workshop of Internet Economics (WINE) 2010.

    31. ■Online Stochastic Matching: Beating 1-1/e,

    32.    Joint with J. Feldman, A. Mehta, and S. Muthukrishnan
         IEEE Foundations of Computer Science (FOCS), 2009.

    33. ■Online Ad Assignment with Free Disposal

    34.    Joint with J. Feldman, N. Koroula, S. Muthukrishnan and M. Pal
         Workshop of Internet Economics(WINE) 2009.

    35. ■On the Complexity of Nash Dynamics and Sink Equilibria,

    36.    Joint with A. Skopalik
         ACM Conference on Electronic Commerce (EC), 2009.

    37. ■Selfish Routing Over Time

    38.    Joint with M. Hoefer, H. Roeglin, S. Teng
               NetEcon Workshop, Stanford, 2009 and Workshop of Internet Economics (WINE) 2009.

    39. ■PASS Approximations: A New Framework for Analyzing Heuristics,

    40.    Joint with U. Feige, N. Immorlica, and H. Nazerzadeh.

    41.    Approximation Algorithms and Combinatorial Optimization (APPROX), 2009.

    42. ■Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints,

    43.    Joint with J. Lee, V. Nagarajan, M. Sviridenko,

    44.    Symposium of Theory of Computing (STOC), 2009.

    45. ■Bid Optimization for Broad-Match Ad Auctions,

    46.    Joint with E. Even-dar, Y. Mansour, M. Muthukrishnan, U. Nadav,

    47.    18th Int. World Wide Web Conference (WWW), 2009.

    48. ■Approximating Submodular Functions Everywhere,

    49.    Joint with M. Goemans, N. Harvey, and S. Iwata
         Symposium of Discrete Algorithms (SODA), 2009. [ PDF File ]

    50. ■Robust Network Design with Exponential Scenarios,

    51.    Joint with R. Khandekar, G. Kortsarz, M. Salavatipour
         European Symposium of Algorithms (ESA) 2008. [ PDF File ]

    52. ■Uncoordinated Two-sided Markets

    53.    Joint with H. Ackermann, P. Goldberg, H. Roeglin, and B. Voecking
        ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]
        Winner of the Best Paper Award.

    54. ■Fast Convergence to Nearly Optimal Solutions in Potential Games,

    55.    Joint with B. Awerbuch, Y. Azar, and A. Epstein, A. Skopalik
         ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]

    56. ■Tight Information-Theoretic Lower Bounds for Combinatorial Auctions,

    57.    Joint with M. Schapira and J. Vondrak
         ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]

    58. ■Singleton Betting for Permutation Betting Markets,

    59.    Joint with M. Ghodsi, H. Mahini, M. Zadi-moghaddam
         ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]

    60. ■The Myth of the Folk Theorem,

    61.    Joint with C. Borgs, J. Chayes, N. Immorlica, A. Kalai, and C. Papadimitriou
         ACM Symposium of Theory of Computing (STOC) 2008 [ PDF File ]

    62. ■On the Stability of Web Crawling and Web Search,

    63.    Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, and S. Teng,

    64.    19th International Symposium on Algorithms and Computation (ISAAC), 2008. [ PDF File ]

    65. ■Optimal Marketing Strategies over Social Networks,

    66.    Joint with J. Hartline and M. Sundararajan
         17th International World Wide Web Conference (WWW), 2008 [ PDF File ]

    67. ■A Combinatorial Allocation Mechanism for Banner Advertisment with Penalties,

    68.    Joint with U. Feige, N. Immorlica, and H. Nazerzadeh,

    69.    17th International World Wide Web Conference (WWW), 2008 [ PDF File ]

    70. ■Trust-based Recommendation Systems: an Axiomatic Approach,

    71.    Joint with R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, and M. Tennenholtz,

    72.    17th International World Wide Web Conference (WWW), 2008. [ PDF File ]

    73. ■Robust PageRank and Locally Computable Link Spam Features,

    74.    Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain and\ S. Teng,

    75.    International Workshop on Adverserial Information Retreival on the Web (AirWeb) , 2008. [ PDF File ]

    76. ■Improved Approximation Algorithms for Minimum Power Connectivity Problems,

    77.    Joint with G. Kortsarz, Z. Nutov, and E. Tsanko,

    78.    8th Latin American Theoretical Informatics (LATIN), 2008 [ PDF File ]

    79. ■Optimal Coordination Mechanisms for Unrelated Machine Scheduling

    80.    Joint with Y. Azar and K. Jain
         Symposium on Discrete Algorithms (SODA), 2008 [ PDF File ]

    81. ■Maximizing Non-monotone Submodular Functions ,

    82.    Joint with U. Feige and J. Vondrak
         Foundations of Computer Science (FOCS), 2007 [ PDF File ]

    83. ■A Unified Approach to Congestion Games and Two-sided Markets

    84.    Joint with H. Ackermann, P. Goldberg, H. Roeglin, and B. Voecking,

    85.    Workshop of Internet Economics (WINE), 2007 [ PDF File ]

    86. ■Local Computation of PageRank Contributions

    87.    Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, and S. Teng
         Workshop of Graph Models of the Web (WAW), 2008. [ PDF File ]

    88.    Journal version, to appear Internet Mathematics Journal.

    89. ■Robust Combinatorial Optimization with Exponential Scenarios,

    90.    Joint with U. Feige, K. Jain and M. Mahdian,
         Integer Programming and Combinatorial Optimization (IPCO), 2007 [ PDF File ]

    91. ■A Recommendation System Based on Random Walks and Spectral Methods,

    92.    Joint with Z. Abbassi
         Workshop of Web Mining and Social Network Analysis(WebKDD), 2007

    93. ■Assignment Problems in Rental Markets,

    94.    Joint with D. Abraham, N. Chen and V. Kumar,
         2nd Workshop of Internet Economics, WINE, 2006 [ PDF File ]

    95. ■Cell Breathing in Wireless LANs: Algorithms and Evaluation

    96.     Joint with V. Bahl, M. Hajiaghayi, K. Jain, L. Qiu, A. Saberi
          IEEE Transaction on Mobile Computing, 2008. [ PDF File ]

    97. ■Convergence and Approximation in Potential Games ,

    98.    Joint with G. Christodolou and A. Sidiropolous
         Symposium on Theoretical Aspects of Computer Science (STACS), 2006 [ PS File ]

    99. ■Overlay Secure Network Design ,

    100.    Joint with L. Li and M. Mahdian
               Journal Version to appear Algorithmica 2008. Algorithmic Aspects in Information and Management (AAIM) 2006. [ PS File ]

    101. ■(Almost) Tight Approximation Algorithms for Maximizing General Assignment Problems.

    102.     Joint with L. Fleischer, M. Goemans, and M. Sviridenko
          Symposium on Discrete Algorithms (SODA), 2006 [ PS File ]

    103. ■Sink Equilibria and Convergence,

    104.    Joint with M. Goemans and A. Vetta,
         Foundations of Computer Science(FOCS), 2005. [ PS File ]

    105. ■A Relation between Choosability and Uniquely List Colorability,

    106.    Joint with S. Akbari, B.S. Sadjad.
         Journal of Combinatorial Theory, Ser. B . [ PS File ]

    107. ■Bandwidth Sharing VPN Network Design for Multi-class Traffic with Application to VoIP,

    108.    Joint with M. Hajiaghayi, L. Li, and M. Thottan,

    109.    INFOCOM, 2006.

    110. ■Power Optimization for Connectivity Problems, ,

    111.    Joint with M. Hajiaghayi, G. Kortsarz and Z. Nutov,
         Integer Programming and Combinatorial Optimization (IPCO), 2005. [ PS File ]

    112. ■Coordination Mechanisms for Selfish Scheduling ,

    113.    Joint with N. Immorlica, L. Li, and A. Schulz
         Workshop of Internet Economics(WINE), 2005. [ PDF File ]

    114. ■Subjective Cost Policy Routing ,

    115.    Joint with J. Feigenbaum, D. Karger, and R. Sami
               Workshop of Internet Economics(WINE), 2005. Journal Version Theoretical Computer Science 2007. [ PS File ]

    116. ■Confluent Flow Augmentaion for Data Traffic Engineering,

    117.    Joint with R. Bahtia, N. Immorlica, T. Krimbel, S. Naor, and B. Scheiber,

    118.    SPAA, 2005. [ PS File ]

    119. ■Cycle Cover with short cycles ,

    120.    Joint with N. Immorlica and M. Mahdian
               Symposium on Theoretical Aspects of Computer Science (STACS), 2005. [ PDF File ]

    121. ■On the limitations of the Cross-monotone Cost Sharings. ,

    122.    Joint with N. Immorlica and M. Mahdian
         Symposium on Discrete Algorithms (SODA), 2005. [ PS File ]
         Winner of the Best Student Paper Award.

    123. ■Convergence Issues in Competitive Games,

    124.    Joint with A. Vetta,

    125.    APPROX 2004. [ PS File ]

    126. ■On Spectrum Sharing Games ,

    127.    Joint with J. Halpern, M. Halldorson, L. Li,

    128.    PODC 2004. [ PS File ]

    129. ■On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems,

    130.    Joint with N. Immorlica, D. Karger and M. Minkoff.

    131.    Symposium on Discrete Algorithms (SODA), 2004. [ PS File ]

    132. ■Locality-Sensitive Hashing Scheme Based on $p$-Stable Distributions,

    133.    Joint with M. Datar, N. Immorlica and P. Indyk,

    134.    SoCG 2004. [ PS File ]

    135. ■Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks ,

    136.    Joint with M. Bahramgiri; M. Hajiaghayi,

    137.    ACM/Kluwer Wireless Network. [ PS File ]

    138. ■Market Sharing games applied to Content Distribution in Ad-Hoc Networks ,

    139.    Joint with M. Goemans, L. Li, M. Thottan.

    140.    MOBIHOC 2004. [ PS File ]

    141. ■A Simple Polynomial Time Framework To Reduced Path Decomposition in Multi-Path Routing ,

    142.    Joint with M. Thottan, H. Uzunalioglu and S. Paul,

    143.    INFOCOM 2004. [ PS File ]

    144. ■Power Optimization in Topology Control Algorithms for Wireless Multihop networks,

    145.    Joint with M. Hajiaghayi and N. Immorlica,

    146.    MOBICOM 2003. IEEE/ACM Transactions on Networking. [ PS File ]

    147. ■The Facility location problem with general cost functions ,

    148.    Joint with M. Hajiaghayi; M. Mahdian,
         Networks 42(1), pp. 42--47, August 2003. Technical Report MIT-LCS-TR-864, MIT, March 2002. [ PS File ]

    149. ■Path Matching Problems with length constraints,

    150.    Joint with M. Ghodsi, M.T.Hajiaghayi, M. Mahdian.
         Networks, Vol 39/4(2002). pp 210-215. [ PS File ]

    151. ■Scalable Network Monitoring for Evolving IP Networks ,

    152.    Joint with L. Li, M. Thottan, B. Yao and S. Paul
         ICDCS 2004. [ PS File ]

    153. ■Uniquely Vertex Colorable Graphs with Minimum Possible Edges,

    154.    Joint with S. Akbari, B.S. Sadjad.
         Journal of Combinatorial Theory Ser. B, 82 (2001) no.2, 316--318. [ PS File ]

    155. ■On Simultaneous Edge Coloring of Graphs,

    156.    Joint with M.T. Hajiaghaee, E.S.Mahmoodian, A. Saberi, R. Tusserkani,

    157.    Discrete Mathematics 216(2000), pp267-272.


    159. PhD Thesis


    1. ■Approximation Algorithms for Distributed and Selfish Agents , Massachusetts Institute of Technology, June, 2005.


        Tutorials


    1. ■Online Ad Serving: Theory and Practice,

    2.    Joint with A. Mehta
         ACM SIGMETRICS, 2011.


    1. ■Ad Serving: Algorithmic Theory and Practice,

    2.    Joint with A. Mehta
         ACM Conference on Electronic Commerce (EC), 2010.

    3. ■Optimal Marketing and Pricing over Social Networks,

    4.    Joint with N. Immorlica
         World Wide Web Conference (WWW), 2010.

    5. ■Convergence of Natural Game Dynamics,

    6.    Joint with E. Even Dar
         Inernational Conference on Machine Learning (ICML), 2009.

    7. ■Convergence of Nash Dynamics: Equilibria and Nearly-optimal Solutions,

    8.    Joint with H. Roeglin
               ACM Conference on Electronic Commerce (EC), 2009.


        Book Chapters


    1. ■A book chapter on Content Distribution and Two-sided Markets, in Encyclopedia of Algorithms.

    2. ■A book chapter on Nearest Neighbor Methods in Learning and Vision Joint with A. Andoni, M. Datar, N. Immorlica, and P. Indyk.

    3. ■Iranian Informatics Olympiad , Joint with M.T. Hajiaghayi and Y. Ahmadi, Young Scholars Club Pub. Sept, 2000.


        Patents


    1. •Online Clustering of micro-blog posts: Coverage and Diversity with Mayur Thakur.

    2. •Large-scale clustering of Youtube video graph: Connectivity and Density with U. Gargi. W. Lu, S. Yoon.

    3. •Online Ad Allocation with Smooth Delivery, with S. Benson, K. Chen, J. Feldman, S. Gilpin.

    4. •Yield Management of Display Ad Allocation and Ad Exchange , with S. Belsairo, J. Feldman, S. Muthukrishnan.

    5. •Optimal bidding strategies in online advertising with carryover effects , with N. Archak, S. Muthukrishnan.

    6. •Online Stochastic Ad Allocation and Resource Allocation, with J. Feldman, M. Henzinger, N. Korula, C. Stein.

    7. •Online Ad Assignment with Replacements, with J. Feldman, S. Muthukrishnan, M. Pal, N. Koroula.

    8. •Graph-based Attribution in Advertising, with N. Archak, S. Muthukrishnan.

    9. •Social Ad Auctions in the presence of Ad Propagation, with C. Cortes, E. Chang.

    10. •Ad Allocation with Frequency Capping, with J. Feldman, S. Muthukrishnan, A. Mehta.

    11. •Bid Optimization for BroadMatch Ad Auctions, with E. Even Dar, Y. Mansour, S. Muthukrishnan, U. Nadav.

    12. •Offline Optimization for Online Stochastic Ad Allocation, with J. Feldman, S. Muthukrishnan, A. Mehta.

    13. •Quasi-Proportional Mechanisms, with S. Muthukrishnan and U. Nadav.

    14. •Optimal Marketing Strategies over Social Networks, with J. Hartline, V. Mirrokni and M. Sundararajan.

    15. •Monetizing a Social Network Platform with R. Andersen, C. Borgs, J. Chayes, K. Jain, and V. Mirrokni.

    16. •Trust-based Recommendation Systems with R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, V. S. Mirrokni, A. Kalai, M. Tennenholtz.

    17. •Robust PageRank and Locally computable SPAM detection features with R. Andersen, C. Borgs, J. Chayes, K. Jain, J. Hopcroft, V. S. Mirrokni, S. Teng.

    18. •Local Computation of PageRank Contributions, with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, V. S. Mirrokni, S. Teng.

    19. •Score Propagation and Web SPAM Detection. with C. Borgs, J. Chayes, C. Gade, J. Hopcroft, V. S. Mirrokni, A. Prakash, T. Tao.

    20. •Local Partitioning and Web SPAM Detection, with C. Borgs, J. Chayes, C. Gade, J. Hopcroft, V. S. Mirrokni, A. Prakash, T. Tao.

    21. •Graph Structures and Web SPAM Detection, with C. Borgs, J. Chayes, C. Gade, J. Hopcroft, V. S. Mirrokni, A. Prakash, T. Tao.

    22. •Optimal policies for distributed and strategic load balancing, with Y. Azar, K. Jain, and V. S. Mirrokni.

    23. • A Unified Approach to Secure Transactions and Reputation Systems, with C. Borgs, J. Chayes, K. Jain, N. Immorlica, V. S. Mirrokni.

    24. •Wireless LAN Cell-Breathing, with P. Bahl, M. Hajiaghayi, K. Jain, V. Mirrokni, L. Qiu, A. Saberi.

    25. •Confluent Flow Augmentation for Data Traffic Engineering, with R. Bhatia, N.Immorlica, T.Kimbrel, V. S. Mirrokni, S.Naor, and B.Schieber.
       

DBLP         Conferences and Journals      Tutorials      Patents