Approximation Algorithms for Capacitated k-Travelling Repairmen Problem,

In Proceedings of ISAAC 2016.

Local Search Yields a PTAS for k-Means in Doubling Metrics,

In Proceedings of FOCS 2016. Journal version invited to special issue of SICOMP.

- Approximating
Connected Facility Location with Lower and Upper Bounds
via LP Rounding

In Proceedings of SWAT 2016.

In this paper, we present LP-based approximation algorithms for connected facility location problem where each facility may have capacities with upper and lower bounds. In particular, we present the first constant factor bicriteria approximation for facility location problem with non-uniform lower bounds and uniform upper bounds.

- Approximation
Algorithms
for
Min-Sum k-Clustering and Balanced k-Median

In Proceedings of ICALP 2015.

In this paper, we present improved approximation algorithms for min-sum k-clustering and Balanced k-Median. The main results of the paper are: a PTAS for balanced K-Median on HST's which implies an O(log n)-approximation for general graphs (improving the previous result by Bartal et al. from STOC'01). Also we present a QPTAS for when the metric has constant doubling dimension.

- LP-based Approximation Algorithms for
Facility Location in Buy-at-Bulk Network Design

In Proceedings of WADS 2015.

In this paper, we present LP-based approximation algorithms for different versions of facility location buy-at-bulk problems.

- S. Ahmadian, B. Behsaz, Z. Friggstad,
A. Jorati, M.R. Salavatipour, and C. Swamy

Approximation Algorithms for Minimum-Load k-Facility Location

In Proceedings of APPROX 2014.

In this paper, we consider the minimum-load k-facility location problem: have a set F of facilities, a set of C clients and in a metric space and a parameter k. The goal is to open k facilities and assign each client to an open facility such that the maximum cost of each facility (where the cost of each facility is the total distances of the clients served by it to itself) is minimized. This generalizes the min-max k-star cover problem. Among others we present a PTAS for the case when the metric is a line. This is the first true approximation for this problem even for this simple metric. We also present a QPTAS for tree metrics.

- B. Behsaz, Z. Svitkina, and M.R.
Salavatipour

__New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem__

Algorithmica, earlier version in Proceedings of SWAT 2012.

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present some new approximation algorithms for it. We present a framework for designing bicriteria approximation algorithms and show two new approximation algorithms with factors (10.173,3/2) and (30.432,4/3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithms is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any (O(1),1+\eps)-approximation for the restricted version implies an (O(1),1+\eps)-approximation for the UCFLP for any constant \eps>0. In addition, we present a quasi-polynomial time (1+\epsilon,1+\epsilon)-approximation for the (uniform) UCFLP in Euclidean metrics, for any constant \eps>0.

- B. Behsaz and M.R. Salavatipour

__On Minimum Sum of Radii and Diameters Clustering__

Algorithmica 73(1): 143-165 (2015). Earlier version in Proceedings of SWAT 2012.

Given a metric (V,d) and an integer k, we consider the problem of covering the points of V with at most k clusters so as to minimize the sum of radii or the sum of diameters of these clusters. The former problem is called the Minimum Sum Radii (MSR) problem and the latter is the Minimum Sum Diameters (MSD) problem. The current best polynomial time algorithms for these problems have approximation ratios 3.504 and 7.008, respectively. For the MSR problem, we give an exact algorithm when the metric is the shortest-path metric of an unweighted graph and there cannot be any singleton clusters. For the MSD problem on the plane with Euclidean distances, we present a polynomial time approximation scheme.

- S. Har-Peled, A. Nayyeri, M.R.
Salavatipour, and A. Sidiropoulos

__How to Walk Your Dog in the Mountains with No Magic Leash__

Discrete and Computational Geometry 55(1): 39-73 (2016). Earlier version in Proceedings of SoCG 2012.

In this paper we describe a O(log n)-approximation algorithm for computing the homotopic Frechet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms where known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a O(log n)-approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Frechet distance, or the minimum height of a homotopy, is in NP.

- M.R. Khani and M.R. Salavatipour,

__Improved Approximations for Buy-at-Bulk and Shallow-light k-Steiner trees and (k,2)-subgraph__

J. Comb. Optim. 31(2): 669-685 (2016). Earlier version in Proc. Of ISAAC 2011. -
M.R. Khani and M.R. Salavatipour,

__Improved Approximation algorithms for Min-max Tree Cover and Bounded Tree Cover Problems__

Algorithmica 69(2): 443-460 (2014). Earlier version in Proc. Of APPROX 2011, LNCS 6845 pp 302-314. -
I. Pirwani and M.R. Salavatipour,

*A PTAS for Minimum Clique Partition in Unit Disk Graphs,*

Algorithmica 62(3-4): 1050-1072 (2012). Earlier version in proceedings of SWAT 2010. -
Z. Friggstad, M.R. Salavatipour, and Z. Svitkina,

*Asymmetric Traveling Salesman Path and Directed Latency Problems,*

SIAM J. Comput. 42(4): 1596-1619 (2013). Earlier version in Proc. of SODA 2010. Complete version is here -
N. Bansal, Z. Friggstad, R. Khandekar, and M.R. Salavatipour,

*A Logarithmic Approximation for Unsplittable Flow on Line Graphs,*

To appear in ACM. Trans. on Algorithms. Earlier version in Proc. of SODA 2009. -
Z. Friggstad and M.R. Salavatipour,

Minimizing movement in mobile facility location problems.

ACM Transactions on Algorithms 7(3): 28 (2011). Earlier version in Proceedings of FOCS 2008. -
R. Khandekar, G. Kortsarz, V. Mirrokni, and M.R. Salavatipour,

*Two Stage Robust Network Design with Exponential Scenarios,*

To appear in Algorithmica. Earlier version in Proc. of ESA 2008. -
M.A. Safari and M.R. Salavatipour,

*A constant factor approximation for minimum λ-edge-connected κ-subgraph with metric costs,*

SIAM J. Discrete Math. 25 (3): 1089-1102 (2011). Earlier version in Proceedings of APPROX 2008. -
Z. Friggstad and M.R. Salavatipour,

*Approximability of Packing Disjoint Cycles,*

Algorithmica 60(2): 395-400 (2011). Earlier version appeared in Proceedings of ISAAC 2007. -
L. Lau, S. Naor, M.R. Salavatipour, and M. Singh,

*Survivable Network Design with Degree or Order Constraints ,*

Invited to SIAM J. on Computing (special issue for selected papers of STOC'07) Vol.39, No.3 pp 1062-1087, 2009.

Earlier version appeared in Proceedings of ACM STOC 2007. -
O. Madani, W. Greiner, D. Kempe, and M.R. Salavatipour,

*Recall Systems: Efficient Learning and Use of Category Indices,*

In Proceedings of AISTATS 2007. -
C. Chekuri, M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour,

*Approximation Algorithms for Node-Weighted Buy-at-Bulk Network Design Problems,*

In Proceedings of SODA 2007.

The Journal version which combines the results of this paper with our FOCS 2006 paper titled

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design

In SIAM J. on Computing (5): 1772-1798 (2010) -
Z. Cai, R. Goebel, M.R. Salavatipour, and G. Lin,

*Selecting dissimilar genes for multi-class classification, an application in cancer subtyping,*

*BMC Bioinformatics*2007,**8:**206.

Z. Cai, R. Goebel, M.R. Salavatipour, Y. Shi, L. Xu, and G. Lin,

*Selecting Genes with Dissimilar Discrimination Strength for Sample Class Prediction,*

In Proceedings of the Fifth Asia-Pacific Bioinformatics Conference (APBC 2007).

Z. Cai, L. Xu, Y. Shi, M. Salavatipour, R. Goebel, and G. Lin,

*Using Gene Clustering to Identify Discriminatory Genes with Higher Classification Accuracy.*

In Proceedings of IEEE 6th Symposium on Bioinformatics and Bioengineering (BIBE 2006). -
C. Chekuri, M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour,

*Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design problems,*

In Proceedings of FOCS 2006. -
M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour,

*Approximating Buy-at-Bulk and Shallow-light k-Steiner trees,*

Algorithmica 53(1): 89-103 (2009). Earlier version in Proceedings of APPROX 2006. -
E. Demaine, U. Feige, M.T. Hajiaghayi, and M. R. Salavatipour,

*Combination Can Be Hard: Approximability of the Unique Coverage Problem,*

SIAM J. on Computing, Volume 38, Issue 4, pp. 1464-1483. Prelimnary version in Proceedings of SODA 2006. -
J. Cheriyan and M.R. Salavatipour,

*Packing Element-Disjoint Steiner Trees*

ACM Trans. on Algorithms. Volume 3, Issue 4, Article No. 47. Preliminary version in proceedings of APPROX 2005. -
M. Krivelevich, Z. Nutov, M.R. Salavatipour, J. Verstraete, and R. Yuster

*Approximation Algorithms and Hardness Results for Cycle Packing Problems*,

ACM Transactions on Algorithms, Volume 3 , Issue 4,Article No. 48.

Part of these results appeared in the following conference paper:

M.R. Salavatipour and J. Verstraete,

*Disjoint Cycles: Integrality Gap, Hardness, and Approximation*,

In Proceedings of IPCO 2005, LNCS volume 3509, pp 51-65. -
J. Cheriyan and M.R. Salavatipour,

*Hardness and Approximation Results for Packing Steiner Trees*,

Algorithmica 45(1):21-43, 2006. The special issue for selected papers of ESA 2004. -
M.R. Salavatipour

*Large Induced Forests in Triangle-free Planar Graphs*,

Graphs and Combinatorics 22(1):113-126, 2006. -
M. Molloy and M.R. Salavatipour,

*The Resolution Complexity of Random Constraint Satisfaction Problems*,

SIAM J. on Computing 37(3): 895-922, 2007.

A preliminary version appeared in Proceedings of FOCS 2003. -
O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour.

*Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable*,

J. of Combinatorial Theory (Series B), 93:303-311, 2005. -
K. Jain, M. Mahdian, and M.R. Salavatipour,

*Packing Steiner Trees*,

In Proceedings of SODA 2003. -
M.R. Salavatipour,

*A Polynomial Time Algorithm for Strong Edge Coloring of Partial k-Trees*,

Discrete Applied Mathematics 143:(1-3) 2004, pp 285-291. -
M.R. Salavatipour,

*A (1+ε)-Approximation Algorithm for Partitioning Hypergraphs Using A New Algorithmic Version of the Lovasz Local Lemma*,

Random Structures and Algorithms 25(1) 2004, pp 68-90.

Earlier version appeared in Proceedings of SODA 2003. -
M. Molloy and M.R. Salavatipour,

*A Bound on the Chromatic Number of the Square of a Planar Graph*,

J. of Combinatorial Theory (Series B), Volume 94(2), pp 189-213, 2005.

Conference version was:*Frequency Channel Assignment on Planar Networks*, In Proceedings of ESA 2002, LNCS 2461, pp. 736-747. -
M.R. Salavatipour,

*The Three Color Problem For Planar Graphs*,

Technical Report CSRG-458, Department of Computer Science, University of Toronto, July 2002. Also available here .

Here are the supplementary material for this paper. -
M.R. Salavatipour,

*On Sum Coloring of Graphs*,

Discrete Applied Math. 127(3), 477-488, 2003. -
M. Mahdian, E.S. Mahmoodian, A. Saberi, M.R. Salavatipour, and R. Touserkani,

*On a Conjecture of Keedwell and the Cycle Double Cover Conjecture*,

Disc. Math. 216: (1-3), pp 287-292, 2000. -
M.R. Salavatipour,

__Graph Colouring via the Discharging Method__

Ph.D. thesis, Department of Computer Science, University of Toronto, 2003. -
M.R. Salavatipour,

__On sum coloring of graphs__

M.Sc. thesis, Department of Computer Science, University of Toronto, 2000. -
M.R. Salavatipour,

*Parallel Delauney Triangulation*,

B.Sc thesis, Department of Computer Eng. , Sharif University of Tech. (in persian).

Publications and Manuscripts

**Copyright note:** For the papers that have been published,
the copyright has been transferred to the respective publisher.
Therefore, the paper cannot be copied or used for commercial
purposes.

(updated Dec, 2016).

We study variants of the capacitated vehicle routing
problem. In the multiple depot capacitated k-travelling
repairmen problem, we have a collection of clients to be
served by one vehicle in a fleet of k identical vehicles
based at given depots. Each client has a given demand that
must be satisfied, and each vehicle can carry a total of
at most Q demand before it must resupply at its original
depot. We wish to route the vehicles in a way that obeys
the constraints while minimizing the average time
(latency) required to serve a client. This generalizes the
Multi-depot k-Travelling Repairman Problem to the
capacitated vehicle setting.
We give constant factor approximation to this general
problem, and refine this constant to 25.49 when clients
have unit demands. We achieve these results by developing
a framework allowing us to solve a wider range of latency
problems, and crafting various orienteering-style oracles
for use in this framework. dimension.

In this paper we present the first PTAS
for k-means in constant dimension Euclidean metrics. More
specifically, we show that a simple local search operation
which considers a (sufficiently large) constant number of
swaps in each operation is a PTAS for k-means in
d-dimensional Euclidean metrics for any fixed d. The
result extends to the setting where we want to minimize
the sum of q-th power of distances for any fixed q (e.g.
q=1 gives the k-median problem and q=2 is k-means). It
also generalizes to metrics with constant doubling
dimension.

In this paper we give
improved approximation algorithms for some network design
problems. In the Bounded-Diameter or Shallow-Light k-Steiner
tree problem (SLkST), we are given an undirected graph
G=(V,E) with terminals T including a root r, a cost function
c on the edges, a length function \ell on the edges, a bound
L>0, and an integer k>=1.

The goal is to find a minimum c-cost r-rooted Steiner tree
containing at least k terminals whose diameter under \ell
metric is at most L. We present a bicriteria (O(\log^2
n),O(\log n))-approximation for SLkST: the algorithm finds a
k-Steiner tree of diameter at most O(L \log n) whose cost is
at most O(\log^2 n \opt^*) where \opt^* is the cost of an LP
relaxation of the problem. This improves on the algorithm of
Hajiaghayi et al.(APPROX'06/Algorithmica'09) which had ratio
(O(\log^4 n), O(\log^2 n)).

Using this, we obtain an O(\log^3 n)-approximation for
Buy-at-Bulk k-Steiner tree which improves upon the O(\log^4
n)-approximation of the same reference. We also consider the
problem of finding a minimum cost 2-edge-connected subgraph
with at least k vertices, which is introduced as the
(k,2)-subgraph problem by Lau et al. (STOC'07/SICOMP09). We
give an O(\log n)-approximation algorithm for this problem
which improves upon the O(\log^2 n)-approximation of Lau et
al.

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with edge weights w, a set T_1,T_2,...,T_k of subtrees of G is called a tree cover of G if together they contain all the nodes. In the Min-Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented by Arkin et al. (J. of Algorithms 2006) and Even et al. (Opr. Rsch. Ltrs 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of 3/2. In the Bounded Tree Cover problem we are given graph G and a bound \lambda and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most \lambda. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound of Arkin et. al.

We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a weakly robust polynomial time approximation scheme (PTAS) for UDGs expressed with edge-lengths that either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) that it computes a clique partition, we show that it is guaranteed to be within (1+\eps) ratio of the optimum if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG's is NP-hard even if we are given edge lengths, our PTAS is a weakly-robust algorithm. Our algorithm can be transformed into an O(\frac{\log^* n}{\eps^{O(1)}}) time distributed PTAS.

We also consider a weighted version of the clique partition problem on vertex-weighted UDGs that generalizes the problem. We note some key distinctions with the unweighted version, where ideas useful in obtaining a PTAS break down. Yet, surprisingly, it admits a (2+\eps)-approximation algorithm for the weighted case where the graph is expressed, say, as an adjacency matrix. This improves on the best known 8-approximation for the {\em unweighted} case for UDGs expressed in standard form.

We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified nodes s and t, both problems ask to find an s-t path visiting all other nodes. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total cost of this path. In the directed latency problem, the objective is to minimize the sum of distances on this path from s to each node. Both of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio O(\log n) until the very recent result that improves it to O(\log n/\log \log n) by Asadpour et al. (SODA2010). However, only a bound of O(\sqrt{n}) for the integrality gap of its linear programming relaxation has been known. For directed latency, the best previously known approximation algorithm has a guarantee of O(n^{1/2+\epsilon}), for any constant \eps>0 by Nagarajan and Ravi (Approx 2008). We present a new algorithm for the ATSPP problem that has an approximation ratio of O(\log n), but whose analysis also bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed by Chekuri and Pal (TOC 2007). We then pursue a deeper study of this linear program and its variations, which leads to an algorithm for the $k$-person ATSPP (where k s-t paths of minimum total length are sought) and an O(\log n)-approximation for the directed latency problem.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time $s_i$, an end time t_i, a demand d_i>0, and a profit p_i>0. A task, if accepted, requires d_i units of ``bandwidth'' from time s_i to t_i and accrues a profit of p_i. For every time t, we are also specified the available bandwidth c_t, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. We present the first polynomial-time O(\log n)-approximation algorithm for this problem. This significantly advances the state-of-the-art, as no polynomial-time o(n)-approximation was known previously. Previous results for this problem were known only in more restrictive settings, in particular, either the instance satisfies so-called ``no-bottleneck'' assumption: \max_i d_i \leq \min_t c_t, or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an \Omega(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

In the mobile facility location problem, which is a variant of the classical facility location, each facility and client is assigned to a start location in a metric graph and our goal is to find a destination node for each client and facility such that every client is sent to a node which is the destination of some facility. The quality of a solution can be measured either by the total distance clients and facilities travel or by the maximum distance traveled by any client or facility. As we show in this paper (by an approximation preserving reduction), the problem of minimizing the total movement of facilities and clients generalizes the classical k-median problem. The class of movement problems was introduced by Demaine et al. [SODA'07/TALG 2009] where a simple 2-approximation was proposed for the minimum maximum movement mobile facility location problem while an approximation for the minimum total movement variant and hardness results for both were left as open problems. Our main result here is an 8-approximation algorithm for the minimum total movement mobile facility location problem. Our algorithm is obtained by rounding an LP relaxation in five phases. We also show that this problem generalizes the classical $k$-median problem using an approximation preserving reduction. For the minimum maximum movement mobile facility location problem, we show that we cannot have a better than a 2-approximation for the problem, unless $P=NP$; so the simple algorithm proposed by Demaine et al.is essentially best possible.

We study two-stage robust variants of combinatorial optimization problems on undirected graphs, like Steiner tree, Steiner forest, and uncapacitated facility location. Robust optimization problems, previously studied by Dhamdhere et al. (FOCS'05), Golovin et al. (STACS'06), and Feige et al. (IPCO'07), are two-stage planning problems in which the requirements are revealed after some decisions are taken in Stage 1. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust k-Steiner tree problem, for example, one buys some edges in Stage 1. Then k terminals are revealed in Stage 2 and one has to buy more edges, at a higher cost, to complete the Stage 1 solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario. In this paper, we focus on the case of exponentially many scenarios given implicitly. A scenario consists of any subset of k terminals (for k-Steiner tree), or any subset of k terminal-pairs (for k-Steiner forest), or any subset of k clients (for facility location). Feige et al. give an LP-based general framework for approximation algorithms for a class of two stage robust problems. Their framework cannot be used for network design problems like k-Steiner tree. Their framework can be used for the robust facility location problem, but gives only a logarithmic approximation. We present the first constant-factor approximation algorithms for the robust k-Steiner tree (with exponential number of scenarios) and robust uncapacitated facility location problems. Our algorithms are combinatorial and are based on guessing the optimum cost and clustering to aggregate nearby vertices. For the robust k-Steiner forest problem on trees and with uniform multiplicative increase factor for Stage 2 (also known as inflation), we present a constant approximation. We show APX-hardness of the robust min-cut problem (even with singleton-set scenarios), resolving an open question of Dhamdhere et al. and Golovin et al.

In the (k,\lambda)-subgraph problem, we are given an undirected graph G=(V,E) with edge costs and two positive integers k and \lambda and the goal is to find a minimum cost simple \lambda-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-Spanning Tree problem or k-MST (which is a (k,1)-subgraph), and minimum cost \lambda-edge-connected spanning subgraph (which is a (|V(G)|,\lambda)-subgraph). The only previously known results on this problem Lau et al. (SICOMP'09) Chekuri and Korula (Algorithmica'10) show that the (k,2)-subgraph problem has an O(\log^2 n)-approximation (even for 2-node-connectivity) and that the (k,\lambda)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e. satisfy triangle inequality), like in the k-MST problem, then there is an O(1)-approximation algorithm for (k,\lambda)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity.

Given a graph G, the edge-disjoint cycle packing problem is to find the largest set of cycles of which no two share an edge. For undirected graphs, the best known approximation algorithm has ratio O(\sqrt{\log n}) Krivelevich et al. (TALG'07). In fact, they proved the same upper bound for the integrality gap of this problem by presenting a simple greedy algorithm. Here we show that this is almost best possible. By modifying integrality gap and hardness results for the edge-disjoint paths problem, we show that the undirected edge-disjoint cycle packing problem has an integrality gap of \Omega(\frac{\sqrt{\log n}}{\log\log n}) and furthermore it is quasi-NP-hard to approximate within ratio of O(\log^{0.5-\epsilon} n) for any constant \eps>0. The same result holds for the problem of packing vertex-disjoint cycles.

In this paper we introduce the idea of iterative relaxation and use that to present algorithmic results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds B_v on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a (2,2B_v+3)-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most 2B_v+3. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly $k$-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic results is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost \lambda-edge-connected subgraph with at least k vertices, which we call the (k,\lambda)-subgraph problem. This generalizes some well-studied classical problems such as the k-MST and the minimum cost \lambda-edge-connected subgraph problems. We give a poly-logarithmic approximation for the (k,2)-subgraph problem. However, by relating it to the Densest k-Subgraph problem, we provide evidence that the (k,\lambda)-subgraph problem might be hard to approximate for arbitrary \lambda.

We introduce the framework of recall systems for efficient learning and retrieval of categories when the number of categories is large. A recall-system is a simple feature-based pre-processing step which reduces the potential categories for an instance to a small manageable set. The correct categories from this set can then be determined using traditional classifiers. We present a formalization of the index learning problem and establish NP-hardness and approximation hardness. We proceed to give an efficient heuristic for learning indices, and evaluate it on several large data sets. In our experiments, the index is learned within minutes, and reduces the number of categories by several orders of magnitude, without affecting the quality of classification overall.

Buy-at-bulk network design problems arise in settings where the costs for purchasing or installing equipment exhibit economies of scale. The objective is to build a network of cheapest cost to support a given multi-commodity flow demand between node pairs. We present approximation algorithms for buy-at-bulk network design problems with costs on both edges and nodes of an undirected graph. Our main result is the first poly-logarithmic approximation ratio for the non-uniform problem that allows different cost functions on each edge and node; the ratio we achieve is O(\log^4 h) where h is the number of demand pairs. In addition we present an O(\log h) approximation for the single sink problem. Poly-logarithmic ratios for some related problems are also obtained. Our algorithm for the multi-commodity problem is obtained via a reduction to the single source problem using the notion of junction trees. We believe that this presents a simple yet useful general technique for network design problems.

We consider approximation algorithms for non-uniform buy-at-bulk network design problems. The first non-trivial approximation algorithm for this problem is due to Charikar and Karagiozova (STOC' 05); for an instance on h pairs their algorithm has an approximation guarantee of \exp(O(\sqrt{\log h \log\log h})) for the uniform-demand case, and \log D\cdot\exp(O(\sqrt{\log h \log\log h})) for the general demand case, where D is the total demand. We improve upon this result, by presenting the first poly-logarithmic approximation for this problem. The ratio we obtain is O(\log^3 h \cdot \min\{\log D, \gamma(h^2)\}) where h is the number of pairs and \gamma(n) is the worst case distortion in embedding the metric induced by a n vertex graph into a distribution over its spanning trees. Using the best known upper bound on \gamma(n) we obtain an O(\min\{\log^3 h\cdot \log D, \log^5 h \log \log h \}) ratio approximation. We also give poly-logarithmic approximations for some variants of the singe-source problem that we need for the multicommodity problem.

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T\subseteq V including a particular vertex s called the root, and an integer k\leq |T|. There are two cost functions on the edges of G, a buy cost b:E\longrightarrow \RR^+ and a distance cost r:E\longrightarrow \RR^+. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost \sum_{e\in H} b(e)+\sum_{t\in T-s} dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(\log^4 n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(\log n),O(\log^3 n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least k/8 terminals. Using this we obtain an (O(\log^2 n),O(\log^4 n))-approximation algorithm for the shallow-light k-Steiner tree and an O(\log^4 n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem Chekuri et al. (FOCS'06).

We prove semi-logarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, assuming that \NP \not\subseteq \BPTIME(2^{n^\eps}) for an arbitrary \eps>0, we prove O(1/\log^{\sigma} n) inapproximability for some constant \sigma=\sigma(\epsilon). We also prove O(1/\log^{1/3-\epsilon} n) inapproximability, for any \eps>0, assuming that refuting random instances of 3SAT is hard on average; and prove O(1/\log n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish an $\Omega(1/\log n)$-approximation algorithm, even for a more general (budgeted) setting, and obtain an \Omega(1/\log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems including max cut, maximum coverage, and radio broadcasting.

Given an undirected graph G(V,E) with terminal set T\subseteq V the problem of packing element-disjoint Steiner trees is to find the maximum number of Steiner trees that are disjoint on the nonterminal nodes and on the edges. The problem is known to be NP-hard to approximate within a factor of \Omega(\log n), where n=|V|. We present a randomized O(\log n)-approximation algorithm for this problem, thus matching the hardness lower bound. Moreover, we show a tight upper bound of O(\log n) on the integrality ratio of a natural linear programming relaxation.

The cycle packing number of a graph G is the maximum number of pairwise edge-disjoint cycles in G. Computing this number is an NP-hard problem. We present approximation algorithms for computing this in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [J. of Algorithms'03] and show that it has approximation ratio \Theta(\sqrt{\log n}). This improves upon the previous O(\log n) upper bound for the approximation ratio of this algorithm. In the directed case we present a $\sqrt{n}$-approximation algorithm. Finally we give an O(n^{2/3})-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset $S$ of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability in directed graphs. Specifically, we prove a lower bound of \Omega(\frac{\log n}{\log\log n}) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate the solution within a factor of O(\log^{1-\epsilon} n) for any constant \eps>0. This improves upon the previously known APX-hardness result for this problem.

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for 4 terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee of O(\sqrt{n}\log n), where n denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of \Omega(m^{1/3-\eps) and give an approximation guarantee of O(m^{1/2+\eps}), where m denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs.

Given a planar graph G, what is the largest subset of vertices of $G$ that induces a forest? Albertson and Berman in 1979 conjectured that every planar graph has an induced subgraph on at least half of the vertices that is a forest. For bipartite planar graphs, Akiyama and Wanatabe conjectured that there is always an induced forest of size at least 5n/8. Here we prove that every triangle-free (and therefore every bipartite) planar graph on n vertices has an induced forest of size at least (17n+24)32.

We consider random instances of constraint satisfaction problems where each variable has domain size d, and each constraint contains t restrictions on k variables. For each (d,k,t) we determine whether the resolution complexity is a.s. constant, polynomial or exponential in the number of variables. For a particular range of (d,k,t), we determine a sharp threshold for resolution complexity where the resolution complexity drops from a.s. exponential to a.s. polynomial when the clause density passes a specific value.

Planar graphs without cycles of length from 4 to 7 are proved to be 3-colorable. Moreover, it is proved that each proper 3-coloring of a face of length from 8 to 11 in a connected plane graph without cycles of length from 4 to 7 can be extended to a proper 3-coloring of the whole graph. This improves on the previous results on a long standing conjecture of Steinberg.

The Steiner packing problem is to find the maximum number of edge-disjoint subgraphs of a given graph G that connect a given set of required points S. This problem is motivated by practical applications in VLSI-layout and broadcasting, as well as theoretical reasons. In this paper, we study this problem and present an algorithm with an asymptotic approximation factor of |S|/4. This gives a sufficient condition for the existence of k edge-disjoint Steiner trees in a graph in terms of the edge-connectivity of the graph. We will show that this condition is the best possible if the number of terminals is 3. At the end, we consider the fractional version of this problem, and observe that it can be reduced to the minimum Steiner tree problem via the ellipsoid algorithm.

A matching M in a graph is called induced if there is no edge in the graph connecting two edges of M. The strong edge coloring problem is to find an edge coloring of a given graph with minimum number of colors such that each color class is an induced matching. This problem is known to be NP-complete, even in very restricted cases. Here, we show that it can be solved in polynomial time on graphs with bounded treewidth, i.e partial $k$-trees. This answers an open question of Mahdian (Disc. Appl. Math 2002).

In his seminal result, Beck gave the first algorithmic version of the Lovasz Local Lemma by giving polynomial time algorithms for 2-coloring and partitioning uniform hypergraphs. His work was later generalized by Alon, and Molloy and Reed. Recently, Czumaj and Scheideler gave an efficient algorithm for 2-coloring non-uniform hypergraphs. But the partitioning algorithm obtained based on their second paper only applies to a more limited range of hypergraphs, so much so that their work doesn't imply the result of Beck for the uniform case. Here we give an algorithmic version of the general form of the Local Lemma which captures (almost) all applications of the results of Beck and Czumaj and Scheideler, with an overall simpler proof. In particular, if H is a non-uniform hypergraph in which every edge e_i intersects at most |e_i|2^{\alpha k} other edges of size at most k, for some small constant \alpha, then we can find a partitioning of H in expected linear time. This result implies the result of Beck for uniform hypergraphs along with a speedup in his running time.

Wegner conjectured that the chromatic number of the square of any planar graph G with maximum degree D>=8 is bounded by \chi(G^2)<=\lfloor\frac{3}{2}D\rfloor+1. We prove the bound \chi(G^2)<=\lceil(5/3)D\rceil +78$. This is asymptotically an improvement on the previously best known bound. For large values of D we give the bound of $\chi(G^2)\leq \lceil(5/3)D\rceil+25$. We generalize this result to L(p,q)-labeling of planar graphs, by showing that $\lambda^p_q(G)\leq q\lceil\frac{5}{3}\D\rceil+18p+77q-18$. For each of the results, the proof provides a quadratic time algorithm.

The sum coloring problem asks to find a vertex coloring of a given graph G, using natural numbers, such that the total sum of the colors is minimized. A coloring which achieves this total sum is called an optimum coloring and the minimum number of colors needed in any optimum coloring of a graph is called the strength of the graph. We prove the NP-hardness of finding the vertex strength for graphs with $\Delta=6$. Polynomial time algorithms are presented for the sum coloring of chain bipartite graphs and $k$-split graphs. The edge sum coloring problem and the edge strength of a graph are defined similarly. We prove that the edge sum coloring and the edge strength problems are both NP-complete for $k$-regular graphs, $k\geq 3$. Also we give a polynomial time algorithm to solve the edge sum coloring problem on trees.

Theses