Jump to Content
Mohammad Mahdian

Mohammad Mahdian

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, desc
  • Year
  • Year, desc
    Preview abstract Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and to address this, Dasgupta recently introduced an optimization view-point of hierarchical clustering with pair- wise similarity information that spurred a line of work shedding light on old algorithms (e.g., Average-Linkage), but also designing new algorithms. Here, for the maximization dual of Dasgupta’s objec- tive (introduced by Moseley-Wang), we present polynomial-time 42.46% approximation algorithms that use Max-Uncut Bisection as a subroutine. The previous best worst-case approximation factor in polynomial time was 33.6%, improving only slightly over Average-Linkage which achieves 33.3%. Finally, we complement our positive results by providing APX-hardness (even for 0-1 similarities), under the Small Set Expansion hypothesis. View details
    Preview abstract As machine learning has become more and more integrated into our businesses and lifestyles, researchers have begun to recognize the necessity of ensuring machine learning systems are fair. Recently, there has been an interest in defining a notion of fairness that mitigates over-representation in traditional clustering. In this paper we extend this notion to hierarchical clustering, where the goal is to recursively partition the data to optimize a certain objective~\cite{dasgupta}. For various natural objectives, we obtain simple, efficient algorithms to find a provably good fair hierarchical clustering. Empirically, we show that our algorithms can find a fair hierarchical clustering, surprisingly, with only a negligible loss in the objective. View details
    Fair Correlation clustering
    23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020) (2020) (to appear)
    Preview abstract In this paper, we study correlation clustering under fairness constraints. Fair variants of k-median and k-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair correlation clustering under several important types of fairness constraints. Our results hinge on obtaining a fairlet decomposition for correlation clustering by introducing a novel combinatorial optimization problem. We define a fairlet decomposition with cost similar to the k-median cost and this allows us to obtain approximation algorithms for a wide range of fairness constraints. We complement our theoretical results with an in-depth analysis of our algorithms on real graphs where we show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms. View details
    Preview abstract Companies like Google and Microsoft run billions of auctions every day to sell advertising opportunities. Any change to the rules of these auctions can have a tremendous effect on the revenue of the company and the welfare of the advertisers and the users. Therefore, any change requires careful evaluation of its potential impacts. Currently, such impacts are often evaluated by running simulations or small controlled experiments. This, however, misses the important factor that the advertisers respond to changes. Our goal is to build a theoretical framework for predicting the actions of an agent (the advertiser) that is optimizing her actions in an uncertain environment. We model this problem using a variant of the multi armed bandit setting where playing an arm is costly. The cost of each arm changes over time and is publicly observable. The value of playing an arm is drawn stochastically from a static distribution and is observed by the agent and not by us. We, however, observe the actions of the agent. Our main result is that assuming the agent is playing a strategy with a regret of at most f(T) within the first T rounds, we can learn to play the multi-armed bandits game without observing the rewards) in such a way that the regret of our selected actions is at most O(k^4 (f(T) + 1) log(T)). View details
    Preview abstract Clustering is a fundamental problem in unsupervised machine learning. In many applications, clustering needs to be performed in presence of additional constraints, such as fairness or diversity constraints. In this paper, we formulate the problem of k-center clustering without over-representation, and propose approximation algorithms to solve the problem, as well as hardness results. We empirically evaluate our clusterings on real-world dataset and show that fairness can be obtained with limited effect on clustering quality. View details
    Incentive-Aware Learning for Large Markets
    Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pp. 1369-1378
    Preview abstract In a typical learning problem, one key step is to use training data to pick one model from a collection of models that optimizes an objective function. In many multi-agent settings, the training data is generated through the actions of the agents, and the model is used to make a decision (e.g., how to sell an item) that affects the agents. An illustrative example of this is the problem of learning the reserve price in an auction. In such cases, the agents have an incentive to influence the training data (e.g., by manipulating their bids in the case of an auction) to game the system and achieve a more favorable outcome. In this paper, we study such incentive-aware learning problem in a general setting and show that it is possible to approximately optimize the objective function under two assumptions: (i) each individual agent is a “small” (part of the market); and (ii) there is a cost associated with manipulation. For our illustrative application, this nicely translates to a mechanism for setting approximately optimal reserve prices in auctions where no individual agent has significant market share. For this application, we also show that the second assumption (that manipulations are costly) is not necessary since we can “perturb” any auction to make it costly for the agents to manipulate. View details
    Preview abstract In online advertising, advertisers purchase ad placements by participating in a long sequence of repeated auctions. One of the most important features advertising platforms often provide, and advertisers often use, is budget management, which allows advertisers to control their cumulative expenditures. Advertisers typically declare the maximum daily amount they are willing to pay, and the platform adjusts allocations and payments to guarantee that cumulative expenditures do not exceed budgets. There are multiple ways to achieve this goal, and each one, when applied to all budget-constrained advertisers simultaneously, steers the system toward a different equilibrium. While previous research focused on online stochastic optimization techniques or game-theoretic equilibria of such settings, our goal in this paper is to compare the ``system equilibria'' of a range of budget management strategies in terms of the seller's profit and buyers' utility. In particular, we consider six different budget management strategies including probabilistic throttling, thresholding, bid shading, reserve pricing, and multiplicative boosting. We show these methods admit a system equilibrium in a rather general setting, and prove dominance relations between them in a simplified setting. Our study sheds light on the impact of budget management strategies on the tradeoff between the seller's profit and buyers' utility. Finally, we also empirically compare the system equilibria of these strategies using real ad auction data in sponsored search and randomly generated bids. The empirical study confirms our theoretical findings about the relative performances of budget management strategies. View details
    Pricing a low-regret seller
    Hoda Heidari
    Sadra Yazdanbod
    Proceedings of the Thirty-Third International Conference on Machine Learning (ICML 2016)
    Preview abstract As the number of ad exchanges has grown, publishers have turned to low regret learning algorithms to decide which exchange offers the best price for their inventory. This in turn opens the following question for the exchange: how to set prices to attract as many sellers as possible and maximize revenue. In this work we formulate this precisely as a learning problem, and present algorithms showing that by simply knowing that the counterparty is using a low regret algorithm is enough for the exchange to have its own low regret learning algorithm to find the optimal price. View details
    Preview abstract In this paper we consider efficient construction of “composable core-sets” for basic diversity and coverage maximization problems. A core-set for a point-set in a metric space is a subset of the point-set with the property that an approximate solution to the whole point-set can be obtained given the core-set alone. A composable core-set has the property that for a collection of sets, the approximate solution to the union of the sets in the collection can be obtained given the union of the composable core-sets for the point sets in the collection. Using composable core-sets one can obtain effi- cient solutions to a wide variety of massive data processing applications, including nearest neighbor search, streaming algorithms and map-reduce computation. Our main results are algorithms for constructing composable core-sets for several notions of “diversity objective functions”, a topic that attracted a significant amount of research over the last few years. The composable core-sets we construct are small and accurate: their approximation factor almost matches that of the best “off-line” algorithms for the relevant optimization problems (up to a constant factor). Moreover, we also show applications of our results to diverse nearest neighbor search, streaming algorithms and map-reduce computation. Finally, we show that for an alternative notion of diversity maximization based on the maximum coverage problem small composable core-sets do not exist. View details
    Designing Markets for Daily Deals
    Yang Cai
    Bo Waggoner
    Conference on Web and Internet Economics (WINE) (2013) (to appear)
    Preview
    PageRank on an evolving graph
    Bahman Bahmani
    Ravi Kumar
    Eli Upfal
    KDD (2012), pp. 24-32
    Preview
    To match or not to match: economics of cookie matching in online advertising
    Arpita Ghosh
    Preston McAfee
    Proceedings of the 13th ACM Conference on Electronic Commerce, ACM, New York, NY, USA (2012), pp. 741-753
    Preview
    Ad auctions with data
    Hu Fu
    Patrick R. Jordan
    Inbal Talgam-Cohen
    INFOCOM Workshops (2012), pp. 184-189
    Preview
    Algorithms on evolving graphs
    Aris Anagnostopoulos
    Ravi Kumar
    Eli Upfal
    Fabio Vandin
    ITCS (2012), pp. 149-160
    TrustBets: betting over an IOU network
    Sharad Goel
    David M. Pennock
    Daniel M. Reeves
    AAMAS (2012), pp. 1319-1320
    Christmas Gift Exchange Games
    Arpita Ghosh
    Theory Comput. Syst., vol. 50 (2012), pp. 3-19
    Online Optimization with Uncertain Information
    Hamid Nazerzadeh
    Amin Saberi
    ACM Transactions on Algorithms, vol. 8 (2012), pp. 2
    The Multiple Attribution Problem in Pay-Per-Conversion Advertising
    Patrick R. Jordan
    Erik Vee
    SAGT (2011), pp. 31-43
    Fighting censorship with algorithms
    ACM Crossroads, vol. 18 (2011), pp. 41
    Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs
    STOC (2011), pp. 597-606
    Special Section on Foundations of Computer Science
    Scott Aaronson
    Jeff Erickson
    R. Ravi
    Emanuele Viola
    SIAM J. Comput., vol. 40 (2011), pp. 770
    Stochastic kronecker graphs
    Ying Xu 0002
    Random Struct. Algorithms, vol. 38 (2011), pp. 453-466
    Sorting and selection on dynamic data
    Aris Anagnostopoulos
    Ravi Kumar
    Eli Upfal
    Theor. Comput. Sci., vol. 412 (2011), pp. 2564-2576
    Value of Learning in Sponsored Search Auctions
    Sai-Ming Li
    Randolph Preston McAfee
    WINE (2010), pp. 294-305
    Advertisement allocation for generalized second-pricing schemes
    Ashish Goel
    Hamid Nazerzadeh
    Amin Saberi
    Oper. Res. Lett., vol. 38 (2010), pp. 571-576
    Fighting Censorship with Algorithms
    FUN (2010), pp. 296-306
    Secure Overlay Network Design
    Li (Erran) Li
    Algorithmica, vol. 57 (2010), pp. 82-96
    Dynamics of conversations
    Ravi Kumar
    Mary McGlohon
    KDD (2010), pp. 553-562
    Christmas Gift Exchange Games
    Arpita Ghosh
    FUN (2010), pp. 228-236
    Mechanism Design for Complexity-Constrained Bidders
    Ravi Kumar
    Amin Sayedi
    WINE (2009), pp. 513-520
    Approximating Matches Made in Heaven
    Ning Chen
    Nicole Immorlica
    Anna R. Karlin
    Atri Rudra
    ICALP (1) (2009), pp. 266-278
    Clustering-Based Bidding Languages for Sponsored Search
    Grant Wang
    ESA (2009), pp. 167-178
    Sort Me If You Can: How to Sort Dynamic Data
    Aris Anagnostopoulos
    Ravi Kumar
    Eli Upfal
    ICALP (2) (2009), pp. 339-350
    The Minimum Distance of Turbo-Like Codes
    Louay Bazzi
    Daniel A. Spielman
    IEEE Transactions on Information Theory, vol. 55 (2009), pp. 6-15
    Facility Location
    Karen Aardal
    Jaroslaw Byrka
    Encyclopedia of Algorithms (2008)
    Charity auctions on social networks
    Arpita Ghosh
    SODA (2008), pp. 1019-1028
    Rainbow solutions to the Sidon equation
    Jacob Fox
    Rados Radoicic
    Discrete Mathematics, vol. 308 (2008), pp. 4773-4778
    Deterministic Decentralized Search in Random Graphs
    Esteban Arcaute
    Ning Chen
    Ravi Kumar
    David Liben-Nowell
    Hamid Nazerzadeh
    Ying Xu 0002
    Internet Mathematics, vol. 5 (2008), pp. 141-154
    A Cascade Model for Externalities in Sponsored Search
    David Kempe
    WINE (2008), pp. 585-596
    Influence and correlation in social networks
    Aris Anagnostopoulos
    Ravi Kumar
    KDD (2008), pp. 7-15
    Limitations of cross-monotonic cost-sharing schemes
    Nicole Immorlica
    ACM Transactions on Algorithms, vol. 4 (2008)
    Externalities in online advertising
    Arpita Ghosh
    WWW (2008), pp. 161-168
    The Secretary Problem with a Hazard Rate Condition
    Randolph Preston McAfee
    David Pennock
    WINE (2008), pp. 708-715
    The role of compatibility in the diffusion of technologies through social networks
    Nicole Immorlica
    Jon M. Kleinberg
    Tom Wexler
    ACM Conference on Electronic Commerce (2007), pp. 75-83
    Stochastic Kronecker Graphs
    Ying Xu 0002
    WAW (2007), pp. 179-186
    Towards a pay-per-action model in sponsored search
    Kerem Tomak
    ICEC (2007), pp. 87-88
    Pay-per-action Model for Online Advertising
    Kerem Tomak
    WINE (2007), pp. 549-557
    Dynamics of bid optimization in online advertisement auctions
    Christian Borgs
    Jennifer T. Chayes
    Nicole Immorlica
    Kamal Jain
    Omid Etesami
    WWW (2007), pp. 531-540
    Balloon Popping With Applications to Ascending Auctions
    Nicole Immorlica
    Anna R. Karlin
    Kunal Talwar
    FOCS (2007), pp. 104-112
    Deterministic Decentralized Search in Random Graphs
    Esteban Arcaute
    Ning Chen
    Ravi Kumar
    David Liben-Nowell
    Hamid Nazerzadeh
    Ying Xu 0002
    WAW (2007), pp. 187-194
    Robust Combinatorial Optimization with Exponential Scenarios
    Uriel Feige
    Kamal Jain
    IPCO (2007), pp. 439-453
    Allocating online advertisement space with unreliable estimates
    Hamid Nazerzadeh
    Amin Saberi
    ACM Conference on Electronic Commerce (2007), pp. 288-294
    Mechanism Design on Trust Networks
    Arpita Ghosh
    Daniel M. Reeves
    David M. Pennock
    Ryan Fugger
    WINE (2007), pp. 257-268
    Game-Theoretic Aspects of Designing Hyperlink Structures
    Nicole Immorlica
    Kamal Jain
    WINE (2006), pp. 150-161
    Secretary Problems with Competing Employers
    Nicole Immorlica
    Robert D. Kleinberg
    WINE (2006), pp. 389-400
    Finding small balanced separators
    Uriel Feige
    STOC (2006), pp. 375-384
    Secure Overlay Network Design
    Erran L. Li
    AAIM (2006), pp. 354-366
    Approximation Algorithms for Metric Facility Location Problems
    Yinyu Ye
    Jiawei Zhang
    SIAM J. Comput., vol. 36 (2006), pp. 411-432
    Comparing Partial Rankings
    Ronald Fagin
    Ravi Kumar
    D. Sivakumar
    Erik Vee
    SIAM J. Discrete Math., vol. 20 (2006), pp. 628-648
    Random popular matchings
    ACM Conference on Electronic Commerce (2006), pp. 238-242
    Multi-unit auctions with unknown supply
    Amin Saberi
    ACM Conference on Electronic Commerce (2006), pp. 243-249
    Multi-unit auctions with budget-constrained bidders
    Christian Borgs
    Jennifer T. Chayes
    Nicole Immorlica
    Amin Saberi
    ACM Conference on Electronic Commerce (2005), pp. 44-51
    Limitations of cross-monotonic cost sharing schemes
    Nicole Immorlica
    SODA (2005), pp. 602-611
    Marriage, honesty, and stability
    Nicole Immorlica
    SODA (2005), pp. 53-62
    Cycle Cover with Short Cycles
    Nicole Immorlica
    STACS (2005), pp. 641-653
    Click Fraud Resistant Methods for Learning Click-Through Rates
    Nicole Immorlica
    Kamal Jain
    Kunal Talwar
    WINE (2005), pp. 34-45
    Computing Equilibria in a Fisher Market with Linear Single-Constraint Production Units
    Kamal Jain
    WINE (2005), pp. 788-792
    Minimizing Makespan in No-Wait Job Shops
    Nikhil Bansal
    Maxim Sviridenko
    Math. Oper. Res., vol. 30 (2005), pp. 817-831
    Online auctions with re-usable goods
    Mohammad Taghi Hajiaghayi
    Robert D. Kleinberg
    David C. Parkes
    ACM Conference on Electronic Commerce (2005), pp. 165-174
    Comparing and Aggregating Rankings with Ties
    Ronald Fagin
    Ravi Kumar
    D. Sivakumar
    Erik Vee
    PODS (2004), pp. 47-58
    Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games
    Lisa Fleischer
    Kamal Jain
    FOCS (2004), pp. 277-285
    Further Improvements in Competitive Guarantees for QoS Buffering
    Nikhil Bansal
    Lisa Fleischer
    Tracy Kimbrel
    Baruch Schieber
    Maxim Sviridenko
    ICALP (2004), pp. 196-207
    On the forced matching numbers of bipartite graphs
    Peter Adams
    Ebadollah S. Mahmoodian
    Discrete Mathematics, vol. 281 (2004), pp. 1-12
    Exploring the community structure of newsgroups
    Christian Borgs
    Jennifer T. Chayes
    Amin Saberi
    KDD (2004), pp. 783-787
    Optimizing the Placement of Internet TAPs in Wireless Neighborhood Networks
    Ranveer Chandra
    Lili Qiu
    Kamal Jain
    ICNP (2004), pp. 271-282
    Packing Steiner trees
    Kamal Jain
    Mohammad R. Salavatipour
    SODA (2003), pp. 266-274
    Universal Facility Location
    Martin Pál
    ESA (2003), pp. 409-421
    The facility location problem with general cost functions
    Mohammad Taghi Hajiaghayi
    Networks, vol. 42 (2003), pp. 42-47
    A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem
    Yingyu Ye
    Jiawei Zhang
    RANDOM-APPROX (2003), pp. 129-140
    Rainbow Arithmetic Progressions and Anti-Ramsey Results
    Veselin Jungic
    Jacob Licht
    Jaroslav Nesetril
    Rados Radoicic
    Combinatorics, Probability & Computing, vol. 12 (2003), pp. 599-620
    Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
    Kamal Jain
    Evangelos Markakis
    Amin Saberi
    Vijay V. Vazirani
    J. ACM, vol. 50 (2003), pp. 795-824
    Approximating Market Equilibria
    Kamal Jain
    Amin Saberi
    RANDOM-APPROX (2003), pp. 98-108
    Improved Approximation Algorithms for Metric Facility Location Problems
    Yinyu Ye
    Jiawei Zhang
    APPROX (2002), pp. 229-242
    Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP
    Kamal Jain
    Evangelos Markakis
    Amin Saberi
    Vijay V. Vazirani
    CoRR, vol. cs.DS/0207028 (2002)
    A new greedy approach for facility location problems
    Kamal Jain
    Amin Saberi
    STOC (2002), pp. 731-740
    On the computational complexity of strong edge coloring
    Discrete Applied Mathematics, vol. 118 (2002), pp. 239-248
    Length-constrained path-matchings in graphs
    Mohammad Ghodsi
    Mohammad Taghi Hajiaghayi
    Networks, vol. 39 (2002), pp. 210-215
    A Greedy Facility Location Algorithm Analyzed Using Dual Fitting
    Evangelos Markakis
    Amin Saberi
    Vijay V. Vazirani
    RANDOM-APPROX (2001), pp. 127-137
    The strong chromatic index of C4-free graphs
    Random Struct. Algorithms, vol. 17 (2000), pp. 357-375
    On a conjecture of Keedwell and the cycle double cover conjecture
    Ebadollah S. Mahmoodian
    Amin Saberi
    Mohammad R. Salavatipour
    Ruzbeh Tusserkani
    Discrete Mathematics, vol. 216 (2000), pp. 287-292
    A Characterization of Uniquely 2-List Colorable Graphs
    Ebadollah S. Mahmoodian
    Ars Comb., vol. 51 (1999)