Publications categorized by subject (the papers in each category ranked by their importance):

A. The Bidimensionality Theory (See Subsection 1.1 of my Research Statement )

Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewid,
Invited presentation in the 12th International Symposium on Graph Drawing(GD), 2004, New York City, 2004.  See the Slides here.

This paper is a survey of our (joint work with Erik Demaine) theory of bidimensionality and its known combinatorial and algorithmic results of this theory. Minor(contraction)-closed bidimensional problems include lots of problems e.g. feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal problems, dominating set, edge dominating set, R-dominating set, diameter, connected dominating set, connected edge dominating set, and connected R-dominating set  See the Subsection  1.1. of my research statement for a  breif introduction to this theory (the more detailed version is this survey). The bidimensionality theory unifies and improves several previous results. The theory is based on algorithmic and combinatorial extensions to parts of the Robertson-Seymour Graph Minor Theory, in particular initiating a parallel theory of graph contractions.  The foundation of this work is the topological theory of drawings of graphs on surfaces. In this theory, we improve and generalize several results of others including Seymour, Robertson, Thomas, Alon, Eppstein, Bodlaender, Niedermeier, Reed, Lipton, Tarjan, Baker, Diestel, Thomassen, etc --namely linearity of local treewidth (the previous bound was doubly-exponential), linearity of the size of the grid minor in terms of treewidth, reproving the separator theorem, tight parameter-treewidth bounds for a general class of parameters and  PTASs for general  minimization problems using the separator approach in minor closed graph families,  some of these problems were unsolved despite frequent study for over 15 years.

Below I highlight 11 papers in which this theory has been developed (in order of their importance) and mention a brief description about their importance.
Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs (full paper) ,
Proc. the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 830-839, January 11-13, 2004, New Orleans.  See Tech. Report MIT-LCS-TR-905 for a more complete version. Journal version submitted to Journal of the ACM.

This is the first paper which officially introduces the concept of bidimensionality and its numeros applications in designing subexponential parameterized algorithms.
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, To appear. Journal version submitted to Combinatorica.

We prove that any H-minor-free graph, for a fixed graph H,  of treewidth w has an Omega(w) \times Omega(w) grid graph as a minor.  Thus grid minors suffice to certify that H-minor-free graphs   have large treewidth, up to constant factors. This strong relationship was previously known for the special cases  of planar graphs and bounded-genus graphs,  and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has  many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms.
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, To appear.

We demonstrate a new connection between fixed-parameter tractability and approximation algorithms for combinatorial optimization problems on planar graphs and their generalizations.  Specifically, we extend the theory of bidimensionality to show that essentially all such problems have both subexponential fixed-parameter algorithms and PTASs. We obtain PTASs for all bidimensional problems in planar graphs and certain generalizations; of particular interest are our results for the two well-known problems of connected dominating set and general feedback vertex set  for planar graphs and their generalizations, for which PTASs were not known to exist. Our techniques generalize and in some sense unify the two main previous approaches for designing PTASs in planar graphs, namely, the Lipton-Tarjan separator approach [FOCS'77] and the Baker layerwise decomposition approach [FOCS'83].
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications (full paper),
Proc. 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.

We solve an open problem posed by Eppstein in 1995 and re-enforced by Grohe concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local treewidth if the subgraph induced by vertices within distance r of any vertex has treewidth bounded by a function of r (not n). Eppstein  characterized minor-closed families of graphs with bounded local treewidth as precisely minor-closed families that minor-exclude an apex graph, where an apex graphone vertex whose removal leaves a planar graph. In particular, Eppstein showed that all apex-minor-free graphs have bounded local treewidth, but his bound is doubly exponential in~$r$, leaving open whether a tighter bound could be obtained. We improve this doubly exponential bound to a linear bound, which is optimal. In particular, any minor-closed graph family with bounded local treewidth has linear local treewidth. Our bound generalizes previously known linear bounds for special classes of graphs proved by several authors. As a consequence of our result, we obtain substantially faster polynomial-time approximation schemes for a broad class of problems in apex-minor-free graphs, improving the running time from 2^{2^{2^{O(1/epsilon)}}} n^{O(1)} to 2^{O(1/epsilon)} n^{O(1)}.
Bidimensionality for planar graphs (without mentioning the name) first very briefly has been mentioned in this  paper. Also for the first time, in this paper, we obtain subexponential fixed parameter algorithms for graphs (e.g., map graphs) which do not necessarily exlclude a fixed minor.
Bidimensional Parameters and Local Treewidth,
Siam Journal on Discrete Mathematics. Vol 18, No. 3, pp. 501-511, 2004.

Bidimensionality in apex-minor-free graphs (a.k.a. minor-closed classes of graphs of locally bounded treewidth) for a general set of graph parameters introduced in this paper.
The Bidimensional Theory of Bounded-Genus Graphs,
Proc. the 29th International Symposium on Math. Foundations of Computer Science, 2004, Prague, Europe, 2004. pp. 191-203. Journal version submitted to Siam Journal on Discrete Mathematics.

A more refined version of Bidimensionality in bounded-genus graphs for a general set of graph  parameters introduced in this paper. Also our results is a step  toward a theory of graph contractions analogous to the seminal theory of graph minors by Robertson and Seymour.
Diameter and Treewidth in Minor-Closed Graph Families, Revisited,
Algorithmica. Vol 40, No. 3, pp. 211-215, 2004.

This paper considers the relation of diameter, a contraction-closed bidimensional parameter, and treewidth. Here we reprove a characterization result of Eppstein with a much simpler proof. In addition, the relation between treewidth and diameter is slightly better and explicit (see the big improvement on this bound from doubly exponential to linear in a paper above.)

This  paper  was the first paper in this series of papers, in which the concept of minor (contraction)-closed parameters (i.e. those parameters of the graph which do not increase when we take a minor (contraction) of a graph) was initiated.

Quickly Deciding Minor-Closed Parameters in General Graphs, Submitted to European Journal of Combinatorics, 2004.

We construct algorithms for deciding essentially any minor-closed parameter,  with explicit time bounds.  This result strengthens previous results by  Robertson and Seymour, Frick and Grohe, and  Fellows and Langston toward obtaining fixed-parameter algorithms for a general class of parameters.

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.

B. Vertex Separator, Approximating Treewidth, and Max-Flow Min-Cut Relation (See Subsection 1.2 of my Research Statement )

             Improved approximation algorithms for minimum-weight vertex separators,
            In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Baltimore, MD, May 21-24, 2005, To appear.
We develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces.  Unlike in the edge case, we show that embeddings into L_1 (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an O(\sqrt{\log n}) approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be \Theta(\sqrt{\log n}). We also prove variousapproximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded minor family of graphs. These results have a number of applications.  We exhibit an O(\sqrt{\log n}) pseudo-approximation for finding balanced vertex separators in general graphs, improving over the previous best bound of O(\log n). Likewise, we get improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k \sqrt{\log k}). For graphs excluding a fixed graph as a minor (which includes, e.g. bounded genus graphs) we give a constant-factor approximation for the treewidth, which can be used in order to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs.
             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.
In this paper, we obtain  constant factor approximation for treewidth of a generalization of planar graphs. Previously, constant-factor approximations where possible only for AT-free graphs and on planar graphs. More precisely, we demonstrate structural properties of larger classes of graphs and show how to exploit the properties to obtain algorithms.  The classes considered are those formed by excluding as a minor a graph that can be embedded in the plane with at most one crossing.  We show that graphs in these classes can be decomposed into planar graphs and graphs of small treewidth; we use the decomposition to show that all such graphs have linear local treewidth (all subgraphs of a certain form are graphs of bounded treewidth).  Finally, we make use of the structural properties to derive polynomial-time algorithms for approximating treewidth within a factor of 1.5 and branchwidth within a factor of 2.25 as well as polynomial-time approximation schemes for both minimization and maximization problems and fixed-parameter algorithms for problems such as vertex cover, edge-dominating set, feedback vertex set, and others. 
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.

The main results of this paper regarding approximating treewidth have been improved and generalized in the previous paper. 

An O(sqrt{n})-Approximation Algorithm For Directed Sparsest Cut, Submitted.

We give an O(\sqrt{n})-approximation algorithm for the Sparsest Cut Problem on directed graphs, an open problem posed by Leighton and Rao.A naive reduction from Sparsest Cut to Minimum Multicut would only give an approximation ratio of O(\sqrt{n}\,\log D), where D is the sum of the demands. We obtain the improvement using a novel LP-rounding method for fractional Sparsest Cut, the dual of Maximum Concurrent Flow. We use this result in ``oblivous routing'' scheme.

             On the max-flow min-cut ratio for directed multicommodity flows,
             Submitted to Theoretical Computer science, 2003. See Tech. Report MIT-LCS-TR-910.
We give a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the approximation factor of Greedy algorithm for maximum edge disjoint path problem. More precisely, our upper bound improves the approximation factor for this problem to O(n^{3/4}). Finally, we demonstrate how even for very simple graphs the aforementioned ratio might be very large.

C. Fault-Tolerant Wireless Network Design (See Subsection 2.1 of my Research Statement)

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

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 Siam Journal on Computing.

 Ad hoc wireless networks are networks in which all the nodes communicate with each other through wireless channels. These networks are common in situations like disaster relief where rescuers try to coordinate efforts by talking on advanced walkie-talkies. A major problem in these networks is that the nodes have limitted battery power and it is typically difficult to recharge them. Nonetheless, it is important that the network maintain certain characteristics like connectivity. This work studies power assignments of wireless devices that minimize power while maintaining k-connectivity. The problem is known to be NP-hard, so we develop approximate solutions. One approach, based on the same problem in standard networks, gives an O(k) approximation for general graphs. We then present a more practical distributed poly(k) approximation algorithm for geometric graphs.

This paper and the paper below with Bahramgir and Mirrokni which pioneered the concept of power optimization in fault-tolerant topology control algorithms for wireless multi-hop sensor networks got  references from a dozen of papers just in the past two years.
Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks,
ACM/Kluwer Wireless Networks. To appear.

We can control the topology of a multi-hop wireless network by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. In this paper, we present a distributed fault-tolerant topology control algorithm for minimum energy consumption in these networks. More precisely, we present an algorithm which preserves the connectivity of the network upon failing of at most k nodes (k is constant) and simultaneously minimizes the transmission power at each node. We also demonstrate some optimizations  to further minimize the power at each node. Finally, we show how our algorithms can be extended to 3-dimensions.

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, To appear.

We consider the problem of deploying or repairing a sensor network to provide simultaneously fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first constant factor approximation algorithm that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any fixed k.

D. Routing Scheme (See Subsection 2.2 of my Research Statement)

               Oblivious routing in directed graphs with random demands,
              In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Baltimore, MD, May 21-24, 2005, To appear.
           
We show that interestingly if we consider probabilistic oblivious routing, in which demands between all commodity pairs in the network are drawn i.i.d. from some distributions agreed in advance between the adversary and the algorithm, a polylogarithmic competitive ratio with high probability for oblivious routing in directed graphs is possible (note that as mentioned above, the competitive ratio  is in Omega(\sqrt{n}) without this assumption). We show that the lower bound on competitive ratio is still polynomial if distributions are unknown to the algorithm or even when distributions are known to the algorithms but they are not independent.

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, To appear.
Journal version submitted to Siam Journal on Computing.
Invitation to Journal of Scheduling special issue for selected papers from SODA 2005 regretfully declined.

Roughly speaking, we consider oblivious routing in directed graphs and node-weighted graphs when our cost-measure is throuput. More precisely, we consider distributed online algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph.  Unlike most prior work on online load balancing, we do not assume centralized control and seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors.  Our problem can be seen as analogous to the recent work on oblivious routing by Raecke, but with the objective of maximizing throughput rather than minimizing congestion.  In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm.  This is accompanied by simple algorithms achieving upper bounds which are tight in terms of OPT, the maximum throughput achievable by an omniscient algorithm. Finally, we examine a restricted model in which clients, upon becoming active, must remain so for at least log(n) time steps.  In contrast to the primarily negative results in the oblivious case, here we present an algorithm which is constant-competitive.  Our lower bounds justify the intuition, implicit in earlier work on the subject, that some such restriction (i.e. requiring some stability in the demand pattern over time) is necessary in order to achieve a constant --- or even polylogarithmic ---competitive ratio.

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, To appear.
Journal version  submitted to ACM Transactions on Algorithms.
Invitation to Journal of Scheduling special issue for selected papers from SODA 2005 regretfully declined.

Oblivious routing algorithms for general undirected networks were introduced by Raecke, and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities.  We present the first non-trivial upper bounds for both of these cases, supplying algorithms for k-commodity oblivious routing problems whose competitive ratio is O(\sqrt{k} \log(n)) for undirected node-capacitated graphs and O(\sqrt{k} n^{1/4}log(n)) for directed graphs with either edge or node capacities, where k is the number of commodities  that potentially may be routed.  In the special case that all commodities have a common source or sink, our upper bound becomes O(\sqrt{n} log(n)) in both cases, matching the lower bound up to a factor of log(n). The lower bound  is supplied by a graph containing very high-degree vertices; we show that this requirement is essential for undirected node-capacitated graphs, by providing an O(Delta polylog(n))-competitive oblivious routing scheme for such graphs of maximum degree Delta. However we show that for directed graphs of degree at most three, the lower bound  Omega(\sqrt{n}) on the competitive ratio does still hold.  Finally, we settle an open question about single-sink (or single-source) oblivious routing problems in undirected edge-capacitated graphs, by proving a lower bound of Omega(\log n) for such problems.

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

Interval routing scheme (IRS) is a well-known space-efficient routing strategy for routing messages in distributed networks. In IRS, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link e at a node v indicates the set of destination addresses of the messages which should be forwarded through e at v. In a joint work with Ganjali, we consider a generalization of IRS, called Multi-dimensional IRS(MIRS), in which each node (each link) is assigned a multi-dimensional label. Then we characterize the class of networks supporting ``linear'' MIRS for a given number of dimensions.
Path-matching in graphs with length constraints,
Networks, Vol 39, No. 4, pp. 210-215, 2002.

We consider the problem of path-matching in graphs in which we want to match  a set of nodes in the network via length restricted edge-disjoint paths (it is the matching problem  if the paths should have length one).  We present several NP-hardness and  polynomial-time algorithms (depending on the length restriction) for this problem which has several applications in broadcasting and multicasting in computer networks.

E. Random SAT and Random Graphs (See Subsection 3.1 of my Research Statement)
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.

With random inputs, certain decision problems undergo a ``phase transition''. In this pioneering long paper, we prove similar behavior in an optimization context. More precisely, given a conjunctive normal form (CNF) formula F on n variables and with m k-variable clauses, denote by max F the maximum number of clauses satisfiable by a single assignment of the variables. (Thus the decision problem k-SAT is to determine if max F is equal to m.) With the formula F chosen at random, the expectation of max F is trivially bounded by 3/4 m <= E \max F <= m. We prove that for random formulas with m=cn clauses (c is called the density): for constants c<1, E max F is cn-Theta(1/n); for large c, it approaches (3/4 c + Theta(\sqrt{c}))n; and in the ``window'' c=1+Theta(n^{-1/3}), it is cn-Theta(1). Our full results are more detailed, but this already shows that the optimization problem MAX SAT for random inputs undergoes a phase transition just as the 2-SAT decision problem does, and at the same critical value c=1. Most of our results are established without reference to the analogous propositions for decision 2-SAT, and can be used to reproduce them. We also consider ``online'' versions of MAX SAT, and show that for one version the obvious greedy algorithm is optimal.  We also prove analogous results for random MAX CUT.

It is worth mentioning only during the last year there were at least a half-dozen papers extending and/or improving the results of this work.

Tight Bounds For Random MAX 2-SAT,
To be submitted to Random  Structures and Algorithms.

Using the new Poisson cloning model introduced by Kim, we further sharpen and simplify some results of the above paper with Coppersmith et al. by obtaining tight upper/lower bounds when the density c is small, i.e., when c=1+epsilon, or when density c is large enough.
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.

We prove that the random 3-SAT instance with clause to variable density less than 3.52 is satisfiable with high probabbility. Currently 3.52 is the best lower bound known for the satisfiability threshold of random 3-SAT.

F.  Auction Design and Game Theory (see Subsection 2.3 of my Research Statement)

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

Motivated by auctions of digital goods, say in eBay or Amazon.com,  we consider the limited-supply online auction problem, in which an  auctioneer has k goods to sell and bidders arrive and depart dynamically.  We suppose that agent valuations are drawn independently from some unknown distribution and construct an adaptive auction that is nevertheless value- and time-strategyproof.  We show how interestingly Mathematical Economics, Scheduling theory, and Probability theory have a nice intersection in this area.  More formally, . For the k=1 problem we have a strategyproof variant on the classic secretary problem. We present a 4-competitive (e-competitive) strategyproof online algorithm with respect to offline Vickrey for revenue (efficiency).  We also show (in a model that slightly generalizes the assumption of independent valuations) that no mechanism can be better than 3/2-competitive (2-competitive) for revenue (efficiency). Our general approach considers a  learning phase followed by an accepting phase, and is careful to handle incentive issues for agents that span the two phases. We extend to the k>1 case, by deriving strategyproof mechanisms which are constant-competitive  for revenue and efficiency. Finally, we present some strategyproof competitive algorithms for the case in which adversary uses a distribution known to the mechanism.  Also in this paper, we show that how the assumption that agents' valuations are sampled i.i.d from some unknown stationary distributions can help desing of algorithms.

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

We consider the online aution in which we have re-usable goods. Each agent is assumed to require the resource for one unit of time, but they differ in their arrival and departure times, and their value for being allocated a time slot.  This problem  arise in several practical applications of mechanism design in wireless  network such as pricing access to a WiFi port at Starbucks.  Here we present the  relation of this auction problem to finding a maximum weight matching in bipartite graphs or more generally scheduling theory.  More precisely, we seek mechanisms which are  truthful in the sense that truthful revelation of value, arrival, and departure information is a dominant strategy for each agent, and which are  online in the sense that they make allocation decisions without foreknowledge of the future.   In this paper we formulate a general criterion for such mechanisms to be truthful, we present an online mechanism such that the total value of the allocation is 2-competitive with the maximum value, and we prove that no truthful online mechanism can achieve a competitive ratio better than 2.  We also prove that there is no truthful online mechanism whose revenue is constant-competitive with that of the Vickrey-Clarke-Groves (VCG) mechanism.

          Efficient Power Assignment in Wireless LAN,
             To be submitted to MOBICOM 2005.
We consider the problem of power assignment inwireless sensor networks and its relation to game theory and auction design, in which we want to assign powers to access points such that if each client chooses its ``preferred'' access point to which it connects, no access point excesses its capacity. We show that there is a very close relation between this problem and the notion of ``envy-free'' assignment in auction design and we can use the ideas from Mathematical Economics to obtain power assignment for our practical scenario in Microsoft Research.

G.  Approximate Graph Embeddings (see Subsection 1.3 of my Research Statement)

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, To appear.Journal version submitted to Siam Journal on Computing.

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the  standard notion of minimum-distortion (metric) embedding.  In an ordinal embedding, it is the relative order between pairs of distances,  and not the distances themselves, that must be preserved as much as possible.  The (multiplicative) relaxation of an ordinal embedding is the maximum ratio  between two distances whose relative order is inverted by the embedding.  We develop several worst-case bounds and approximation algorithms  on ordinal embedding.  In particular, we establish that ordinal embedding  has many qualitative differences from metric embedding, and capture the ordinal behavior of ultrametrics and  shortest-path metrics of unweighted trees.
Low Dimensional Embedding with Extra Information,
To appear in the 20th ACM Symposium on Computational Geometry (SoCG), June 9 - 11,  2004, New York.
Journal version invited to Discrete & Computational Geometry for a  special issue of selected papers from SoCG 2004.

We consider the problem of approximating the minimum distortion of the shortest-path metric of a graph into low dimensional spaces, e.g., into L_1 or L_2 with one or two dimensions. Note that here instead of considering the worst case distortion, we consider the distortion of the shortest-path metric of a particular graph. This problem is a
frequently arising problem in computational geometry, computer graphics, ad-hoc wireless sensor network (e.g., in SLAM project in M.I.T) and obtaining a protein backbone in computational Biology.  We give several approximation algorithms and contrasting hardness results for this problem.

This paper is the first paper which approximates distortion of embeddings into two-dimensional  Euclidean space.

H. Cost-effective Network Design (see Subsection 2.4 of my Research Statement)

The Prize-Collecting Generalized Steiner Tree Problem via a new approach of Primal-Dual Schema,
Submitted to IPCO 2005.

We consider the prize-collecting generalized Steiner tree problem, in which given a set of pairs of nodes in the network, we want to buy a set of edges and rent another set of edges such that for any given pair if they are not connected via a path of bought edges, they should be connected directly via a rented edge. We introduce a general combinatorial approach toward solving this problem through a novel primal-dual schema.

The Generalized Deadlock Resolution Problem,
To be submitted to ICALP 2005.

We initiate the study of the AND-OR directed feedback vertex set problem motivated by a practical deadlock resolution problem appears in the development of distributed databases. This problem is a natural generalization of the directed feedback vertex set problem. We show that interestingly this problem is Omega(log^2 n) hard to approximate (so far directed feedback vertex set is known only to be Omega(log n) hard to approximate). Using the region growing technique of Leighton and Rao we present approximation algorithms when there is a small number of AND nodes or when there is a small number of OR nodes in the graph.
The facility location problem with general cost functions,
Networks, Vol. 42, No. 1, pp.  42-47, 2003.

In this paper we introduce a generalization of the facility location problem (a.k.a. universal facility location) in which the cost of each facility is an arbitrary function of the number of clients served by it (this problem is called universal facility location in a later paper), and analyze a natural greedy algorithm for the case of concave cost functions. We give polynomial-time algorithm for the case of convex cost functions.

Bandwidth Sharing VPN Network Design for Multi-class Traffic with Application to VoIP,
To be submitted to SPAA 2005.

We consider the problem of bandwidth sharing  for multi-class traffic, in which our goal is to minimize the cost of bandwidth reservation for confluent flow while satisfying the peak demand for real time VoIP traffic and the average demand of both real time and best effort data traffic. We present constant factor approximation algorithms
for minimizing the cost of bandwidth reservation for this problem.

I. Miscellaneous Theory Papers

          Balanced vertex-orderings of graphs, 
             Discrete Applied Mathematics. To appear.

This paper considers the problem of determining a balanced ordering of vertices of a graph; that is the neighbours of each vertex v are as evenly distributed to the left and right of v as possible. We present several NP-hardness and constant factor approximation algorithms in this paper.
          On the simultaneous edge-coloring conjecture,
Discrete Mathematics 216 (2000), no. 1-3, 267--272. 

In this paper, we connect two seamingly unrelated conjectures: A conjecture of Keedwell (restated by Cameron) on critical sets in Latin squares, and the well-known cycle double cover conjecture. We prove that the former conjecture is implied by the latter, and use this theorem to settle Keedwell's conjecture in almost the general case.

             The Minimum k-Colored Subgraph Problem in Haplotyping and DNA Primer Selection,
             To be submitted to ICALP 2005.

In this paper we consider the minimum k-colored subgraph problem (MkCSP),which is motivated by maximum parsimony based population haplotyping and minimum primer set selection for DNA amplification by multiplex Polymerase Chain Reaction, two important problems in computational biology. We use several new techniques to obtain improved approximation algorithms for both the general MkCSP and some important special cases. We also establish a novel relation between MkCSP and the densest k-subgraph problem, whose approximability is notoriously hard. This relation gives evidence that some of the approximation factors in this paper might be almost tight. Furthermore, this relation could shed light into a potential proof of polynomial inapproximability for the densest k-subgraph problem (using an inapproximability result that we present for a generalized version of the densest k-subgraph problem).
Palindrome Recognition Using a Multidimensioinal Tape,
Theoretical Computer science, Vol. 302, No. 1-3, pp. 475-480, 2003.

The problem of palindrom recognition using a Turing machine with one multidimensional tape is proved to require Theta(n^2 log n) time.
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.

In this paper, we introduce a new property for graphs along with an associated graph class (a generalization on bounded degree graphs) and extend the known classes of inputs for which polynomial-time subgraph isomorphism algorithms are attainable.  In particular, if the removal of any set of at most k vertices from an n-vertex graph results in connected components, we say that the graph is a O(k log n) log-bounded fragmentation graph.  We present a polynomial-time algorithm for finding a subgraph of H isomorphic to a graph G when G is a log-bounded fragmentation graph and H has bounded treewidth; these results are extended to handle graphs of locally bounded treewidth (a generalization of treewidth) when G is a log-bounded fragmentation graph and has constant diameter.

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.

We introduce a new property for graphs called bounded fragmentation, by which we mean after removing any set of at most k vertices the number of connected components is bounded only by a function of  k. We demonstrate how bounded fragmentation can be used to measure the reliability of a network and introduce several classes of bounded fragmentation graphs.
 A Note on the Consecutive Ones Submatrix Problem,
Information Processing Letters, Vol 83, No. 3, pp. 163-166, 2002.

K. Image Processing and RoboCup

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

 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.
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.
A Goal Keeper for Middle  Size RoboCup,
RoboCup 2000, Lecture Notes in Computer Science 2019, 2001: 583-586. 
 
Thesis

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

 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.

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