pub.html

Publications :

Journal Articles:

23 E.D. Demaine; Hajiaghayi, M.T.; Fomin, F.V.;Thilikos, D.;

Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs,
Journal of the ACM. Vol 52, No 6, pp. 866-893. A preliminary version appeared in the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 11-13, 2004, New Orleans, pp. 830-839.

22 M. Badoiu; E.D. Demaine; M.T. Hajiaghayi; P. Indyk;

Low Dimensional Embedding with Extra Information,
A special issue of Discrete & Computational Geometry for selected papers from SoCG 2004. To appear. A preliminary version appeared in the 20th ACM Symposium on Computational Geometry (SoCG), June 9 - 11, 2004, New York. pp. 320-329.

21 E.D. Demaine; Hajiaghayi, M.T.; Thilikos, D.;

The Bidimensional Theory of Bounded-Genus Graphs,
To appear in Siam Journal on Discrete Mathematics. A preliminary version appeared in the 29th International Symposium on Math. Foundations of Computer Science, 2004, Prague, Europe, 2004. pp. 191-203.

20 E.D. Demaine; M.T. Hajiaghayi;

Quickly Deciding Minor-Closed Parameters in General Graphs,
To appear in European Journal of Combinatorics.

19 Hajiaghayi, M.T.; Leighton, F.T.;

On the max-flow min-cut ratio for directed multicommodity flows,
Theoretical Computer science, Vol 352(1--3): 318-321, 2006.

18 M.T. Hajiaghayi; H. Raecke;

An O(sqrt{n})-Approximation Algorithm For Directed Sparsest Cut,
Information Processing Letters, Vol 97, No. 4, pp. 156-160, 2006.

17 Hajiaghayi, M. T.; Bahramgiri, M.; Mirrokni, V. S.;

Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks,
ACM/Kluwer Wireless Networks. To appear. A preliminary version appeared in the 11th IEEE International Conference on Computer Communications and Networks, October, 2002, pp. 392-398.

16 Hajiaghayi, M.T.; Demaine, E.D.; Fomin, F.V.;Thilikos, D.;
Fixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs,
ACM Transactions on Algorithms. Vol 1, No 1, pp. 1-15. A preliminary version appeared in 30th International Colloquium on Automata, Languages and Programming (ICALP), July, 2003, pp. 829-844.
15 Hajiaghayi, M.T; Biedl, T; Chan. T; Ganjali, Y; Wood, D.R.;

Balanced vertex-orderings of graphs,
Discrete Applied Mathematics. Vol 148, No 1, pp. 27-48, 2005.

14 Hajiaghayi, M.T.; Demaine, E.D.; Thilikos, D.;
Exponential Speedup of Fixed Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors,
Algorithmica, Vol 41, No. 4, pp. 245-267, 2005. A preliminary version appeared in Annual International Symposium on Algorithms and Computation, November, 2002.

13 Hajiaghayi, M.T.; Demaine, E.D.; Fomin, F.V.;Thilikos, D.;

Bidimensional Parameters and Local Treewidth,
Siam Journal on Discrete Mathematics. Vol 18, No. 3, pp. 501-511, 2004. Preliminary versions appeared in Latin American Theoretical Informatics, April, 2004 and Annual European Symposium on Algorithms, September, 2003.

12 Hajiaghayi, M. T.; Ganjali Y.;

Characterization of Networks Supporting Multi-dimensional Linear Interval Routing Schemes
Theoretical Computer Science, Vol 326, No. 1-3, pp. 103-116.

11 Hajiaghayi,M.T.; Demaine, E.D.;

Diameter and Treewidth in Minor-Closed Graph Families, Revisited,
Algorithmica. Vol 40, No. 3, pp. 211-215, 2004.

10 Hajiaghayi, M.T.; Demaine, E.D.; Nishimura, N; Ragde, P; Thilikos, D.;

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
Journal of Computer and System Sciences, Vol 69, No. 2, pp. 166-195, 2004.

9 Hajiaghayi, M. T.; Coppersmith, D.; Gamarnik, D.; Sorkin, G. B.;

Random MAX SAT, Random MAX CUT, and Their Phase Transitions
A special issue of Random Structures and Algorithms, Vol 24, Issue 4 , pp. 502-545. A preliminary version appeared in Proceedings of Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 364-373, January 12-14, 2003, Baltimore.

8 Hajiaghayi, M.T.; Hajiaghayi, M.;

On the bounded fragmentation property and its applications,

European Journal of Combinatorics, Vol 24, No. 7, pp. 891-896, 2003. A preliminary version appeared in Proc. Euroconference on Combinatorics, Graph Theory and Applications, EuroCOMB'03, Sep. 2003.

7 Hajiaghayi, M. T.; Mahdian, M.; Mirrokni, V.S.;

The facility location problem with general cost functions,
Networks, Vol. 42, No. 1, pp. 42-47, 2003.

6 Hajiaghayi, M.T.; Biedl, T.; Buss, J.F.; Demaine, E.D., Demaine, M.L.; Vinar,T.;

Palindrome Recognition Using a Multidimensioinal Tape,
Theoretical Computer science, Vol. 302, No. 1-3, pp. 475-480, 2003.

5 Hajiaghai¹, M.T.; Veloso, M.; Balch, T.; Stone, P.; Kitano, H.; Yamasaki, F.; Endo, K.; Asada, M; Jamzad, M; Sadjad, B. S.; Mirrokni, V. S.; Kazemi, M.; Chitsaz, H.; Heydarnoori, A.; Chiniforooshan E.;

RoboCup-2001 -The Fifth Robotic Soccer World Chapmpionships.
AI magazine, Vol. 23, No. 1, pp. 55-68, 2002.

4 Hajiaghayi, M.T.; Ghodsi, M; Mahdian, M.; Mirrokni, V.S.;

Path-matching in graphs with length constraints,
Networks, Vol 39, No. 4, pp. 210-215, 2002.

3 Hajiaghayi, M.T.; Ganjali Y.;

A Note on the Consecutive Ones Submatrix Problem,
Information Processing Letters, Vol 83, No. 3, pp. 163-166, 2002.

2 Hajiaghayi, M.T; Nishimura, N; Ragde, P; Thilikos, D.;

Fast approximation schemes for K_{3,3}-minor-free or K_{5}-minor-free graphs,

Electronic Notes in Discrete Mathematics Vol 10, 2001. A preliminary version appeared in Proc. Euroconference on Combinatorics, Graph Theory and Applications, EuroCOMB'01, Sep. 2001: 158-163.

1 Hajiaghaee¹, M. T.; Mahmoodian, E. S.; Mirrokni, V. S.; Saberi, A.; Tusserkani;

On the simultaneous edge-coloring conjecture,
Discrete Mathematics 216 (2000), no. 1-3, 267--272.

Conference and Submitted Papers (excluding those that have already appeared in journals)

38 M.T. Hajiaghayi; G. Kortsarz; M. R. Salavatipour;

Polylogarithmic approximation algorithm for non-uniform multicommodity buy-at-bulk, Manuscipt 2005.

37 M.T. Hajiaghayi; G. Kortsarz; M. R. Salavatipour;

Approximating buy-at-bulk k-Steiner trees, Submitted 2005.

35 S. Butler; M.T. Hajiaghayi; R.D. Kleinberg; T. Leighton;

Hat Guessing Games, Submitted to SIAM Journal on Discrete Mathematics.

34 E.D. Demaine; M.T. Hajiaghayi;

Bidimensionality, mapgraphs and grid minors, Submitted to Journal of Combinatorial Theory, Series B.

33 Mohammad T. Hajiaghayi; Jeong H. Kim;

Tight Bounds For Random MAX 2-SAT, Submitted to Random Structures and Algorithms.

36 E.D. Demaine; M.T. Hajiaghayi; H. Mahini; S. Oveisgharan; A. Seyedi; M. Zadimoghadam;

Minimizing movement,
In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 7-9, 2007, New Orleans, To appear.

38 C. Chekuri; M.T. Hajiaghayi; G. Kortsarz; M. R. Salavatipour;

Polylogarithmic approximation algorithm for non-uniform multicommodity buy-at-bulk, Manuscipt 2005.

37 M.T. Hajiaghayi; G. Kortsarz; M. R. Salavatipour;

Approximating Buy-at-Bulk and Shallow-light k-Steiner trees,
Approximating buy-at-bulk k-Steiner trees, Submitted 2005.

32 V. Bahl; M.T. Hajiaghayi; K. Jain; V.S. Mirrokni; L. Qui; A. Saberi;

Market models and algorithms for distributed load balancing in wireless LAN,

In Proceedings of the 7th ACM Conference on Electronic Commerce (EC), Ann Arbor, Michigan, June 2006, To appear.

31 M.S. Bateni; E.D. Demaine; M.T. Hajiaghayi; M. Moharrami;

Plane embeddings of planar graph metrics,

In Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG), Ann Arbor, Michigan, June 2006, To appear.

30 M.T. Hajiaghayi; L.E. Li; V.S. Mirrokni; M. Thottan;

Bandwidth Sharing VPN Network Design for Multi-class Traffic with Application to VoIP, in Proceedings of the 25th Annual IEEE Conference on Computer Communications (INFOCOM), Barcelona, Spain, April 23-29, 2006, To appear.

29 E.D. Demaine, U. Feige, M.T. Hajiaghayi; M.R. Salavatipour;

Combination can be hard: approximability of the unique coverage problem,
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, Miami, Florida, January 22-24, 2006, To appear. See the journal version.

28 M. Charikar; M.T. Hajiaghayi; H. Karloff; S. Rao;

l₂² spreading metrics for vertex ordering problems,
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, Miami, Florida, January 22-24, 2006, To appear. Journal version submitted to Siam Journal on Computing.

27 A. Gupta; M.T. Hajiaghayi; H. Raecke;

Oblivious Network Design,
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, Miami, Florida, January 22-24, 2006, To appear.

26 M.T. Hajiaghayi; R. D. Kleinberg; T. Leighton; H. Raecke;

New lower bounds for oblivious routing in undirected graphs,
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, Miami, Florida, January 22-24, 2006, To appear.

25 M.T. Hajiaghayi; R. D. Kleinberg; 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), Vancouver, Miami, Florida, January 22-24, 2006, To appear.

24 M.T. Hajiaghayi; 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), Vancouver, Miami, Florida, January 22-24, 2006, To appear.

23 M.T. Hajiaghayi; K. Jain; K. Konwar; L.C. Lau; I.I. Mandoiu; 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), University of Reading, UK, May 2006, To appear.

22 E.D. Demaine; M.T. Hajiaghayi; K Kawarabayashi

Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring

In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, October 23-25, 2005, pp. 637-646.

21 K. Jain; M.T. Hajiaghayi; K. Talwar;

The Generalized Deadlock Resolution Problem,
In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005, pp. 853-865. Journal version invited to Theoretical Computer Science special issue for selected papers from ICALP 2005.

20 J.L. Bredin; E.D. Demaine; M.T. Hajiaghayi; D. Rus;

Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance, In Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Urbana-Champaign, IL, May 2005, pp. 309--319.

19 U. Feige; M.T. Hajiaghayi; J.R. Lee;

Improved approximation algorithms for minimum-weight vertex separators,

In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), pp. 563-572, Baltimore, MD, May 21-24, 2005. Journal version invited to Siam Journal on Computing special issue for selected papers from STOC 2005.

18 M.T. Hajiahgayi; J.H. Kim; T. Leighton; H. Raecke;

Oblivious routing in directed graphs with random demands,

In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), pp. 193-201, Baltimore, MD, May 21-24, 2005.

17 M.T. Hajiaghayi; R.D. Kleinberg; M. Mahdian; D.C. Parkes;

Online Auctions with Re-usable Goods,
In Proceedings of the 6th ACM Conference on Electronic Commerce (EC), pp. 165-174, Vancouver, Canada, June 5-8, 2005.

16 M.T. Hajiahgayi; G. Kortsarz; V. S. Mirrokni; Z. Nutov;

Power Optimization for Connectivity Problems,

In Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 349-361, Berlin, Germany, June 2005. Journal version invited to Mathematical Programming, Series B special issue for selected papers from IPCO 2005.

15 E.D. Demaine; M.T. Hajiaghayi;

Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth,
Invited presentation in the 12th International Symposium on Graph Drawing(GD), pp. 517-533, New York City, New York, 2004. This paper surveys our theory of bidimensionality and its known combinatorial and algorithmic results of this theory. See the Slides here .pdf , .ppt.

14 E.D. Demaine; M.T. Hajiaghayi;

Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, pp. 682-689. Journal version version submitted to Journal of the ACM.

13 E.D. Demaine; M.T. Hajiaghayi;

Bidimensionality: New Connections between FPT Algorithms and PTASs (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, pp. 590-601.

12 N. Alon; M. Badoiu; E.D. Demaine; M. Farach-Colton; M.T. Hajiaghayi; A. Sidiropoulos;

Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, pp. 650-659.
Journal version to submitted to Siam Journal on Computing.

11 M.T. Hajiaghayi;Robert D. Kleinberg; Tom Leighton; Harald Raecke;

Oblivious Routing on Node-Capacitated and Directed Graphs (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, pp. 782-790.
Journal version submitted to ACM Transactions on Algorithms.
Invitation to Journal of Scheduling special issue for selected papers from SODA 2005 regretfully declined.

10 B. Awerbuch; M.T. Hajiaghayi; R.D. Kleinberg; T. Leighton;

Online Client-Server Load Balancing Without Global Information (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, 197-206.
Journal version submitted to Siam Journal on Computing.
Invitation to Journal of Scheduling special issue for selected papers from SODA 2005 regretfully declined.

9 Hajiaghayi, M.T.; Kleinberg, R.; Parkes, D.C.;

Adaptive Limited-Supply Online Auctions (full paper),
Proc. ACM Conference on Electronic Commerce (EC), pp. 71-80, May 17-20, 2004. New York.

8 Hajiaghayi, M.T.; Demaine, E.D.;

Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications (full paper),
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 840-849, January 11-13, 2004, New Orleans. See Tech. Report MIT-LCS-TR-903 for a more complete version.

7 Hajiaghayi, M.; Immorlica, N.; Mirrokni, V.S.;

Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks,

in Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MOBICOM), pp. 300-312, September 15-18 2003, San Diego. Journal version submitted to IEEE/ACM Transactions on Networking.

6 Hajiaghayi, M.T.; Sorkin G.B.;

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52,
arXiv:math.CO/0310193 v2 22 Oct 2003. See also IBM Research Report RC22942, 2003.

5 Hajiaghayi, M.T.; Demaine, E.D.; Thilikos, D.;

1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor,
Proc. the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), September 17-21, 2002, Italy, Lecture Notes in Computer Science 2462, pp. 67-80, 2002.

4 Hajiaghayi, M.T; Nishimura, N.;

Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth,
Proc. the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS), August 26-30, 2002, Poland, Lecture Notes in Computer Science 2420, pp. 305-318, 2002. Journal version submitted to Journal of Computer and System Sciences.

3 Hajiaghayi, M.T; Jamzad, M.;

Simple, fast, and robust self-localization in environments similar to the robocup environment,
Proc. the 18th International Conference on CAD/CAM, Robotics and Factories of the future (CARS&FOF), Porto, Portugal, vol (2), pp:513-522, 2002. Journal version submitted.

2 Hajiaghai¹, M.T.; Jamzad, M; Sadjad, B. S.; Mirrokni, V. S.; Kazemi, M.; Chitsaz, H.; Heydarnoori, A.; Chiniforooshan E.;

A Fast Vision System for Middle Size Robots in RoboCup,
The RoboCup 2001 International Symposium, winner of The Best Engineering Challenge Award, Lecture Notes in Computer Science 2377, pp. 71-80, 2002.

1 Hadji Aaghai¹, T; Jamzad, M.; Foroughnassiraei, A.; Mirrokni, V.S.; Ghorbani, R.; Heydar Noori, A.; Kazemi, M.; Chitsaz, H.; Mobasser, F.; Ebraahimi M.; Gudarzi, M; Ghaffarzadeganet. N.;

A Goal Keeper for Middle Size RoboCup,
RoboCup 2000, Lecture Notes in Computer Science 2019, 2001: 583-586.

Thesis

Hajiaghayi, M.T.;

The bidimensionality Theory and Its Algorithmic Applications,
Ph.D. Thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, U.S.A., May 2005.

Hajiaghayi, M.T.;

Algorithms for Graphs of (Locally) Bounded Treewidth,
M.Sc. Thesis, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, September 2001.

Content of the thesis appeared in Journal papers [8], [10] (partially), and Conference paper [4].

Hajiaghayi, M.T.;

Multicasting and Pseudomatching (in Persian),
B.Sc. Thesis, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran, September 2000

Content of the thesis appeared in Journal paper [4].

Book

Iranian Informatics Olympiad shared with V.S. Mirrokni and Y. Ahmadi, Young Scholars Club Pub. Sept, 2000.

Some Other Manuscripts

Hajiaghayi, M.T.; Comparing of SGML documents, Appril 2001.

Hajiaghayi, M.T.; Consecutive Ones Property, December 2000.

Hajiaghayi, M.T.; Clustering algorithms in PBS, Appril 2001.

Hajiaghayi, M.T.; Mathematical Markup Language, Feb. 2001.

Some educational papers (in Persian) published in Olympiad Quarterly and The Way to Olympiad magazines.

¹ :The name is mis-spelled a bit in the publication.