MohammadTaghi Hajiaghayi

MohammadTaghi Hajiaghayi

Auto-generated profile, based on publicly available information

MohammadTaghi Hajiaghayi

University of Maryland, College Park, USA

Research Focus & Metrics

Academic Career Length

17Years (2010-Present)

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

Representative Publications

View All Publications
7 January 2019 in Journal of Artificial Intelligence Research
Verified
Journal Article
Open access
PDF file
AFAlireza Farhadi
Alireza Farhadi
Mohammad Reza GhodsiMohammad Reza Ghodsi
Mohammad Reza Ghodsi
MHMohammad Taghi Hajiaghayi
Mohammad Taghi Hajiaghayi
SLSébastien Lahaie
Sébastien Lahaie
DPDavid Pennock
David Pennock
HYHadi Yami
Hadi Yami
We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

1 September 2010 in Combinatorica
Verified
Journal Article
Open access
PDF file
EDErik D. Demaine
Erik D. Demaine
MHMohammadTaghi Hajiaghayi
MohammadTaghi Hajiaghayi
BMBojan Mohar
Bojan Mohar
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [4,20, 10, 17], and it generalizes a similar result for “compression” (a variant of contraction) in planar graphs [29]. Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [24, 1, 29, 25, 8, 5]. We also highlight the only main difficulty in extending our results to general H-minor-free graphs.

3 February 2011 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MCMoses Charikar
Moses Charikar
MHMohammadTaghi Hajiaghayi
MohammadTaghi Hajiaghayi
HKHoward Karloff
Howard Karloff

22 January 2011 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MBMohammadHossein Bateni
MohammadHossein Bateni
MHMohammadTaghi Hajiaghayi
MohammadTaghi Hajiaghayi

1 May 2020 in Operations Research
Verified
Journal Article
Closed access
DJDavid S. Johnson
David S. Johnson
LBLee Breslau
Lee Breslau
IDIlias Diakonikolas
Ilias Diakonikolas
NDNicholas Duffield
Nicholas Duffield
YGYu Gu
Yu Gu
SSSubhabrata Sen
Subhabrata Sen
Content Distribution and End-to-End Monitoring with Set Cover by Pairs

11 August 2013 in Wireless Networks
Verified
Journal Article
Closed access
PDF file
MHMahdi Hajiaghayi
Mahdi Hajiaghayi
CWCarl Wijting
Carl Wijting
CRCassio Ribeiro
Cassio Ribeiro
MHMohammad T. Hajiaghayi
Mohammad T. Hajiaghayi