Publications
Journal Articles
[1] 
M. Bateni, M. Hajiaghayi, and
D. Marx. Approximation schemes for Steiner forest on planar graphs
and graphs of bounded treewidth. Journal of
the ACM. To appear. A preliminary version appeared in Proceedings of
the 42nd ACM Symposium on Theory of computing (STOC), 2010, pages
211220. 
[2] 
M. T.
Hajiagahyi, R. Khandekar,
G. Kortsarz, and Z. Nutov.
Prizecollecting Steiner network problems. ACM Trans. on Algorithms.
To appear. A preliminary version appeared in Proceedings of the 14th
Conference on Integer Programming and Combinatorial Optimization ( IPCO), 2010, pages 7184. 
[3] 
M. T.
Hajiaghayi, R. Khandekar,
and G. Kortsarz. Budgeted
redblue median and its generalizations. A special issue of
Algorithmica for selected papers from ESA 2010,
2010. A preliminary version appeared in Proceedings of the 18th Annual
European Symposium on Algorithms (ESA), 2010, pages 314325. 
[4] 
M. Charikar, M. T. Hajiaghayi,
and H. Karloff. Improved approximation algorithms for label cover
problems. A special issue of Algorithmica
for selected papers from ESA 2009. To appear, A preliminary
version appeared in Proceedings of the 17th Annual European Symposium on
Algorithms (ESA), 2009, pages 2334. 
[5] 
J. Erman, A. Gerber, M. T. Hajiaghayi,
D. Pei, S. Sen, and O. Spatscheck. To cache or not to cache: the 3G case.
IEEE Internet Computing. To appear. 
[6] 
M. H.
Bateni, L. Golab,
M. T. Hajiaghayi, and H. Karloff. Scheduling
to minimize Staleness and stretch in realtime data warehouses. A
special issue of Theory of Computing Systems for selected
papers from SPAA 2009. To appear, Proceedings of the 21st Annual
ACM Symposium on Parallel Algorithms and Architectures (SPAA),
2009, pages 2938. 
[7] 
M. H.
Bateni and M. T. Hajiaghayi.
Assignment problem in content distribution networks: unsplittable
hardcapacitated facility location. ACM Trans. Algorithms. To
appear. A preliminary version appeared in Proceedings of the 20th Annual
ACMSIAM Symposium on Discrete Algorithms (SODA), 2009, pages
805814. 
[8] 
E. D.
Demaine, M. T. Hajiaghayi,
H. Mahini, and M. Zadimoghaddam.
The price of anarchy in network creation games. ACM Trans.
Algorithms. To appear. A preliminary version appeared in Proceedings
of the 26th Annual ACM Symposium on Principles of Distributed Computing ( PODC), 2007, pages 292298. 
[9] 
M. H.
Bateni and M. T. Hajiaghayi.
Euclidean prizecollecting Steiner forest. Algorithmica.
To appear. A preliminary version appeared in Proceedings of the 9th Latin
American Theoretical Informatics Symposium (LATIN), 2010, pages
503514. 
[10] 
M. H.
Bateni, M. T. Hajiaghayi, , A. Gerber, and S. Sen. MultiVPN
Optimization for scalable routing via relaying. IEEE/ACM Trans. Netw., 18(5):15441556, 2010. A preliminary version
appeared in the 28th IEEE International Conference on Computer
Communications (INFOCOM), 2009. 
[11] 
E. D.
Demaine, M. T. Hajiaghayi,
and B. Mohar. Approximation algorithms via
contraction decomposition. Combinatorica,
30(5):533552, 2010. A preliminary version appeared in Proceedings of the
18th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
2007, pages 278287. 
[12] 
A. Archer,
M. Bateni, M. Hajiaghayi,
and H. Karloff. Improved approximation algorithms for
prizecollecting Steiner tree and TSP. SIAM J. Comput.,
40(2):309332, 2011. A preliminary version appeared in Proceedings of the
50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2009, pages 427436. 
[13] 
C. Chekuri, M. T. Hajiaghayi,
G. Kortsarz, and M. R. Salavatipour. Approximation algorithms for nonuniform
buyatbulk network design. SIAM J. Comput.,
39(5):17721798, 2010. A preliminary version appeared in Proceedings of
the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2006, pages 677686. 
[14] 
J. Bredin, E. D. Demaine,
M. T. Hajiaghayi, and D. Rus. Deploying
sensor networks with guaranteed fault tolerance. IEEE/ACM Trans. Netw., 18(1):216228, 2010. A preliminary version
appeared in Proceedings of the 6th ACM International Symposium on Mobile
Ad Hoc Networking and Computing ( MOBIHOC),
May 2005, pages 309319. 
[15] 
E. D.
Demaine, M. T. Hajiaghayi,
H. Mahini, A. S. SayediRoshkhar,
S. Oveisgharan, and M. Zadimoghaddam. Minimizing movement. A
special issue of ACM Trans. Algorithms for selected papers
from SODA 2007, 5(3), 2009. A preliminary version appeared in Proceedings
of the 18th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
January 2007, pages 258267. 
[16] 
A. Gupta,
M. T. Hajiaghayi, V. Nagarajan,
and R. Ravi. Dialaride from kforest. ACM Trans.
Algorithms, 6(2), 2010. A preliminary version appeared in Proceedings
of the 15th Annual European Symposium on Algorithms (ESA),
October 2007, pages 241252. 
[17] 
M. Charikar, M. T. Hajiaghayi,
H. Karloff, and S. Rao. l_{2}^{2} spreading
metrics for vertex ordering problems. Algorithmica,
56(4):577604, 2010. A preliminary version appeared in Proceedings of the
17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
January 2006, pages 10181027. 
[18] 
E. D.
Demaine, M. Hajiaghayi,
H. Mahini, and M. Zadimoghaddam.
The Price of Anarchy in Cooperative Network Creation Games. ACM SIGecom Exchanges, 8(2), 2009. A preliminary version
appeared in Proceedings of the 26th International Symposium on
Theoretical Aspects of Computer Science (STACS), 2009, pages
301312. 
[19] 
M. H.
Bateni and M. T. Hajiaghayi.
A note on subadditive network design. Oper. Res. Lett.,
37(5):339344, 2009. 
[20] 
E. D.
Demaine, M. T. Hajiaghayi,
and K. Kawarabayashi. Algorithmic graph
minor theory: improved grid minor bounds and Wagner's contraction. Special
issue of Algorithmica for selected
papers from ISAAC 2006, 54(2):142180, 2009. A preliminary version
appeared in Proceedings of the 17th Annual International Symposium on
Algorithms and Computation (ISAAC 2006), December 2006, pages
315. Winner of the best paper award in ISAAC 2006. 
[21] 
M. T.
Hajiaghayi, G. Kortsarz,
and M. R. Salavatipour. Approximating
buyatbulk and shallowlight kSteiner trees. Algorithmica, 53(1):89103, 2009. A preliminary
version appeared in Proceedings of the 9th International Workshop on
Approximation Algorithms for Combinatorial Optimization (APPROX),
August 2006, pages 153163. 
[22] 
U. Feige, M. T. Hajiaghayi,
and J. R. Lee. Improved approximation algorithms for minimum weight
vertex separators. Special issue of SIAM J. Comput. for
selected papers from STOC 2005, 38(2):629657, 2008. A preliminary
version appeared in Proceedings of the 37th ACM Symposium on Theory of
Computing (STOC), May 2005, pages 563572. 
[23] 
E. D.
Demaine, U. Feige,
M. T. Hajiaghayi, and M. R. Salavatipour. Combination can be hard: approximability of the unique coverage problem. SIAM
J. Comput., 38(4):14641483, 2008. A
preliminary version appeared in Proceedings of the 17th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), January 2006, pages
162171. 
[24] 
E. D.
Demaine and M. T. Hajiaghayi.
Linearity of grid minors in treewidth with
applications through bidimensionality. Combinatorica, 28(1):1936, 2008. A preliminary
version appeared in Proceedings of the 16th Annual ACMSIAM Symposium on
Discrete Algorithms (SODA), January 2005, pages 682689. 
[25] 
S. Butler,
M. T. Hajiaghayi, R. D. Kleinberg, and
T. Leighton. Hat guessing games. SIAM J. Discrete Math.,
22(2):592605, 2008. The paper has been selected as an
exceptional paper published in SIAM's specialized journals for
the SIGEST section of SIAM Review. Revised version appeared in SIAM
Rev. 51(2):397397, 2009 
[26] 
N. Alon, M. Badoiu,
E. D. Demaine, M. FarachColton,
M. T. Hajiaghayi, and A. Sidiropoulos. Ordinal embeddings of minimum
relaxation: general properties, trees, and ultrametrics.
ACM Trans. Algorithms, 4(4):Art. 46, 21,
2008. A preliminary version appeared in Proceedings of the 16th Annual
ACMSIAM Symposium on Discrete Algorithms (SODA), January 2005,
pages 650659. 
[27] 
E. D.
Demaine and M. T. Hajiaghayi.
The Bidimensionality theory and its algorithmic
applications. Special issue of Comput.
J. for selected surveypapers in FixedParameter Tractability,
51(3):292302, 2008. This paper surveys our theory of bidimensionality and its known combinatorial and
algorithmic results of this theory. 
[28] 
B. Awerbuch, M. T. Hajiaghayi,
R. Kleinberg, and T. Leighton. Localized ClientServer Load
Balancing without Global Information. SIAM J. Comput.,
37(4):12591279, 2007. A preliminary version appeared in Proceedings of
the 16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),January 2005, pages 197206. Invitation to Journal
of Scheduling special issue for selected papers from SODA 2005
regretfully declined. 
[29] 
M. T.
Hajiaghayi, N. Immorlica,
and V. S. Mirrokni. Power optimization in
faulttolerant topology control algorithms for wireless multihop networks.
IEEE/ACM Trans. Netw., 15(6):13451358,
2007. A preliminary version appeared in Proceedings of the 9th Annual
International Conference on Mobile Computing and Networking (MOBICOM),
September 2003, pages 300312. 
[30] 
M. T.
Hajiaghayi, R. D. Kleinberg, T. Leighton,
and H. Räcke. Oblivious routing on
nodecapacitated and directed graphs. ACM Trans. Algorithms, 3(4):Art. 51, 13, 2007. A preliminary version appeared in Proceedings
of the 16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
January 2005, pages 782790. Invitation to Journal of Scheduling
special issue for selected papers from SODA 2005 regretfully
declined. 
[31] 
M. T.
Hajiaghayi, G. Kortsarz,
V. S. Mirrokni, and Z. Nutov. Power optimization for connectivity problems.
Special issue of Math. Program. for
selected papers from IPCO 2005, 110(1, Ser. B):195208, 2007. A
preliminary version appeared in Proceedings the 11th Conference on
Integer Programming and Combinatorial Optimization (
IPCO), June 2005, pages 349361. 
[32] 
M. H.
Bateni, E. D. Demaine,
M. T. Hajiaghayi, and M. Moharrami. Plane embeddings of planar graph metrics.
Discrete Comput. Geom., 38(3):615637, 2007.
A preliminary version appeared in Proceedings of the 22nd Annual ACM
Symposium on Computational Geometry (SOCG), June 2006, pages
197206. 
[33] 
P. Bahl, M. T. Hajiaghayi,
K. Jain, V. S. Mirrokni, L. Qiu, and A. Saberi. Cell
Breathing in Wireless LANs: Algorithms and Evaluation. IEEE Trans.
Mob. Comput.,
6(2):164178, 2007. 
[34] 
M. T.
Hajiaghayi and N. Nishimura. Subgraph isomorphism, logbounded
fragmentation, and graphs of (locally) bounded treewidth.
J. Comput. System Sci., 73(5):755768, 2007.
A preliminary version appeared in Proceedings of the 27th International
Symposium on Mathematical Foundations of Computer Science (MFCS),
August 2002, pages 305318. 
[35] 
E. D.
Demaine and M. T. Hajiaghayi.
Quickly deciding minorclosed parameters in general graphs. European
J. Combin., 28(1):311314, 2007. 
[36] 
M. Badoiu, E. D. Demaine,
M. T. Hajiaghayi, and P. Indyk. Lowdimensional embedding with extra
information. Special issue of Discrete Comput. Geom. for selected papers from SOCG 2004,
36(4):609632, 2006. A preliminary version appeared in Proceedings of the
20th ACM Symposium on Computational Geometry (SOCG), June 2004,
pages 320329. 
[37] 
E. D.
Demaine, M. T. Hajiaghayi,
and D. M. Thilikos. The bidimensional
theory of boundedgenus graphs. SIAM J. Discrete Math.,
20(2):357371, 2006. A preliminary version appeared in Proceedings of the
29th International Symposium on Math. Foundations of Computer Science ( MFCS), 2004, pages 191203. 
[38] 
M. Bahramgiri, M. T. Hajiaghayi,
and V. S. Mirrokni. FaultTolerant and
3Dimensional Distributed Topology Control Algorithms in Wireless Multihop
Networks. ACM/Kluwer Wireless Networks,
12(2):179188, 2006. A preliminary version appeared in Proceedings of the
11th IEEE International Conference on Computer Communications and Networks
( ICCCN), October 2002, pages 392398. 
[39] 
M. T.
Hajiaghayi and T. Leighton. On the maxflow
mincut ratio for directed multicommodity flows.
Theoret. Comput.
Sci., 352(13):318321, 2006. 
[40] 
M. T.
Hajiaghayi and H. Räcke.
An O(sqrt(n))approximation
algorithm for directed sparsest cut. Inform. Process. Lett., 97(4):156160, 2006. 
[41] 
E. D.
Demaine, F. V. Fomin,
M. T. Hajiaghayi, and D. M. Thilikos. Subexponential
parameterized algorithms on boundedgenus graphs and Hminorfree
graphs. J. ACM, 52(6):866893, 2005. A preliminary version
appeared in Proceedings of the 15th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), January 2004, pages 830839. 
[42] 
E. D.
Demaine, F. V. Fomin,
M. T. Hajiaghayi, and D. M. Thilikos. Fixedparameter algorithms for (k,r)center in
planar graphs and map graphs. ACM Trans. Algorithms, 1(1):3347,
2005. A preliminary version appeared in Proceedings of the 30th
International Colloquium on Automata, Languages and Programming ( ICALP), July 2003, pages 829844. 
[43] 
E. D.
Demaine, M. T. Hajiaghayi,
and D. M. Thilikos. Exponential speedup of
fixedparameter algorithms for classes of graphs excluding singlecrossing
graphs as minors. Algorithmica,
41(4):245267, 2005. A preliminary version appeared in Proceedings of the
13th Annual International Symposium on Algorithms and Computation (ISAAC),
November 2002. 
[44] 
T. Biedl, T. Chan, Y. Ganjali,
M. T. Hajiaghayi, and D. R. Wood. Balanced
vertexorderings of graphs. Discrete Appl. Math., 148(1):2748,
2005. 
[45] 
E. D.
Demaine, F. V. Fomin,
M. T. Hajiaghayi, and D. M. Thilikos. Bidimensional
parameters and local treewidth. SIAM J.
Discrete Math., 18(3):501511, 2004/05. Preliminary versions appeared in Proceedings
of the 6th Latin American Theoretical Informatics (LATIN),
April 2004, and Proceeding of the 11th Annual European Symposium on
Algorithms (ESA), September 2003. 
[46] 
D. Coppersmith,
D. Gamarnik, M. T. Hajiaghayi,
and G. B. Sorkin. Random MAX SAT, random
MAX CUT, and their phase transitions. Random Structures Algorithms,
24(4):502545, 2004. A preliminary version appeared in Proceedings of
14th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
January 2003, pages 364373. 
[100] 
E. D.
Demaine and M. T. Hajiaghayi.
Diameter and treewidth in minorclosed graph
families, revisited. Algorithmica,
40(3):211215, 2004. 
[48] 
E. D.
Demaine, M. T. Hajiaghayi,
N. Nishimura, P. Ragde, and D. M. Thilikos. Approximation algorithms for classes of
graphs excluding singlecrossing graphs as minors. J. Comput. System Sci., 69(2):166195, 2004. 
[49] 
Y. Ganjali and M. T. Hajiaghayi.
Characterization of networks supporting multidimensional linear interval
routing schemes. Theoret. Comput. Sci., 326(13):103116, 2004. 
[50] 
T. Biedl, J. F. Buss, E. D. Demaine,
M. L. Demaine, M. T. Hajiaghayi,
and T. Vinař. Palindrome recognition
using a multidimensional tape. Theoret.
Comput. Sci., 302(13):475480, 2003. 
[51] 
M. T.
Hajiaghayi, M. Mahdian,
and V. S. Mirrokni. The facility location
problem with general cost functions. Networks, 42(1):4247, 2003. 
[52] 
M. T.
Hajiaghayi and M. Hajiaghayi.
A note on the bounded fragmentation property and its applications in
network reliability. European J. Combin.,
24(7):891896, 2003. A preliminary version appeared in Proceedings of Euroconference on Combinatorics,
Graph Theory and Applications (EuroCOMB),
September 2003. 
[53] 
M. M.
Veloso, T. R. Balch, P. Stone,
H. Kitano, F. Yamasaki, K. Endo, M. Asada, M. Jamzad, S. B. Sadjad,
V. S. Mirrokni, M. Kazemi,
H. R. Chitsaz, A. Heydarnoori,
M. T. Hajiaghayi, and E. Chiniforooshan. RoboCup2001: The Fifth Robotic Soccer
World Championships. AI Magazine, 23(1):5568, 2002. 
[54] 
M. Ghodsi, M. T. Hajiaghayi,
M. Mahdian, and V. S. Mirrokni.
Lengthconstrained pathmatchings in graphs.
Networks, 39(4):210215, 2002. 
[55] 
M. T.
Hajiaghayi and Y. Ganjali.
A note on the consecutive ones submatrix problem.
Inform. Process. Lett.,
83(3):163166, 2002. 
[56] 
M. T.
Hajiaghayi, N. Nishimura, P. Ragde, and D. M. Thilikos.
Fast approximation schemes for K_{3,3}minorfree
or K_{5}minorfree graphs. Electron. Notes Discrete
Math., 10:6 pp., 2001. A preliminary version appeared in Proceedings
of Euroconference on Combinatorics,
Graph Theory and Applications (EuroCOMB),
September 2001, pages 158163. 
[57] 
M. T.
Hajiaghaee, E. S. Mahmoodian,
V. S. Mirrokni, A. Saberi,
and R. Tusserkani. On the simultaneous
edgecoloring conjecture. Discrete Math., 216(13):267272, 2000. Conference
Papers (excluding those already appeared in journals) 
[58] 
R. Chitnis, M. T. Hajiaghayi,
and V. Liaghat. Parameterized complexity of
problems in coalitional resource games. In Proceedings of the 25nd
Association for the Advancement of Artificial Intelligence Conference on
Artificial Intelligence (AAAI). AAAI Press, 2011. To appear. 
[59] 
E. Demaine, M. T. Hajiaghayi,
and K. Kawarabayashi. Contraction
decomposition in Hminorfree graphs and its algorithmic
applications. In Proceedings of the 43rd Annual ACM Symposium on
Theory of Computing (STOC), pages 441450. ACM, 2011. 
[60] 
M. T.
Hajiaghayi, R. Khandekar,
G. Kortsarz, and V. Liaghat.
On a local protocol for concurrent file transfers. In Proceedings
of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), pages 269278. ACM, 2011. 
[61] 
S. Alaei, M. T. Hajiaghayi,
V. Liaghat, D. Pei, and B. Saha. AdCell: ad
allocation in cellular networks. In Proceedings of the 19th Annual
European Symposium on Algorithms (ESA). Springer, 2011. To appear. 
[62] 
S.B.
Lee, D. Pei, M. T. Hajiaghayi, I. Pefkianakis, S. Lu, H. Yan, Z. Ge, J. Yates, and M. Kosseifi.
Scalable monitoring via threshold compression in a large operational 3G
network. In Proceedings of International Conference on Measurement and
Modeling of Computer Systems (SIGMETRICS), pages 135136. ACM, 2011. 
[63] 
M. H.
Bateni, M. T. Hajiaghayi,
S. Jafarpour, and D. Pei. Towards an
efficient algorithmic framework for pricing cellular data service. In Proceedings
of the 30th IEEE International Conference on Computer Communications
(INFOCOM), pages 581585. IEEE Computer Society, 2011. 
[64] 
L. Breslau,
I. Diakonikolas, N. Duffield, Y. Gu, M. T. Hajiagahyi,
D. S. Johnson, H. Karloff, M. C. Resende,
and S. Sen. Disjointpath facility location: theory and practice.
In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments
(ALENEX), pages 6074. SIAM, 2011. 
[65] 
M. Andrews,
M. T. Hajiaghayi, H. Karloff, and
A. Moitra. Capacitated metric labeling.
In Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pages 976995. Society for Industrial and Applied
Mathematics, 2011. 
[66] 
M. H.
Bateni, C. Chekuri,
A. Ene, M. T. Hajiaghayi,
N. Korula, and D. Marx. Prizecollecting
network design on planar graphs. In Proceedings of the 22nd Annual
ACMSIAM Symposium on Discrete Algorithms (SODA), pages 10281049.
Society for Industrial and Applied Mathematics, 2011. 
[67] 
N. Alon, E. D. Demaine,
M. T. Hajiaghayi, and T. Leighton. Basic
network creation games. In Proceedings of the 22nd ACM Symposium on
Parallelism in Algorithms and Architectures (SPAA), pages 106113. ACM,
2010. Journal version submitted to SIAM J. Discrete Math. Winner of the best paper award in SPAA 2010. 
[68] 
E. D.
Demaine, M. T. Hajiaghayi,
and K. Kawarabayashi. Decomposition,
approximation, and coloring of oddminorfree graphs. In Proceedings
of the 21st Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
pages 329344. Society for Industrial and Applied Mathematics, 2010. 
[69] 
M. H.
Bateni, M. T. Hajiaghayi,
N. Immorlica, and H. Mahini.
The cooperative game theory foundations of network bargaining games.
In Proceedings of the 37th International Colloquium on Automata, Languages
and Programming (ICALP), pages 6778. Springer, 2010. 
[70] 
M. H.
Bateni, M. T. Hajiaghayi,
and M. Zadimoghaddam. Submodular
secretary problem and extensions. In Proceedings of the 13th
International Workshop on Approximation Algorithms for Combinatorial
Optimization (APPROX), pages 3952. Springer, 2010. Journal version
submitted to ACM Transactions on Algorithms. 
[71] 
M. T.
Hajiaghayi, R. Khandekar,
G. Kortsarz, and J. Mestre.
The Checkpoint Problem. In Proceedings of the 13th International
Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX),
pages 219231. Springer, 2010. 
[72] 
M. T.
Hajiaghayi and A. A. Nasri.
Prizecollecting Steiner networks via iterative rounding. In Proceedings
of the 9th Latin American Theoretical Informatics Symposium (LATIN),
pages 515526. Springer, 2010. 
[73] 
M. Gupte, M. Hajiaghayi,
L. Han, L. Iftode, P. Shankar, and
R. Ursu. News posting by stragetic users in a social network. In Proceedings
of the 5th International Workshop on Internet and Network Economics (WINE),
pages 632639. Springer, 2009. 
[74] 
K. Kawarabayashi, E. D. Demaine,
and M. T. Hajiaghayi. Additive
approximation algorithms for listcoloring minorclosed class of graphs.
In Proceedings of the 20th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pages 11661175. Society for Industrial and Applied
Mathematics, 2009. 
[75] 
J. Erman, A. Gerber, M. T. Hajiaghayi,
D. Pei, and O. Spatscheck. Networkaware
forward caching. In Proceedings of the 18th International Conference
on World Wide Web (WWW), pages 291300. ACM, 2009. 
[76] 
E. D.
Demaine, M. T. Hajiaghayi,
and P. Klein. Nodeweighted Steiner tree and group Steiner tree in
planar graphs. In Proceedings of the 36th International Colloquium on
Automata, Languages and Programming (ICALP), pages 328340. Springer,
2009. 
[77] 
E. D.
Demaine, M. T. Hajiaghayi,
and K. Kawarabayashi. Nodeweighted Steiner
tree and group Steiner tree in planar graphs. In Proceedings of the
36th International Colloquium on Automata, Languages and Programming (ICALP),
pages 316327. Springer, 2009. 
[78] 
E. D.
Demaine, M. T. Hajiaghayi,
and D. Marx. Minimizing movement: fixedparameter tractability.
In Proceedings of the 17th Annual European Symposium on Algorithms (ESA),
pages 718729. Springer, 2009. Journal version submitted to ACM Tranactions on Algortithms.
Invitation to Algorithmica special
issue for selected papers from ESA 2009 regretfully declined. 
[79] 
A. Blum,
M. T. Hajiaghayi, K. Ligett,
and A. Roth. Regret minimization and the price of total anarchy.
In Proceedings of the 40th Annual ACM Symposium on Theory of Computing
(STOC), pages 373382. ACM, 2008. 
[80] 
M. Badoiu, E. D. Demaine,
M. T. Hajiaghayi, A. Sidiropoulos,
and M. Zadimoghaddam. Ordinal embedding:
approximation algorithms and dimensionality reduction. In Proceedings
of the 11th International Workshop on Approximation Algorithms for
Combinatorial Optimization (APPROX), pages 2134. Springer, 2008. 
[81] 
M. T.
Hajiaghayi, R. D. Kleinberg, and T. Sandholm. Automated online mechanism design and
prophet inequalities. In Proceedings of the 22nd Association for the
Advancement of Artificial Intelligence Conference on Artificial Intelligence
(AAAI), pages 5865. AAAI Press, 2007. 
[82] 
E. D.
Demaine, M. Ghodsi,
M. T. Hajiaghayi, A. S. SayediRoshkhar, and M. Zadimoghaddam.
Scheduling to minimize gaps and power consumption. In Proceedings
of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures
(SPAA), pages 4654. ACM, 2007. Journal version submitted to Journal
of Scheduling. 
[83] 
C. Chekuri, M. T. Hajiaghayi,
G. Kortsarz, and M. R. Salavatipour. Approximation algorithms for
nodeweighted buyatbulk network design. In Proceedings of the 18th
Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 12651274.
ACM, 2007. 
[84] 
M. T.
Hajiaghayi, R. Kleinberg, and
T. Leighton. Semioblivious routing: lower bounds. In Proceedings
of the 18th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
pages 929938. ACM, 2007. A brief announcement of this paper appeared in Proceedings
of 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA),
pages 234235. 
[85] 
A. Gupta,
M. T. Hajiaghayi, and A. Kumar. Stochastic
Steiner tree with nonuniform inflation. In Proceedings of the 10th
International Workshop on Approximation Algorithms for Combinatorial
Optimization (APPROX), pages 134148. Springer, 2007. 
[86] 
M.F.
Balcan, A. Blum, H. Chan, and M. T. Hajiaghayi. A theory of lossseaders:
making money by pricing below cost. In Proceedings of the 3rd
International Workshop on Internet and Network Economics (WINE), pages
293299. Springer, 2007. 
[87] 
M. T.
Hajiaghayi and K. Jain. The
prizecollecting generalized Steiner tree problem via a new approach of
primaldual schema. In Proceedings of the 17th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), pages 631640. ACM, 2006. 
[88] 
A. Gupta,
M. T. Hajiaghayi, and H. Räcke. Oblivious network design. In Proceedings
of the 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
pages 970979. ACM, 2006. 
[89] 
M. T.
Hajiaghayi, R. D. Kleinberg, T. Leighton,
and H. Räcke. New lower bounds for
oblivious routing in undirected graphs. In Proceedings of the 17th
Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 918927.
ACM, 2006. 
[90] 
M. T.
Hajiaghayi, R. Kleinberg, and
T. Leighton. Improved lower and upper bounds for universal TSP in
planar metrics. In Proceedings of the 17th Annual ACMSIAM Symposium
on Discrete Algorithms (SODA), pages 649658. ACM, 2006. 
[91] 
M. T.
Hajiaghayi, L. Li, V. S. Mirrokni, and M. Thottan. Bandwidth
sharing network design for multiclass traffic. In Proceedings of the
25th IEEE International Conference on Computer Communications (INFOCOM).
IEEE Computer Society, 2006. 
[92] 
M. T.
Hajiaghayi, K. Jain, L. C. Lau,
I. I. Mandoiu, A. Russell, and V. V.
Vazirani. Minimum multicolored subgraph problem in multiplex PCR primer set selection
and population haplotyping. In Proceedings
of International Workshop on Bioinformatics Research and Applications (IWBRA),
pages 758766. Springer, 2006. 
[93] 
E. D.
Demaine, M. T. Hajiaghayi,
and K. Kawarabayashi. Algorithmic graph
minor theory: decomposition, approximation, and coloring. In Proceedings
of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
pages 637646. IEEE Computer Society, 2005. 
[94] 
M. T.
Hajiaghayi, J. H. Kim, T. Leighton, and
H. Räcke. Oblivious routing in
directed graphs with random demands. In Proceedings of the 37th Annual
ACM Symposium on Theory of Computing (STOC), pages 193201. ACM, 2005. 
[95] 
E. D.
Demaine and M. T. Hajiaghayi.
Bidimensionality: new connections between
FPT algorithms and PTASs. In Proceedings of the 16th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), pages 590601. ACM, 2005. 
[96] 
M. T.
Hajiaghayi, R. Kleinberg, M. Mahdian, and D. C. Parkes.
Online auctions with reusable goods. In Proceedings of the 6th ACM
Conference on Electronic Commerce (EC), pages 165174. ACM, 2005. 
[97] 
K. Jain,
M. T. Hajiaghayi, and K. Talwar. The generalized deadlock resolution problem.
In Proceedings of the 32nd International Colloquium on Automata, Languages
and Programming (ICALP), pages 853865. Springer, 2005. Journal version
invited to Theoretical Computer Science special issue for
selected papers from ICALP 2005 though regretfully declined. 
[98] 
E. D.
Demaine and M. T. Hajiaghayi.
Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proceedings
of the 15th Annual ACMSIAM Symposium on Discrete Algorithms (SODA),
pages 840849. ACM, 2004. See Tech. Report MITLCSTR903 http://www.lcs.mit.edu/publications/specpub.php?id=1686
for a more complete version. 
[99] 
M. T.
Hajiaghayi, R. Kleinberg, and D. C. Parkes. Adaptive limitedsupply online auctions.
In Proceedings of the 5th ACM Conference on Electronic Commerce (EC),
pages 7180. ACM, 2004. 
[100]

E. D.
Demaine and M. T. Hajiaghayi.
Diameter and treewidth in minorclosed graph
families, revisited. Algorithmica,
40(3):211215, 2004. This was an invited talk at GD'04.
See the slides at http://wwwmath.mit.edu/~hajiagha/bidimensionality4.pdf
or http://wwwmath.mit.edu/~hajiagha/bidimensionality4.ppt

[101] 
M. T.
Hajiaghayi and G. B. Sorkin.
The Satisfiability Threshold of Random 3SAT Is
at Least 3.52. In arXiv:math.CO/0310193
v2 22 Oct 2003, 2003. See also IBM Research Report RC22942http://arxiv.org/pdf/math.CO/0310193,2003. 
[102]

E. D.
Demaine, M. T. Hajiaghayi,
and D. M. Thilikos. 1.5approximation for treewidth of graphs excluding a graph with one crossing
as a minor. In Proceedings of the 5th International Workshop on Approximation
Algorithms for Combinatorial Optimization (APPROX), pages 6780.
Springer, 2002. 
[103] 
M. T.
Hajiaghayi and M. Jamzad.
Simple, fast, and robust selflocalization in environments similar to the robocup environment. In Proceedings of the 18th
International Conference on CAD/CAM, Robotics and Factories of the Future
(CARS&FOF), pages 513522, 2002. 
[104]

M. Jamzad, S. B. Sadjad,
V. S. Mirrokni, M. Kazemi,
H. R. Chitsaz, A. Heydarnoori,
M. T. Hajiaghayi, and E. Chiniforooshan. A fast vision system for middle size
robots in RoboCup. In RoboCup
2001 International Symposium, pages 7180. Springer, 2001. Winner of the Best Engineering Challenge Paper
Award in RoboCup 2001. 
[105]

M. Jamzad, A. Foroughnassiraei,
M. T. Hajiaghayi, V. S. Mirrokni, R. Ghorbani,
A. Heydarnoori, M. Kazemi,
H. R. Chitsaz, F. Mobasser,
M. E. Moghaddam, M. Gudarzi,
and N. Ghaffarzadegan. A goal keeper for
middle size RoboCup. In RoboCup
2000: Robot Soccer World Cup IV, pages 583586. Springer, 2000. Submitted
Manuscripts 
[106] 
M. H.
Bateni, M. T. Hajiaghayi,
P. N. Klein, and C. Mathieu. A Polynomialtime approximation
scheme for planar multiway cut. Submitted,
2011. 
[107] 
C. Guo, M. T. Hajiaghayi,
D. Li, L. Li, V. Liaghat, H. Srzhz, H. Xue,
Y. Yang, and J. Yu. Rapid network application deployment
satisfying applicationwide, innetwork policies. Submitted, 2011. 
[108] 
S. Alaei, M. T. Hajiaghayi,
and V. Liaghat. Generalized online matching
in Prophetinequality setting with applications to ad allocation.
Submitted, 2011. 
[109] 
R. Chitnis, M. T. Hajiaghayi,
and D. Marx. Fixedparameter tractability of directed multiway cut parameterized by the size of the cutset. Submitted, 2011. 
[110] 
M. T.
Hajiaghayi, R. Khandekar,
G. Kortsarz, , and
Z. Nutov. Combinatorial algorithms for
capacitated network design problems. Submitted, 2011. 
[111] 
R. Chitnis, M. T. Hajiaghayi,
J. Katz, and K. Mukherjee. Gametheoretic
model for the DARPA network challenge. Submitted, 2011. Thesis 
[112]

M. T.
Hajiaghayi. The bidimensionality
theory and its algorithmic applications. PhD thesis, Department of
Mathematics, Massachusetts Institute of Technology, Cambridge, MA, U.S.A, May
2005. 
[113]

M. T.
Hajiaghayi. Algorithms for graphs of
(locally) bounded treewidth. Master's
thesis, Department of Computer Science, University of Waterloo, Waterloo, ON,
Canada, September 2001. Content of the thesis appeared in Journal
papers [52], [48], [34]. 
[114]

M. T.
Hajiaghayi. Multicasting and pseudomatching (in Persian). Bachelor's thesis,
Department of Computer Engineering, Sharif University of Technology, Tehran,
Iran, September 2000. Content of the thesis appeared in Journal paper [54]. Book &
Book Chapters 
[115] 
E. D.
Demaine and M. Hajiaghayi.
Approximation Schemes for Planar Graph Problems. In MingYang Kao
(Ed.): Encyclopedia of Algorithms, pages 5962. Springer, 2008. 
[116] 
E. D.
Demaine and M. Hajiaghayi.
Bidimensionality. In MingYang Kao (Ed.):
Encyclopedia of Algorithms, pages 8890. Springer, 2008. 
[117] 
Y. Ahmadi, M. T. Hajiaghayi,
and V. Mirrokni, editors. Iranian
Informatics Olympiad. Young Scholars Club Pub. Co., September 2000. Some Other
Manuscripts 
[118] 
M. T.
Hajiaghayi. Comparing of SGML documents.
April 2001. 
[119] 
M. T.
Hajiaghayi. Consecutive Ones Property.
December 2000. 
[120] 
M. T.
Hajiaghayi. Clustering algorithms in PBS.
April 2001. 
[121] 
M. T.
Hajiaghayi. Mathematical Markup Language.
February 2001. 