Mohammad Hajiaghayi

Mohammad Hajiaghayi


Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
12 July 2011 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MHMohammad Hajiaghayi
Mohammad Hajiaghayi
RKR. Khandekar
R. Khandekar
GKG. Kortsarz
G. Kortsarz

21 May 2008 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MCMoses Charikar
Moses Charikar
MHMohammad Hajiaghayi
Mohammad Hajiaghayi
HKHoward Karloff
Howard Karloff
SRSatish Rao
Satish Rao

25 April 2010 in arXiv
Verified
Preprint
Open access
PDF file
MBMohammadHossein Bateni
MohammadHossein Bateni
MHMohammad Hajiaghayi
Mohammad Hajiaghayi
NINicole Immorlica
Nicole Immorlica
HMHamid Mahini
Hamid Mahini
We study bargaining games between suppliers and manufacturers in a network context. Agents wish to enter into contracts in order to generate surplus which then must be divided among the participants. Potential contracts and their surplus are represented by weighted edges in our bipartite network. Each agent in the market is additionally limited by a capacity representing the number of contracts which he or she may undertake. When all agents are limited to just one contract each, prior research applied natural generalizations of the Nash bargaining solution to the networked setting, defined the new solution concepts of stable and balanced, and characterized the resulting bargaining outcomes. We simplify and generalize these results to a setting in which participants in only one side of the market are limited to one contract each. The heart of our results uses a linear-programming formulation to establish a novel connection between well-studied cooperative game theory concepts (such as core and prekernel) and the solution concepts of stable and balanced defined for the bargaining games. This immediately implies one can take advantage of the results and algorithms in cooperative game theory to reproduce results such as those of Azar et al. [1] and Kleinberg and Tardos [29] and also generalize them to our setting. The cooperative-game-theoretic connection also inspires us to refine our solution space using standard solution concepts from that literature such as nucleolus and lexicographic kernel. The nucleolus is particularly attractive as it is unique, always exists, and is supported by experimental data in the network bargaining literature. Guided by algorithms from cooperative game theory, we show how to compute the nucleolus by pruning and iteratively solving a natural linear-programming formulation.

9 February 2009 in arXiv
Verified
Preprint
Open access
PDF file
EDErik D. Demaine
Erik D. Demaine
MHMohammad Hajiaghayi
Mohammad Hajiaghayi
HMHamid Mahini
Hamid Mahini
MZMorteza Zadimoghaddam
Morteza Zadimoghaddam
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost \alpha. Together the agents create a network (a subgraph of the host graph) while selfishly minimizing the link creation costs plus the sum of the distances to all other players (usage cost). In this paper, we pursue two important facets of the network creation game. First, we study extensively a natural version of the game, called the cooperative model, where nodes can collaborate and share the cost of creating any edge in the host graph. We prove the first nontrivial bounds in this model, establishing that the price of anarchy is polylogarithmic in n for all values of α in complete host graphs. This bound is the first result of this type for any version of the network creation game; most previous general upper bounds are polynomial in n. Interestingly, we also show that equilibrium graphs have polylogarithmic diameter for the most natural range of \alpha (at most n polylg n). Second, we study the impact of the natural assumption that the host graph is a general graph, not necessarily complete. This model is a simple example of nonuniform creation costs among the edges (effectively allowing weights of \alpha and \infty). We prove the first assemblage of upper and lower bounds for this context, stablishing nontrivial tight bounds for many ranges of \alpha, for both the unilateral and cooperative versions of network creation. In particular, we establish polynomial lower bounds for both versions and many ranges of \alpha, even for this simple nonuniform cost model, which sharply contrasts the conjectured constant bounds for these games in complete (uniform) graphs.

6 December 2009 in arXiv
Verified
Preprint
Open access
PDF file
MBMohammadHossein Bateni
MohammadHossein Bateni
MHMohammad Hajiaghayi
Mohammad Hajiaghayi
In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k-Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et al. [12] for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case).

22 June 2010 in arXiv
Verified
Preprint
Open access
PDF file
MBMohammadHossein Bateni
MohammadHossein Bateni
MHMohammad Hajiaghayi
Mohammad Hajiaghayi
DMDániel Marx
Dániel Marx
In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF) and more generally Submodular Prize-Collecting Steiner Forest (SPCSF) on planar graphs (and more generally bounded-genus graphs) to the same problems on graphs of bounded treewidth. More precisely, we show any $\alpha$-approximation algorithm for these problems on graphs of bounded treewidth gives an $(\alpha + \epsilon)$-approximation algorithm for these problems on planar graphs (and more generally bounded-genus graphs), for any constant $\epsilon > 0$. Since PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth using dynamic programming, we obtain PTASs for these problems on planar graphs and bounded-genus graphs. In contrast, we show PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. This result is interesting on its own because it gives the first provable hardness separation between prize-collecting and non-prize-collecting (regular) versions of the problems: regular Steiner Forest is known to be polynomially solvable on series-parallel graphs and admits a PTAS on graphs of bounded treewidth. An analogous hardness result can be shown for Euclidian PCSF. This ends the common belief that prize-collecting variants should not add any new hardness to the problems.