# Mohammad Mahdian

Authored Publications

Google Publications

Other Publications

Sort By

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection

Vaggos Chatziafratis

AISTATS, AISTATS, AISTATS (2020), AISTATS (to appear)

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

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

Fair Hierarchical Clustering

Benjamin Moseley

Marina Knittel

Yuyan Wang

Neurips 2020

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

Response Prediction for Low-Regret Agents

Sadra Yazdanbod

Web and Internet Economics 2019

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

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

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

Designing Markets for Daily Deals

Preview
Yang Cai

Bo Waggoner

Conference on Web and Internet Economics (WINE) (2013) (to appear)

Ad auctions with data

Preview
Hu Fu

Patrick R. Jordan

Inbal Talgam-Cohen

INFOCOM Workshops (2012), pp. 184-189

To match or not to match: economics of cookie matching in online advertising

Preview
Arpita Ghosh

Preston McAfee

Proceedings of the 13th ACM Conference on Electronic Commerce, ACM, New York, NY, USA (2012), pp. 741-753

Algorithms on evolving graphs

Christmas Gift Exchange Games

TrustBets: betting over an IOU network

Online Optimization with Uncertain Information

Sorting and selection on dynamic data

Aris Anagnostopoulos

Ravi Kumar

Eli Upfal

Theor. Comput. Sci., vol. 412 (2011), pp. 2564-2576

Fighting censorship with algorithms

ACM Crossroads, vol. 18 (2011), pp. 41

Special Section on Foundations of Computer Science

Scott Aaronson

Jeff Erickson

R. Ravi

Emanuele Viola

SIAM J. Comput., vol. 40 (2011), pp. 770

Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs

The Multiple Attribution Problem in Pay-Per-Conversion Advertising

Stochastic kronecker graphs

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

Value of Learning in Sponsored Search Auctions

Secure Overlay Network Design

Dynamics of conversations

Christmas Gift Exchange Games

Sort Me If You Can: How to Sort Dynamic Data

Mechanism Design for Complexity-Constrained Bidders

Approximating Matches Made in Heaven

The Minimum Distance of Turbo-Like Codes

Louay Bazzi

Daniel A. Spielman

IEEE Transactions on Information Theory, vol. 55 (2009), pp. 6-15

Clustering-Based Bidding Languages for Sponsored Search

Externalities in online advertising

A Cascade Model for Externalities in Sponsored Search

Charity auctions on social networks

Rainbow solutions to the Sidon equation

Influence and correlation in social networks

Facility Location

The Secretary Problem with a Hazard Rate Condition

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

Limitations of cross-monotonic cost-sharing schemes

Mechanism Design on Trust Networks

Arpita Ghosh

Daniel M. Reeves

David M. Pennock

Ryan Fugger

WINE (2007), pp. 257-268

Balloon Popping With Applications to Ascending Auctions

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

Stochastic Kronecker Graphs

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

Towards a pay-per-action model in sponsored search

Pay-per-action Model for Online Advertising

Dynamics of bid optimization in online advertisement auctions

Christian Borgs

Jennifer T. Chayes

Nicole Immorlica

Kamal Jain

Omid Etesami

WWW (2007), pp. 531-540

Allocating online advertisement space with unreliable estimates

Hamid Nazerzadeh

Amin Saberi

ACM Conference on Electronic Commerce (2007), pp. 288-294

Comparing Partial Rankings

Ronald Fagin

Ravi Kumar

D. Sivakumar

Erik Vee

SIAM J. Discrete Math., vol. 20 (2006), pp. 628-648

Game-Theoretic Aspects of Designing Hyperlink Structures

Secretary Problems with Competing Employers

Approximation Algorithms for Metric Facility Location Problems

Finding small balanced separators

Random popular matchings

ACM Conference on Electronic Commerce (2006), pp. 238-242

Secure Overlay Network Design

Multi-unit auctions with unknown supply

Marriage, honesty, and stability

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

Computing Equilibria in a Fisher Market with Linear Single-Constraint Production Units

Minimizing Makespan in No-Wait Job Shops

Online auctions with re-usable goods

Mohammad Taghi Hajiaghayi

Robert D. Kleinberg

David C. Parkes

ACM Conference on Electronic Commerce (2005), pp. 165-174

Cycle Cover with Short Cycles

Click Fraud Resistant Methods for Learning Click-Through Rates

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

Optimizing the Placement of Internet TAPs in Wireless Neighborhood Networks

Further Improvements in Competitive Guarantees for QoS Buffering

Nikhil Bansal

Lisa Fleischer

Tracy Kimbrel

Baruch Schieber

Maxim Sviridenko

ICALP (2004), pp. 196-207

Comparing and Aggregating Rankings with Ties

Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games

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

Rainbow Arithmetic Progressions and Anti-Ramsey Results

Veselin Jungic

Jacob Licht

Jaroslav Nesetril

Rados Radoicic

Combinatorics, Probability & Computing, vol. 12 (2003), pp. 599-620

A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem

Approximating Market Equilibria

Packing Steiner trees

The facility location problem with general cost functions

Universal Facility Location

Improved Approximation Algorithms for Metric Facility Location Problems

A new greedy approach for facility location problems

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)

Length-constrained path-matchings in graphs

Mohammad Ghodsi

Mohammad Taghi Hajiaghayi

Networks, vol. 39 (2002), pp. 210-215

On the computational complexity of strong edge coloring

Discrete Applied Mathematics, vol. 118 (2002), pp. 239-248

A Greedy Facility Location Algorithm Analyzed Using Dual Fitting

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