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
211-220. |
|
[2] |
M. T.
Hajiagahyi, R. Khandekar,
G. Kortsarz, and Z. Nutov.
Prize-collecting 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 71-84. |
|
[3] |
M. T.
Hajiaghayi, R. Khandekar,
and G. Kortsarz. Budgeted
red-blue 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 314-325. |
|
[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 23-34. |
|
[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 real-time 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 29-38. |
|
[7] |
M. H.
Bateni and M. T. Hajiaghayi.
Assignment problem in content distribution networks: unsplittable
hard-capacitated facility location. ACM Trans. Algorithms. To
appear. A preliminary version appeared in Proceedings of the 20th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, pages
805-814. |
|
[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 292-298. |
|
[9] |
M. H.
Bateni and M. T. Hajiaghayi.
Euclidean prize-collecting Steiner forest. Algorithmica.
To appear. A preliminary version appeared in Proceedings of the 9th Latin
American Theoretical Informatics Symposium (LATIN), 2010, pages
503-514. |
|
[10] |
M. H.
Bateni, M. T. Hajiaghayi, , A. Gerber, and S. Sen. Multi-VPN
Optimization for scalable routing via relaying. IEEE/ACM Trans. Netw., 18(5):1544-1556, 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):533-552, 2010. A preliminary version appeared in Proceedings of the
18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
2007, pages 278-287. |
|
[12] |
A. Archer,
M. Bateni, M. Hajiaghayi,
and H. Karloff. Improved approximation algorithms for
prize-collecting Steiner tree and TSP. SIAM J. Comput.,
40(2):309-332, 2011. A preliminary version appeared in Proceedings of the
50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2009, pages 427-436. |
|
[13] |
C. Chekuri, M. T. Hajiaghayi,
G. Kortsarz, and M. R. Salavatipour. Approximation algorithms for non-uniform
buy-at-bulk network design. SIAM J. Comput.,
39(5):1772-1798, 2010. A preliminary version appeared in Proceedings of
the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2006, pages 677-686. |
|
[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):216-228, 2010. A preliminary version
appeared in Proceedings of the 6th ACM International Symposium on Mobile
Ad Hoc Networking and Computing ( MOBIHOC),
May 2005, pages 309-319. |
|
[15] |
E. D.
Demaine, M. T. Hajiaghayi,
H. Mahini, A. S. Sayedi-Roshkhar,
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 ACM-SIAM Symposium on Discrete Algorithms (SODA),
January 2007, pages 258-267. |
|
[16] |
A. Gupta,
M. T. Hajiaghayi, V. Nagarajan,
and R. Ravi. Dial-a-ride from k-forest. ACM Trans.
Algorithms, 6(2), 2010. A preliminary version appeared in Proceedings
of the 15th Annual European Symposium on Algorithms (ESA),
October 2007, pages 241-252. |
|
[17] |
M. Charikar, M. T. Hajiaghayi,
H. Karloff, and S. Rao. l22 spreading
metrics for vertex ordering problems. Algorithmica,
56(4):577-604, 2010. A preliminary version appeared in Proceedings of the
17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
January 2006, pages 1018-1027. |
|
[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
301-312. |
|
[19] |
M. H.
Bateni and M. T. Hajiaghayi.
A note on subadditive network design. Oper. Res. Lett.,
37(5):339-344, 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):142-180, 2009. A preliminary version
appeared in Proceedings of the 17th Annual International Symposium on
Algorithms and Computation (ISAAC 2006), December 2006, pages
3-15. Winner of the best paper award in ISAAC 2006. |
|
[21] |
M. T.
Hajiaghayi, G. Kortsarz,
and M. R. Salavatipour. Approximating
buy-at-bulk and shallow-light k-Steiner trees. Algorithmica, 53(1):89-103, 2009. A preliminary
version appeared in Proceedings of the 9th International Workshop on
Approximation Algorithms for Combinatorial Optimization (APPROX),
August 2006, pages 153-163. |
|
[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):629-657, 2008. A preliminary
version appeared in Proceedings of the 37th ACM Symposium on Theory of
Computing (STOC), May 2005, pages 563-572. |
|
[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):1464-1483, 2008. A
preliminary version appeared in Proceedings of the 17th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA), January 2006, pages
162-171. |
|
[24] |
E. D.
Demaine and M. T. Hajiaghayi.
Linearity of grid minors in treewidth with
applications through bidimensionality. Combinatorica, 28(1):19-36, 2008. A preliminary
version appeared in Proceedings of the 16th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), January 2005, pages 682-689. |
|
[25] |
S. Butler,
M. T. Hajiaghayi, R. D. Kleinberg, and
T. Leighton. Hat guessing games. SIAM J. Discrete Math.,
22(2):592-605, 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):397-397, 2009 |
|
[26] |
N. Alon, M. Badoiu,
E. D. Demaine, M. Farach-Colton,
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
ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005,
pages 650-659. |
|
[27] |
E. D.
Demaine and M. T. Hajiaghayi.
The Bidimensionality theory and its algorithmic
applications. Special issue of Comput.
J. for selected survey-papers in Fixed-Parameter Tractability,
51(3):292-302, 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 Client-Server Load
Balancing without Global Information. SIAM J. Comput.,
37(4):1259-1279, 2007. A preliminary version appeared in Proceedings of
the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),January 2005, pages 197-206. 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
fault-tolerant topology control algorithms for wireless multi-hop networks.
IEEE/ACM Trans. Netw., 15(6):1345-1358,
2007. A preliminary version appeared in Proceedings of the 9th Annual
International Conference on Mobile Computing and Networking (MOBICOM),
September 2003, pages 300-312. |
|
[30] |
M. T.
Hajiaghayi, R. D. Kleinberg, T. Leighton,
and H. Räcke. Oblivious routing on
node-capacitated and directed graphs. ACM Trans. Algorithms, 3(4):Art. 51, 13, 2007. A preliminary version appeared in Proceedings
of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
January 2005, pages 782-790. 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):195-208, 2007. A
preliminary version appeared in Proceedings the 11th Conference on
Integer Programming and Combinatorial Optimization (
IPCO), June 2005, pages 349-361. |
|
[32] |
M. H.
Bateni, E. D. Demaine,
M. T. Hajiaghayi, and M. Moharrami. Plane embeddings of planar graph metrics.
Discrete Comput. Geom., 38(3):615-637, 2007.
A preliminary version appeared in Proceedings of the 22nd Annual ACM
Symposium on Computational Geometry (SOCG), June 2006, pages
197-206. |
|
[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):164-178, 2007. |
|
[34] |
M. T.
Hajiaghayi and N. Nishimura. Subgraph isomorphism, log-bounded
fragmentation, and graphs of (locally) bounded treewidth.
J. Comput. System Sci., 73(5):755-768, 2007.
A preliminary version appeared in Proceedings of the 27th International
Symposium on Mathematical Foundations of Computer Science (MFCS),
August 2002, pages 305-318. |
|
[35] |
E. D.
Demaine and M. T. Hajiaghayi.
Quickly deciding minor-closed parameters in general graphs. European
J. Combin., 28(1):311-314, 2007. |
|
[36] |
M. Badoiu, E. D. Demaine,
M. T. Hajiaghayi, and P. Indyk. Low-dimensional embedding with extra
information. Special issue of Discrete Comput. Geom. for selected papers from SOCG 2004,
36(4):609-632, 2006. A preliminary version appeared in Proceedings of the
20th ACM Symposium on Computational Geometry (SOCG), June 2004,
pages 320-329. |
|
[37] |
E. D.
Demaine, M. T. Hajiaghayi,
and D. M. Thilikos. The bidimensional
theory of bounded-genus graphs. SIAM J. Discrete Math.,
20(2):357-371, 2006. A preliminary version appeared in Proceedings of the
29th International Symposium on Math. Foundations of Computer Science ( MFCS), 2004, pages 191-203. |
|
[38] |
M. Bahramgiri, M. T. Hajiaghayi,
and V. S. Mirrokni. Fault-Tolerant and
3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop
Networks. ACM/Kluwer Wireless Networks,
12(2):179-188, 2006. A preliminary version appeared in Proceedings of the
11th IEEE International Conference on Computer Communications and Networks
( ICCCN), October 2002, pages 392-398. |
|
[39] |
M. T.
Hajiaghayi and T. Leighton. On the max-flow
min-cut ratio for directed multicommodity flows.
Theoret. Comput.
Sci., 352(1-3):318-321, 2006. |
|
[40] |
M. T.
Hajiaghayi and H. Räcke.
An O(sqrt(n))-approximation
algorithm for directed sparsest cut. Inform. Process. Lett., 97(4):156-160, 2006. |
|
[41] |
E. D.
Demaine, F. V. Fomin,
M. T. Hajiaghayi, and D. M. Thilikos. Subexponential
parameterized algorithms on bounded-genus graphs and H-minor-free
graphs. J. ACM, 52(6):866-893, 2005. A preliminary version
appeared in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), January 2004, pages 830-839. |
|
[42] |
E. D.
Demaine, F. V. Fomin,
M. T. Hajiaghayi, and D. M. Thilikos. Fixed-parameter algorithms for (k,r)-center in
planar graphs and map graphs. ACM Trans. Algorithms, 1(1):33-47,
2005. A preliminary version appeared in Proceedings of the 30th
International Colloquium on Automata, Languages and Programming ( ICALP), July 2003, pages 829-844. |
|
[43] |
E. D.
Demaine, M. T. Hajiaghayi,
and D. M. Thilikos. Exponential speedup of
fixed-parameter algorithms for classes of graphs excluding single-crossing
graphs as minors. Algorithmica,
41(4):245-267, 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
vertex-orderings of graphs. Discrete Appl. Math., 148(1):27-48,
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):501-511, 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):502-545, 2004. A preliminary version appeared in Proceedings of
14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
January 2003, pages 364-373. |
|
[100] |
E. D.
Demaine and M. T. Hajiaghayi.
Diameter and treewidth in minor-closed graph
families, revisited. Algorithmica,
40(3):211-215, 2004. |
|
[48] |
E. D.
Demaine, M. T. Hajiaghayi,
N. Nishimura, P. Ragde, and D. M. Thilikos. Approximation algorithms for classes of
graphs excluding single-crossing graphs as minors. J. Comput. System Sci., 69(2):166-195, 2004. |
|
[49] |
Y. Ganjali and M. T. Hajiaghayi.
Characterization of networks supporting multi-dimensional linear interval
routing schemes. Theoret. Comput. Sci., 326(1-3):103-116, 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(1-3):475-480, 2003. |
|
[51] |
M. T.
Hajiaghayi, M. Mahdian,
and V. S. Mirrokni. The facility location
problem with general cost functions. Networks, 42(1):42-47, 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):891-896, 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. RoboCup-2001: The Fifth Robotic Soccer
World Championships. AI Magazine, 23(1):55-68, 2002. |
|
[54] |
M. Ghodsi, M. T. Hajiaghayi,
M. Mahdian, and V. S. Mirrokni.
Length-constrained path-matchings in graphs.
Networks, 39(4):210-215, 2002. |
|
[55] |
M. T.
Hajiaghayi and Y. Ganjali.
A note on the consecutive ones submatrix problem.
Inform. Process. Lett.,
83(3):163-166, 2002. |
|
[56] |
M. T.
Hajiaghayi, N. Nishimura, P. Ragde, and D. M. Thilikos.
Fast approximation schemes for K3,3-minor-free
or K5-minor-free 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 158-163. |
|
[57] |
M. T.
Hajiaghaee, E. S. Mahmoodian,
V. S. Mirrokni, A. Saberi,
and R. Tusserkani. On the simultaneous
edge-coloring conjecture. Discrete Math., 216(1-3):267-272, 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 H-minor-free graphs and its algorithmic
applications. In Proceedings of the 43rd Annual ACM Symposium on
Theory of Computing (STOC), pages 441-450. 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 269-278. 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 135-136. 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 581-585. 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. Disjoint-path facility location: theory and practice.
In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments
(ALENEX), pages 60-74. SIAM, 2011. |
|
[65] |
M. Andrews,
M. T. Hajiaghayi, H. Karloff, and
A. Moitra. Capacitated metric labeling.
In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 976-995. Society for Industrial and Applied
Mathematics, 2011. |
|
[66] |
M. H.
Bateni, C. Chekuri,
A. Ene, M. T. Hajiaghayi,
N. Korula, and D. Marx. Prize-collecting
network design on planar graphs. In Proceedings of the 22nd Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1028-1049.
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 106-113. 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 odd-minor-free graphs. In Proceedings
of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 329-344. 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 67-78. 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 39-52. 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 219-231. Springer, 2010. |
|
[72] |
M. T.
Hajiaghayi and A. A. Nasri.
Prize-collecting Steiner networks via iterative rounding. In Proceedings
of the 9th Latin American Theoretical Informatics Symposium (LATIN),
pages 515-526. 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 632-639. Springer, 2009. |
|
[74] |
K. Kawarabayashi, E. D. Demaine,
and M. T. Hajiaghayi. Additive
approximation algorithms for list-coloring minor-closed class of graphs.
In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1166-1175. Society for Industrial and Applied
Mathematics, 2009. |
|
[75] |
J. Erman, A. Gerber, M. T. Hajiaghayi,
D. Pei, and O. Spatscheck. Network-aware
forward caching. In Proceedings of the 18th International Conference
on World Wide Web (WWW), pages 291-300. ACM, 2009. |
|
[76] |
E. D.
Demaine, M. T. Hajiaghayi,
and P. Klein. Node-weighted Steiner tree and group Steiner tree in
planar graphs. In Proceedings of the 36th International Colloquium on
Automata, Languages and Programming (ICALP), pages 328-340. Springer,
2009. |
|
[77] |
E. D.
Demaine, M. T. Hajiaghayi,
and K. Kawarabayashi. Node-weighted Steiner
tree and group Steiner tree in planar graphs. In Proceedings of the
36th International Colloquium on Automata, Languages and Programming (ICALP),
pages 316-327. Springer, 2009. |
|
[78] |
E. D.
Demaine, M. T. Hajiaghayi,
and D. Marx. Minimizing movement: fixed-parameter tractability.
In Proceedings of the 17th Annual European Symposium on Algorithms (ESA),
pages 718-729. 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 373-382. 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 21-34. 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 58-65. AAAI Press, 2007. |
|
[82] |
E. D.
Demaine, M. Ghodsi,
M. T. Hajiaghayi, A. S. Sayedi-Roshkhar, 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 46-54. ACM, 2007. Journal version submitted to Journal
of Scheduling. |
|
[83] |
C. Chekuri, M. T. Hajiaghayi,
G. Kortsarz, and M. R. Salavatipour. Approximation algorithms for
node-weighted buy-at-bulk network design. In Proceedings of the 18th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265-1274.
ACM, 2007. |
|
[84] |
M. T.
Hajiaghayi, R. Kleinberg, and
T. Leighton. Semi-oblivious routing: lower bounds. In Proceedings
of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 929-938. ACM, 2007. A brief announcement of this paper appeared in Proceedings
of 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA),
pages 234-235. |
|
[85] |
A. Gupta,
M. T. Hajiaghayi, and A. Kumar. Stochastic
Steiner tree with non-uniform inflation. In Proceedings of the 10th
International Workshop on Approximation Algorithms for Combinatorial
Optimization (APPROX), pages 134-148. Springer, 2007. |
|
[86] |
M.-F.
Balcan, A. Blum, H. Chan, and M. T. Hajiaghayi. A theory of loss-seaders:
making money by pricing below cost. In Proceedings of the 3rd
International Workshop on Internet and Network Economics (WINE), pages
293-299. Springer, 2007. |
|
[87] |
M. T.
Hajiaghayi and K. Jain. The
prize-collecting generalized Steiner tree problem via a new approach of
primal-dual schema. In Proceedings of the 17th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA), pages 631-640. ACM, 2006. |
|
[88] |
A. Gupta,
M. T. Hajiaghayi, and H. Räcke. Oblivious network design. In Proceedings
of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 970-979. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 918-927.
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 ACM-SIAM Symposium
on Discrete Algorithms (SODA), pages 649-658. ACM, 2006. |
|
[91] |
M. T.
Hajiaghayi, L. Li, V. S. Mirrokni, and M. Thottan. Bandwidth
sharing network design for multi-class 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 758-766. 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 637-646. 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 193-201. ACM, 2005. |
|
[95] |
E. D.
Demaine and M. T. Hajiaghayi.
Bidimensionality: new connections between
FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA), pages 590-601. ACM, 2005. |
|
[96] |
M. T.
Hajiaghayi, R. Kleinberg, M. Mahdian, and D. C. Parkes.
Online auctions with re-usable goods. In Proceedings of the 6th ACM
Conference on Electronic Commerce (EC), pages 165-174. 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 853-865. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 840-849. ACM, 2004. See Tech. Report MIT-LCS-TR-903 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 limited-supply online auctions.
In Proceedings of the 5th ACM Conference on Electronic Commerce (EC),
pages 71-80. ACM, 2004. |
|
[100]
|
E. D.
Demaine and M. T. Hajiaghayi.
Diameter and treewidth in minor-closed graph
families, revisited. Algorithmica,
40(3):211-215, 2004. This was an invited talk at GD'04.
See the slides at http://www-math.mit.edu/~hajiagha/bidimensionality4.pdf
or http://www-math.mit.edu/~hajiagha/bidimensionality4.ppt
|
|
[101] |
M. T.
Hajiaghayi and G. B. Sorkin.
The Satisfiability Threshold of Random 3-SAT 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.5-approximation 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 67-80.
Springer, 2002. |
|
[103] |
M. T.
Hajiaghayi and M. Jamzad.
Simple, fast, and robust self-localization 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 513-522, 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 71-80. 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 583-586. Springer, 2000. Submitted
Manuscripts |
|
[106] |
M. H.
Bateni, M. T. Hajiaghayi,
P. N. Klein, and C. Mathieu. A Polynomial-time 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 application-wide, in-network policies. Submitted, 2011. |
|
[108] |
S. Alaei, M. T. Hajiaghayi,
and V. Liaghat. Generalized online matching
in Prophet-inequality setting with applications to ad allocation.
Submitted, 2011. |
|
[109] |
R. Chitnis, M. T. Hajiaghayi,
and D. Marx. Fixed-parameter 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. Game-theoretic
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 Ming-Yang Kao
(Ed.): Encyclopedia of Algorithms, pages 59-62. Springer, 2008. |
|
[116] |
E. D.
Demaine and M. Hajiaghayi.
Bidimensionality. In Ming-Yang Kao (Ed.):
Encyclopedia of Algorithms, pages 88-90. 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. |