Publications

Manuscripts (in preparation, or submitted for publication)

1. David Kempe and Mohammad Mahdian, Cascade Model for Externalities in Sponsored Search, 2008.
   One of the most important yet not well-studied issues in online advertising is the externality effect among ads: the value of an ad impression on a page is affected not just by the location that the ad is placed in, but also by the set of other ads displayed on the page. Ghosh and Mahdian proposed a user-choice-based model for this phenomenon primarily in the context of lead generation advertising. In this paper, we propose a model for externalities in sponsored search ads, and give polynomial-time incentive-compatible auction mechanisms for allocating and pricing ad slots in this model. Our model is based on a model recently evaluated and proven to work well for measuring click-through rates among search results. We also consider generalizations of our model, including a common generalization of our model and the commonly-used separable click-through rate model, and give algorithms that find near optimal allocations for these models.
2. Ashish Goel, Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi Advertisement Allocation for Generalized Second Pricing Schemes, 2008.
   Recently, there has been a surge of interest in algorithms that allocate advertisement space in an online revenue-competitive manner. Most such algorithms, however, assume a pay-as-you-bid pricing scheme. As we will observe in this paper, these algorithms fail to achieve a bounded competitive ratio if the ad space is priced using the well-known and widely-used generalized second price (GSP) scheme. In this paper, we study the problem of online ad space allocation for the GSP scheme. First, we prove that if the model is changed to allow the mechanism to give out free impressions, the idea behind the algorithm of Mehta et al. can be combined with a dynamic programming subroutine to obtain a (1-1/e) competitive ratio for the problem. In fact, this result holds for a much more general class of pricing schemes, including the VCG scheme. In the original model, which does not allow the mechanism to give out free impressions, we are able to modify the natural greedy algorithm to achieve a competitive factor of 1/3. We will show that this analysis is tight, and that no algorithm can achieve a factor better than 1/2 compared to the optimal solution in the model with free impressions.
3. Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian, and Atri Rudra, Approximating Matches Made in Heaven, 2007.
   In this paper we investigate a stochastic matching problem motivated in the context of online matchmaking services and kidney exchange.
4. Louay Bazzi, Mohammad Mahdian, and Daniel Spielman, The Minimum Distance of Turbo-Like Codes, to appear in the IEEE Transactions on Information Theory, 2003.
   This paper reduces the problem of finding the minimum distance of several classes of Turbo-like codes to an extremal hypergraph problem. As a result, we get tight bounds on the minimum distance of several classes of Turbo-like codes, which prove that they are asymptotically bad. We also show that the Turbo-like code obtained by serially concatenating a repeat-3-times code with two accumulators (through random interleavers) is asymptotically good.

Publications

1. Aris Anagnostopoulos, Ravi Kumar, and Mohammad Mahdian, Influence and Correlation in Social Networks, to appear in the Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2008.
   In many social systems, social ties between users play an important role in dictating users' behavior. One of the ways this can happen is through social influence, the phenomenon that the actions of a user can induce his/her friends to behave in a similar way. Identifying and understanding social influence is of tremendous interest from both an analysis (e.g., predicting the future of the system) and a design (e.g., designing viral marketing strategies) point of view. This is a difficult task in general, since there are many other factors that can induce statistical correlation between the actions of friends in a social network.
   In this paper, we propose two simple tests that can identify influence as a source of social correlation in cases where data on the time step of actions are available. We give a theoretical justification of one of the tests by proving that with high probability it succeeds in ruling out influence in a rather general model of social correlation. We also simulate our tests on a number of examples designed by randomly generating actions of nodes on a real social network (from Flickr) according to one of several models. Finally, we apply them to real tagging data on Flickr, exhibiting that while there is significant social correlation in tagging behavior on this system, this correlation cannot be attributed to social influence.
2. Arpita Ghosh and Mohammad Mahdian, Externalities in Online Advertising, Proceedings of the 17th International World Wide Web Conference (WWW), 2008.
   Most models for online advertising assume that each ad has an inherent clickthrough- rate/conversion-rate, regardless of other ads served in the same session. This ignores an important externality effect: as the advertising audience has a limited attention span, a high-quality ad on a page can detract attention from other ads on the same page. In this paper, we propose an online advertising model that takes this effect into account, and studying the winner determination problem in this model. Our models are based on choice models on the audience side. We show that in the most general case, the winner determination problem is hard even to approximate. However, there are some interesting special cases and simplified models, such as the case where the audience preferences are single peaked, where the problem can be solved efficiently. In such cases, the winner determination algorithm can be combined with standard VCG techniques to yield truthful mechanisms.
3. Arpita Ghosh and Mohammad Mahdian, Charity Auctions on Social Networks, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.
   A common way to encourage individuals to donate to charities is by offering to match their contribution (often by their employer or by the government). Conitzer and Sandholm introduced the idea of using auctions to allow individuals to offer to match the contribution of others. We explore this idea in a social network setting, where individuals care about the contribution of their neighbors, and are allowed to specify contributions that are conditional on the contribution of their neighbors. We give a mechanism for this setting that raises the largest individually rational contributions given the conditional bids, and analyze the equilibria of this mechanism in the case of linear utilities. We show that if the social network is strongly connected, the mechanism always has an equilibrium that raises the maximum total contribution (which is the contribution computed according to the true utilities), and characterize social networks for which a non-zero equilibrium exists in terms of the largest eigenvalue of the associated utility matrix.
4. Kamal Jain and Mohammad Mahdian, Cost Sharing, In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors. Cambridge University Press, 2007.
   This is chapter 15 of the book 'Algorithmic Game Theory'. This chapter gives an introductory survey of results on cost sharing in the computer science literature. We discuss core of cooperative games, cross-monotonic cost-sharing schemes and group-strategyproof mechanisms, primal-dual techniques for constructing cost-sharing schemes for combinatorial optimization games, limitations of cross-monotonic cost-sharing schemes, the Shapley value, and the Nash bargaining solution.
5. Arpita Ghosh, Mohammad Mahdian, David M. Pennock, Daniel M. Reeves, and Ryan Fugger, Mechanism Design on Trust Networks, Proceedings of the 3rd international Workshop on Internet and Network Economics (WINE), 2007.
   We introduce the concept of a trust network -- a decentralized payment infrastructure in which payments are routed as IOUs between trusted entities. The network structure introduces group budget constraints on the payments from a subset of agents to another on the trust network: this generalizes the notion of individually budget constrained bidders. We consider a multi-unit auction of identical items among bidders with unit demand, when the auctioneer and bidders are all nodes on a trust network. We define a generalized notion of social welfare for such budget-constrained bidders, and show that the winner determination problem under this notion of social welfare is NP-hard; however the flow structure in a trust network can be exploited to approximate the solution with a factor of 1-1/e. Furthermore, this can be turned into an incentive compatible mechanism.
6. Mohammad Mahdian and Ying Xu, Stochastic Kronecker Graphs, Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW), 2007. Tech report version
   A random graph model based on Kronecker products of probability matrices was recently proposed by Leskovec et al. as a generative model for large-scale real-world networks such as the web. This model simultaneously captures several well-known properties of real-world networks; in particular, it gives rise to a heavy-tailed degree distribution, has a low diameter, and obeys the densification power law. Most properties of Kronecker products of graphs (such as connectivity and diameter) are only rigorously analyzed in the deterministic case. In this paper, we study the basic properties of stochastic Kronecker products based on an initiator matrix of size two (which is the case that is shown to provide the best fit to many real-world networks). We show a phase transition for the emergence of the giant component and another phase transition for connectivity, and prove that such graphs have constant diameters beyond the connectivity threshold, but are not searchable using a decentralized algorithm.
7. Esteban Arcaute, Ning Chen, Ravi Kumar, David Liben-Nowell, Mohammad Mahdian, Hamid Nazerzadeh, and Ying Xu, Deterministic Decentralized Search in Random Graphs, Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW), 2007.
   This paper considers a general framework for decentralized search in random graphs. We give a characterization of graphs that are searchable using deterministic memoryless algorithms that use only local information to reach their destination in a bounded number of steps in expectation (this includes Kleinberg's algorithm for long-range percolation and heirarchical network models). We also use this characterization to prove a monotonicity property for searchability in our model.
8. Mohammad Mahdian and Kerem Tomak, Pay-per-action model for online advertising, Proceedings of the 3rd international Workshop on Internet and Network Economics (WINE), 2007.
   Also presented at the First International Workshop on Data Mining and Audience Intelligence for Advertising (ADKDD), August 2007.
   The online advertising industry is currently based on two dominant business models: the pay-per-impression model and the pay-per-click model. With the growth of sponsored search during the last few years, there has been a move toward the pay-per-click model as it decreases the risk to small advertisers. An alternative model, discussed but not widely used in the advertising industry, is pay-per-conversion, or more generally, pay-per-action. In this paper, we discuss various challenges involved in designing mechanisms for the pay-per-action model, and approaches to tackle some of them.
9. Nicole Immorlica, Anna Karlin, Mohammad Mahdian, and Kunal Talwar, Balloon Popping with Applications to Ascending Auctions, Proceedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
   We study the following puzzle in this paper: we are given n balloons, with capacities 1, 1/2, ..., 1/n. However, the balloons are indistinguishable, and we do not know the capacity of each balloon. We are allowed to inflate the balloons in any order we wish, but as soon as we inflate a balloon to a value beyond its capacity, it pops. The challenge is to come up with a (randomized) strategy wich maximizes the (expected) total volume of air in the balloons. A nice illustration of this problem can be found in Jeff Erickson's blog. This problem is motivated by the study of the power of ascending auctions for selling identical goods to unit-demand buyers. Our result shows that in this setting, a mechanism due to Moulin is within a constant factor of the optimal mechanism.
10. Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi, Allocating online advertisement space with unreliable estimates, Proceedings of the 8th ACM conference on Electronic commerce, 288-294, 2007.
    This paper studies the following online optimization problem faced by online ad publishers like Google or Yahoo: An online ad publisher receives a stream of opportunities to display advertisement (e.g., every time a user searches for a query, they get to show ads alongside the search results), and upon receiving each opportunity, they must decide to which advertiser they must allocate the ad slot. The problem is complicated by the fact that advertisers usually have a limited budget and therefore the ad publisher would like to optimize the allocation of these budgets in order to maximize the revenue. This problem was studied in an online competitive analysis framework by Mehta et al. One of the shortcomings of this framework is that it is too pessimistic: it ignores any historical estimates of the frequency of receiving different advertising opportunities, and instead optimizes for the worst case. In this paper, we address this issue by introducing a framework for online optimization in presence of unreliable estimates. We give an algorithm that acheives two goals simultaneously: it provides a worst-case guarantee for cases where the estimates are totally incorrect, and a better performance guarantee in the case that the estimates are accurate. We also apply this framework to several other online optimization problems.
11. Nicole Immorlica, Jon Kleinberg, Mohammad Mahdian, and Tom Wexler, The role of compatibility in the diffusion of technologies in social networks, Proceedings of the 8th ACM conference on Electronic commerce, 75-83, 2007.
    This paper considers the effect of compatibility on how competing technologies (for example, instant messaging softwares) spread through a social network. Our model builds on work on the diffusion of innovations in the economics literature, which seeks to model how a new technology A might spread through a social network of individuals who are currently users of technology B. We consider several ways of capturing the compatibility of A and B, focusing primarily on a model in which users can choose to adopt A, adopt B, or - at an extra cost - adopt both A and B. We characterize how the ability of A to spread depends on both its quality relative to B, and also this additional cost of adopting both, and find some surprising non-monotonicity properties in the dependence on these parameters: in some cases, for one technology to survive the introduction of another, the cost of adopting both technologies must be balanced within a narrow, intermediate range. We also extend the framework to the case of multiple technologies, where we find that a simple model captures the phenomenon of two firms adopting a limited "strategic alliance" to defend against a new, third technology.
12. Uriel Feige, Kamal Jain, Mohammad Mahdian, and Vahab Mirrokni, Robust combinatorial optimization with Exponential Scenarios, Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science 4513, 439-453, June 2007.
    This paper studies a framework for demand-robust two-stage combinatorial optimization problems in settings where the number of possible scenarios is exponential. We give an LP-based approach for several covering problems. A major component of this algorithm is a subroutine that finds a subset of the given universe that maximizes its minimum cost of covering. We establish an interesting connection between this style of max-min optimization and competitive online algorithms for the underlying covering problem. This connection is used to design algorithms for problems such as set cover and vertex cover.
13. Christian Borgs, Jennifer Chayes, Omid Etesami, Nicole Immorlica, Kamal Jain, and Mohammad Mahdian, Dynamics of Bid Optimization in Online Advertisement Auctions, The 16th International World Wide Web Conference (WWW), 2007.
    We study algorithms for optimizing bids in advertisement auctions like those of Google and Overture, and their behavior in equilibrium. In particular, we show that in a system where the bidders use a bid optimization algorithm based on equalizing return on investments and the auction mechanism is a perturbed variant of the first price auction, the prices of the goods will converge to the market equilibrium prices.
14. Nicole Immorlica, Robert Kleinberg and Mohammad Mahdian. Secretary problems with competing employers, Proceedings of the 2nd international Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 4286, 389-400, 2006.
    This paper studies a game-theoretic variant of the classical secretary problem where several employers compete to hire the best secretary from a sequence of candidate that arrive online.
15. Nicole Immorlica, Kamal Jain, and Mohammad Mahdian, Game-Theoretic Aspects of Designing Hyperlink Structures, Proceedings of the 2nd international Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 4286, 150-161, 2006.
    We study the problem of designing the hyperlink structure between the web pages of a web site in order to maximize the revenue generated from the traffic on the web site. First, we observe that the optimization problem can be solved using algorithms for solving Markov Decision Processes. Next, we study the problem from the perspective of cooperative game theory, when each web page is controlled by a different agent. We use a linear programming formuation of the problem to show that the core of this game is non-empty, when modeled as a TU game. For the NTU setting, we show that if mixed strategies are allowed, the core of the game is non-empty, but it can be highly inefficient.
16. Li Li, Mohammad Mahdian, and Vahab Mirrokni, Secure Overlay Network Design, Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), Lecture Notes in Computer Science 4041, 354-366, 2006.
    In this paper we study the following network design problem motivated by the design of secure overlay networks: the network is a bipartite graph with servelets on one side and access points on the other. If an access point is attacked, all the servelets connected to it will be compromised. An access point will be blocked if all servelets connected to it are compromised. The problem is to design the connections between servelets and access points in such a way to minimize the number of blocked access points, under various models of attack.
17. Mohammad Mahdian and Amin Saberi, Multi-unit auctions with unknown supply, Proceedings of the 7th ACM Conference on Electronic Commerce (EC’06), 243-249, 2006.
    We study a multi-unit auction for a perishable item where an unknown number of items arrive online. This setting is motivated by advertisement auctions, where the supply (ad space on pages) is not known in advance. In this model, we design approximately revenue-maximizing auctions using an online algorithm similar to an algorithm used for the ski-rental problem.
18. Mohammad Mahdian, Random Popular Matchings, Proceedings of the 7th ACM Conference on Electronic Commerce (EC’06), 238-242, 2006.
    In this paper, we consider matching markets where a centralized authority must find a matching between the agents on one side of the market, and the items on the other side. Such settings occur, for example, in mail-based DVD rental services such as NetFlix or in some job markets. The objective is to find a popular matching, or a matching that is prefered by a majority of the agents to any other matching. The main drawback of this concept is that popular matchings sometimes do not exist. We partially address this issue in this paper, by proving that in a probabilistic setting where preference lists are drawn at random and the number of items is more than the number of agents by a small multiplicative factor, popular matchings almost surely exist. Our proof uses a characterization result by Abraham et al., and a number of tools from the theory of random graphs and phase transitions.
19. Uriel Feige and Mohammad Mahdian, Finding small balanced separators, Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 375-384, 2006.
    An a-separator in a graph is a set of vertices whose removal partitions the graph into connected components of size smaller than an. Finding an a-separator of size at most k is NP-hard. Moreover, under reasonable complexity theoretic assumptions, it is shown that this problem is not polynomially solvable even when k = O(log n). In this paper, we give a randomized algorithm that for every epsilon>0, finds an a-separator of size k in the given graph, unless the graph contains an (a+epsilon)-separator of size strictly less than k, in which case our algorithm finds one such separator. In other words, the only instances where our algorithm fails to find the optimal a-separator are those that contain other separators with strictly smaller size though slightly worse balance. The running time of our algorithm is poly(n)*2^{O(k)}, which is polynomial for k = O(log n). Our proof is based on a simplified and improved adaptation of the techniques used by Kleinberg (FOCS 2000), together with a dynamic programming algorithm based on a novel decomposition lemma. As a by-product, our proof improves the best known bound on the size of a detection set for network failures, answering an open question posed by Kleinberg. We also show other applications of our proof techniques to other problems in approximation algorithms and rigorous analysis of heuristics.
20. Ron Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee, Comparing Partial Rankings, SIAM Journal on Discrete Mathematics 20 (3), 628-648, 2006.
    We provide a comprehensive picture of how to compare partial rankings, that is, rankings that allow ties. We propose several metrics to compare partial rankings, and prove that they are within constant multiples of each other.
21. Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang, Approximation Algorithms for Metric Facility Location Problems, SIAM Journal on Computing 36 (2), 411-432, 2006.
    This paper is the merged journal version of two APPROX papers. In this paper, we give the best known approximation algorithms for two problems: the metric facility location problem, and the soft-capacitated facility location problem.
22. Nicole Immorlica, Kamal Jain, Mohammad Mahdian, and Kunal Talwar, Click Fraud Resistant Methods for Learning Click-Through Rates, Proceedings of the First InternationalWorkshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828, 34-45, 2005.
    Most of today's online advertising business (such as Google and Overture) works based on pay-per-click auctions. Such systems often learn a parameter called click-through rate (CTR), and rank bidders based on their bid times their CTR. In this way, in expectation, the system behaves like a pay-per-impression system, where each advertiser pays an amount equal to her bid times her CTR every time her ad is displayed. It is well-known that pay-per-impression systems are less prone to fraud. Therefore, one might expect a pay-per-click system to be resistant to fraud in expectation. In this paper, we observe that this conclusion is not necessarily true, since an adversary can create fluctuation in the CTR and take advantage of the fact that the CTR learning algorithm does not adapt quickly to such fluctuations to cause harm to the advertiser. Then, we define a class of CTR learning algorithms called click-based algorithms and prove that click-based learning algorithms are resistant to such attacks. We give examples demonstrating that many natural non-click-based algorithms are not resistant to such attacks.
23. Kamal Jain, and Mohammad Mahdian, Computing equilibria in a Fisher market with linear single-constraint production units, Proceedings of the First International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828, 788-792, 2005.
    In this paper we give a simple reduction from the problem of computing market equilibrium prices in a Fisher economy with linear utilities and linear single-constraint production units to the same problem without production units.
24. Nikhil Bansal, Mohammad Mahdian, and Maxim Sviridenko, Minimizing makespan in no-wait job shops, Mathematics of Operations Research, 30 (4), 817-831, November 2005.
    In this paper we study approximation schemes for the remaining cases of the no-wait job shop scheduling problem. Specifically, we prove that when each job has at most two operations, this problem admits a PTAS when the number of machines is a constant, and is hard to approximate within a factor better than 5/4 if the number of machines is part of the input.
25. MohammadTaghi Hajiaghayi, Robert Kleinberg, Mohammad Mahdian, and David Parkes, Online Auctions with Re-usable Goods, Proceedings of the 6th ACM Conference on Electronic Commerce (EC’05), 165-174, 2005.
    In this paper we study mechanisms for online scheduling in a setting where agents bid for access to a re-usable good such as one unit of processing time on a machine. We seek mechanisms that are strategyproof with respect to agents' values, arrival times, and departure times. Without any assumption about arrival and departure times, Nissan and Lavi showed that there is no constant-competitive mechanism for this problem. However, in this paper we show that if agents cannot announce a departure time later than their true departure time, then it is possible to achieve a competitive ratio of 2, and this is the best possible. Furthermore, for this model, we give a general characterization of strategyproof mechanisms and tight results on the maximum revenue of such a mechanism.
26. Christian Borgs, Jennifer Chayes, Nicole Immorlica, Mohammad Mahdian, and Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM Conference on Electronic Commerce (EC’05), 44-51, 2005.
    In this paper, we consider the problem of a multi-unit auction with multiple bidders, each of whom has private valuation and budget. We prove an impossibility result assuming the axiom of independence of independent alternatives, and a constructive positive result for the existence of revenue-maximizing truthful auctions in this setting.
27. Nicole Immorlica, Mohammad Mahdian, and Vahab Mirrokni, Cycle Cover with Short Cycles, Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 3404, 641-653, 2005.
    We give a 1+ln(2) approximation algorithm for the problem of covering a subset of edges of a weighted graph with cycles of size at most k such that the total weight of the cycles is minimized. This problem (a.k.a. the lane covering problem) is motivated by its applications in operations research, and our result is the first non-trivial approximation guarantee for this problem. Our proof is based on interpreting a simple greedy algorithm (proposed and empirically analyzed by Ergun, Kuyzu, and Savelsbergh) as a dual-fitting algorithm, and analyzing its approximation ratio using a factor-revealing non-linear program. We show that our analysis is tight, and that the problem is APX-hard. We also consider several extensions of the problem, and propose approximation algorithms for these extensions.
28. Nicole Immorlica, and Mohammad Mahdian, Marriage, Honesty, and Stability, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 53-62, 2005.
    In this paper we study incentive issues in stable marriage mechanisms, and prove a generalization of a conjecture by Roth and Peranson regarding incentives in stable mechanisms with random preference lists. More precisely, we prove that in a probabilistic setting where each woman has an arbitrary complete preference list of men, and each man has a preference list of a constant number of women chosen independently at random from an arbitrary fixed distribution, then with probability approaching one (as the number of participants tend to infinity) truthfulness is (in some sense) the best strategy for any given participant.
29. Nicole Immorlica, Mohammad Mahdian, and Vahab Mirrokni, Limitations of Cross-monotonic Cost Sharing Schemes, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 602-611, 2005. (Winner of the best student paper award in SODA 2005)
    In this work we prove lower bounds for cross-monotonic cost sharing schemes (beyond the lower bounds given by the integrality gap of the corresponding LP relaxation) for various combinatorial optimization problems. In particular, we prove that there is no cross-monotonic cost sharing scheme for the facility location problem covering more than a third of the total cost, thereby showing that a recent scheme given by Pal and Tardos is best possible. As another example, we show strong negative results for cross-monotonic cost sharing schemes for the problems of set cover and vertex cover. We also study the implications of our results on group-strategyproof mechanisms for these problems.
30. Lisa K. Fleischer, Kamal Jain, and Mohammad Mahdian, Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games, Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), 277-285, 2004.
    In this paper we prove that in a multicommodity network, there exists a set of taxes (a.k.a. tolls) that enforce a system optimal flow. This answers an open question of Cole, Dodis, and Roughgarden. Furthermore, we generalize our result to general congestion games with player-specific payoff functions.
31. Christian Borgs, Jennifer Chayes, Mohammad Mahdian, and Amin Saberi, Exploring the Community Structure of Newsgroups, Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 783-787, 2004.
    In this paper we study the question of clustering USENET into communities, and present the results of our experiments on the data gathered by Microsoft in summer 2003. You can see a clustering of newsgroups here.
32. Ranveer Chandra, Kamal Jain, Mohammad Mahdian, and Lili Qiu, Optimizing the Placement of Integration Points in Multi-hop Wireless Networks, Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP), 271-282, 2004.
    In this paper we study various models and optimization algorithms for placing Internet TAPs in wireless neighborhood networks. A longer version of this paper was published as an MSR technical report.
33. Nikhil Bansal, Lisa K. Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko, Online QoS Buffer Management, Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 3142, 196-207, 2004.
    We study the behavior of algorithms for buffering packets weighted by different levels of Quality of Service (QoS) guarantees in a single queue. Buffer space is limited, and packet loss occurs when the buffer overflows. We describe a modification of the preemptive greedy algorithm of Kesselman et al. (ESA 2003) for buffer management and give an analysis to show that this algorithm achieves a competitive ratio of at most 1.75. This improves upon recent work showing a 1.98 competitive ratio, and previous result that shows the simple greedy algorithm has a competitive ratio of 2.
34. Ron Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee, Comparing and Aggregating Rankings with Ties, Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), 47-58, 2004.
    In this paper we propose several metrics to compare partial orderings, present algorithms that efficiently compute them, and prove that they are withing constant multiple of each other. Based on these concepts, we formulate aggregating problems for partial rankings and develop efficient algorithms for rank aggregation.
35. Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay Vazirani, Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP, Journal of the ACM, 50 (6), pp. 795-824, November 2003.
    This is the complete version of the APPROX 2001 and STOC 2002 papers. It includes two approximation algorithms for the metric uncapacitated facility location problem, together with a complete analysis and a discussion about the methods used in the proof.
36. Mohammad Mahdian and Martin Pal, Universal Facility Location, Proceedings of the 11th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2832, 409-421, 2003. Slides (Winner of the best student paper award in ESA 2003)
    In this paper we present a natural generalization of a local-search algorithm of Pal, Tardos, and Wexler to a generalized version of the facility location problem in which the opening cost of each facility is an arbitrary increasing function of the number of clients that will be served by it. This problem is a common generalization of many variants of the facility location problem (FLP), such as the uncapacitated FLP, the hard-capacitated FLP and the soft-capacitated FLP. Also, our algorithm slightly improves the approximation factor of the algorithm of Pal, Tardos, and Wexler.
37. Kamal Jain, Mohammad Mahdian, and Amin Saberi, Approximating Market Equilibria, Proceedings of the 6th InternationalWorkshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Computer Science 2764, 98-108, 2003. Slides
    In this paper we present an algorithm for computing an approximate market equilibrium in a market where there is no dichotomy between buyers and sellers.
38. Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang, A 2-approximation algorithm for the soft-capacitated facility location problem, Proceedings of the 6th InternationalWorkshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Computer Science 2764, 129-140, 2003. Slides
    This paper gives a 2-approximation algorithm for the soft-capacitated facility location problem; This achieves the integrality gap of the LP relaxation of the problem. We also show how having two separate approximation factors for the facility cost and the connection cost can improve the approximation ratio of several variants of the facility location problem.
39. Kamal Jain, Mohammad Mahdian, and Mohammad R. Salavatipour, Packing Steiner Trees, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 266-274, 2003. Slides
    In this paper we investigate the problem of finding the maximum number of edge-disjoint Steiner trees for a graph $G$ and a set $S$ of vertices of $G$ as terminals. This problem is a generalization of the theorem of Nash-Williams and Tutte.
40. MohammadTaghi Hajiaghayi, Mohammad Mahdian, and Vahab Mirrokni Facility Location Problem with General Cost Functions, Networks, 42(1), pp. 42-47, August 2003.
    In this paper we introduce a generalization of the facility location problem in which the cost of each facility is an arbitrary function of the number of clients served by it (this problem is called universal facility location in a later paper), and analyze a natural greedy algorithm for the case of concave cost functions.
41. Jacob Fox, Veselin Jungic, Mohammad Mahdian, Jaroslav Nesetril, and Rados Radoicic, Rainbow Arithmetic Progressions and Anti-Ramsey Results, Combinatorics, Probability, and Computing special issue on Ramsey Theory 12, 599-620, 2003.
    The van der Waerden theorem in Ramsey theory says that for every $k$ and $l$, every coloring of the set of natural numbers with $k$ colors contains a monochromatic arithmetic progression of length $l$. In this paper, we prove a similar result for rainbow arithmetic progressions, i.e., arithmetic progressions whose terms are colored with different colors. More specifically, we prove that every 3-coloring of the set of natural numbers in which each color class has density more than 1/6 contains a 3-term arithmetic progression. We will also explore several generalizations and variants of this result.
42. Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Computer Science 2462, 229-242, 2002.
    We give a 1.52 approximation algorithm for the metric uncapacitated facility location problem. This is currently the best known algorithm for this problem.
43. Kamal Jain, Mohammad Mahdian, and Amin Saberi, A New Greedy Approach for Facility Location Problem, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 731-740, 2002.
    This paper gives a simple 1.61-approximation algorithm for the metric uncapacitated facility location problem. This improves the approximation factor of a generalization of the k-median and facility location problems.
44. Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Mohammad Mahdian, and Vahab Mirrokni, Length-constrained Path-matchings in Graphs, Networks 39, No. 4, pp. 210-215, 2002.
    In this paper we study the computational complexity of the path-matching problem in graphs.
45. Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay Vazirani, A Greedy Facility Location Algorithm Analyzed using Dual-Fitting, In Proceedings of 5th International Workshop on Randomization and Approximation Techniques in Computer Science, volume 2129 of Lecture Notes in Computer Science, pp. 127-137, 2001.
    This paper gives a simple 1.86-approximation algorithm for the metric uncapacitated facility location problem.
46. Mohammad Mahdian, On the Computational Complexity of Strong Edge Coloring, Discrete Applied Mathematics 118, pp. 239-248, 2002.
    This paper studies the computational complexity of the strong edge coloring problem. This was part of my Master's thesis.
47. Mohammad Mahdian, The strong chromatic index of C_4-free graphs, Random Structures and Algorithms 17, pp. 357-375, 2000.
    In this paper, we prove that the strong chromatic index of every graph without a cycle of length 4 is at most $(2+\epsilon)D^2/\ln(D)$, where $D$ is the maximum degree of the vertices of $G$. This was part of my Master's thesis.
48. Babak Farzad, Mohammad Mahdian, Ebad S. Mahmoodian, Amin Saberi, and Bardia Sadri, Forced Orientation of graphs, Bulletin of Iranian Mathematical Society 32 (1), 79-89, April 2006.
    Assume I have a strongly connected directed graph $G$. You know the underlying undirected structure of $G$, but not the direction of the edges. A set $S$ of the edges of $G$ is called a forcing set if by knowing the direction of the edges of $S$ (and the fact that $G$ is strongly connected), you can deduce the direction of all edges of $G$. This concept is defined by Chartrand, Harary, Schultz, and Wall. The main result of this paper is to show that forcing sets of any directed graph constitute a matroid structure.
49. Peter Adams, Mohammad Mahdian, and Ebad S. Mahmoodian, On the forced matching numbers of bipartite graphs, Discrete Mathematics 281, pp. 1-12, 2004.
    Let G be a graph with a perfect matching M. A forcing set for M is a subset S of M such that M is the only perfect matching of G that contains S. The forcing number of a matching M is the size of the smallest forcing set for M. In this paper, we prove that the problem of finding the smallest forcing set for a given matching in a given graph is NP-complete. We also show several results on forcing sets of matchings in hypercubes and an application of this notion in bounding the size of the smallest critical set in a Latin square.
50. Mohammad Mahdian, Ebad S. Mahmoodian, Amin Saberi, Mohammad R. Salavatipour, and Rouzbeh Touserkani, On a conjecture of Keedwell and the cycle double cover conjecture, Discrete Mathematics 216 , pp. 287-292, Apr 2000.
    In this paper, we connect two seamingly unrelated conjectures: A conjecture of Keedwell (restated by Cameron) on critical sets in Latin squares, and the well-known cycle double cover conjecture. We prove that the former conjecture is implied by the latter, and use this theorem to prove Keedwell's conjecture in special cases. Subsequently, C.Q. Zhang et al. used our result to settle Keedwell's conjecture in the general case.
51. Mohammad Mahdian, and Ebad S. Mahmoodian, The roots of an IMO97 problem, Bulletin of the Institute of Combinatorics and its Applications 28 , pp. 48-54, 2000.
    This paper explains the roots of an IMO'97 problem that was proposed by me and Prof. Mahmoodian, and explores related results and open questions.
52. Mohammad Mahdian, and Ebad S. Mahmoodian, A Characterization of Uniquely 2-List Colorable Graphs, Ars Combinatoria 51 , pp. 295-305, Feb 1999.
    A graph $G$ is uniquely 2-list colorable if one can assign a list of two colors to each vertex of $G$ in such a way that there is a unique proper coloring for $G$ from these lists of colors. In this paper, we prove that a graph is uniquely 2-list colorable if and only if none of its connected components is a cycle, a complete graph, or a complete bipartite graph.
53. Mohammad Mahdian, and Ebad S. Mahmoodian, On the Uniquely List Colorable Graphs, Proceeding of 28th Iranian Mathematics Conference, 1997.
    This paper contains a summary of the results of the above paper, plus an application of these results in bounding the size of the smallest defining set of vertex coloring of certain graphs, several other small results, and a few open questions.
54. Reza Naserasr, Ebad S. Mahmoodian, Mohammad Mahdian, and Frank Harary, On defining sets of vertex coloring of the Cartesian product of a cycle and a complete graph, In: Y. Alavi, D.R. Lick, and A.J. Schwenk, eds., Combinatorics, Graph Theory and Algorithms, Kalamazoo, Michigan, USA, 1999.
    In a graph $G$, a set $S$ of vertices together with a partial coloring of $S$ is called a defining set of the vertex coloring of $G$, if this partial coloring can be extended to a proper coloring of $G$ with the minimum number of colors in a unique way. In this paper, we prove bounds on the size of the smallest defining set for certain products of complete graphs and cycles.
55. Mohammad Mahdian, The size of the minimum critical set in the $Z_2\times Z_2\times Z_2$ Latin square is 25, Bulletin of the Institute of Combinatorics and its Applications 21 , pp. 14-16, 1997.
    This short note, which was my first publication, is a report on some results found by a computer program that I had written. The results are not very important, but I was pretty excited about my first publication! :) Thanks to Prof. Mahmoodian who took care of preparing and submitting this note.

Theses

1. Mohammad Mahdian, Facility Location and the Analysis of Algorithms through Factor-Revealing Programs, Ph.D. Thesis, MIT, June 2004.
2. Mohammad Mahdian, The strong chromatic index of graphs, M.Sc. Thesis, University of Toronto, January 2000.
3. Mohammad Mahdian, Shortest Path Algorithms in Triangulated Irregular Networks, B.Sc. Thesis, Sharif University of Technology, August 1997.

Books

1. Mohammad Ghodsi, Mohammad Mahdian, Preparing for Computer Olympiads: Problems (in Persian), Fatemi Pub. Co., May 1999.
   This book contains over 170 algorithmic problems suitable for preparing for computer olympiads and ACM programming competitions.

Other manuscripts

1. Mohammad Mahdian, Introduction to the probabilistic method.
2. Mohammad Mahdian, The Regularity Lemma.