Search

We study the problem of computing the p q norm of a matrix A ∈ Rm×n, defined as ∣∣j4∣∣p-g = maxx∈Rn{0}'.||Ax|q/||x|p This problem generalizes the spectral norm of a matrix (p = q = 2) and the Grothendieck problem (p = ∞, q = 1) and has been widely studied in various regimes. When p ≥ q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 ∈ [g,p], and the problem is hard to approximate within almost polynomial factors when 2 [g,p]. The regime when p < q, known as Hypercontractive norms, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by Barak et al. [Proceedings of the 4Ath Annual ACM Symposium on Theory of Computing, 2012, pp. 307--326], who gave subexponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the exponential time hypothesis. However, no NP-hardness of approximation is known for these problems for any p < q. We prove the first NP-hardness result (under randomized reductions) for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 [p, g], ∣∣√4∣∣p--q is hard to approximate within 2°(log n)1-x) assuming NP g BPTIME(21log n A-). En rθute to the above result, we also prove almost tight results for the case when p > q with 2 ∈ [q, p]. [ABSTRACT FROM AUTHOR]

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an (1 - g(ε))-fraction of constraints on any (1 - ε )- satisfiable instance, where the loss function g is such that g(ε ) \rightarrow 0 as ε \rightarrow 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterized by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(ε ) = O((log log(1/ε ))/ log(1/ε)). It is natural to ask when a better loss can be achieved, in particular polynomial loss g(ε ) = O(ε 1/k) for some constant k. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP [ABSTRACT FROM AUTHOR]

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, includes planar graphs, and in particular is a subset of the family of graphs that have polynomial expansion. We present efficient (1+ε)-approximation algorithms for polynomial expansion graphs for unweighted Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTASs for these problems are known for subclasses of this graph family. These results have immediate applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth. [ABSTRACT FROM AUTHOR]

We present a numerical method for polynomial approximation of multivariate functions. The method utilizes Gauss quadrature in tensor product form, which is known to be inefficient in high dimensions. Here we demonstrate that by using a new randomized algorithm and taking advantage of the tensor structure of the grids, a highly efficient algorithm can be constructed. The new method does not require prior knowledge/storage of the entire data set at all the tensor grid points, whose total number of points is excessively large in high dimensions. Instead the method utilizes one data point at a time and iteratively conducts the approximation. This feature allows the use of the method irrespective of the size of the data set. We establish the rate of convergence of this iterative algorithm and show that its operational counts can be lower than the standard methods, when applicable, such as least squares. Numerical examples in up to hundreds of dimensions are presented to verify the theoretical analysis and demonstrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) algorithms are known for this problem. We develop a polylogarithmic time randomized algorithm that for any constant δ>0, estimates the length of the LIS of an array to within an additive error of n. More precisely, the running time of the algorithm is(log n)c(1/δ)O(1/δ), where the exponent c is independent of δ. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2 approximation. With a suitable choice of parameters, our algorithm also gives, for any fixed т> 0, a multiplicative (1+т)-approximation to the distance to monotonicity εf (the fraction of entries not in the LIS), whose running time is polynomial in log(n) and 1/εf . The best previously known algorithm could only guarantee an approximation within a factor (arbitrarily close to) 2. [ABSTRACT FROM AUTHOR]

For bin packing, the input consists of n items with sizes s1, . . . , sn ∊ [0, 1] which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from 1982 produces a solution with at most OPT +O(log2 OPT) bins. We provide the first improvement in over three decades and show that one can find a solution of cost OPT +O(logOPT · log logOPT) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation using the partial coloring method from discrepancy theory. The result is constructive via the algorithms of Bansal and Lovett-Meka. [ABSTRACT FROM AUTHOR]

In this paper we consider linear fractional systems of commensurate orders and with commensurate delays, whose characteristic equation is a polynomial in the two variables sα (0 < α < 1) and e-ST (T > 0). These systems may have single or multiple chains of poles asymptotic to the imaginary axis. Location of poles of large modulus belonging to these chains are determined by approximation and simple necessary and suffcient H∞-stability conditions are derived. [ABSTRACT FROM AUTHOR]

We study a general class of problems called F-DELETION problems. In an F-DELETION problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and an approximation algorithm achieving an approximation ratio of O(log3/2 OPT), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph θc as a minor for a fixed integer c. The graph θc consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as VERTEX COVER, FEEDBACK VERTEX SET, and DIAMOND HITTING SET. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]

Weighted geometric set-cover problems arise naturally in several geometric and nongeometric settings (e.g., the breakthrough of Bansal and Pruhs [Proceedings of FOCS, 2010, pp. 407-414] reduces a wide class of machine scheduling problems to weighted geometric set cover). More than two decades of research has succeeded in settling the (1 + ∈)-approximability status for most geometric set-cover problems, except for some basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan [Proceedings of STOC'10, 2010, pp. 641-648] presented a clever quasi-sampling technique, which together with improvements by Chan et al. [Proceedings of SODA, 2012, pp. 1576-1585], yielded an O(1)-approximation algorithm. Even for the unweighted case, a polynomial time approximation scheme (PTAS) for a fundamental class of objects called pseudodisks (which includes halfspaces, disks, unit-height rectangles, translates of convex sets, etc.) is currently unknown. Another fundamental case is weighted halfspaces in R³, for which a PTAS is currently lacking. In this paper, we present a quasi PTAS (QPTAS) for all these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese [Proceedings of FOCS, 2013, pp. 400-409; Proceedings of SODA, 2014, pp. 645-656], who recently obtained a QPTAS for a weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming NP ... DTIME(2polylog(n)). Together with the recent work of Chan and Grant [Comput. Geom., 47 (2014), pp. 112-124], this settles the APX-hardness status for all natural geometric set-cover problems. [ABSTRACT FROM AUTHOR]

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class C, that is, the maximum VCdimension over the hypergraphs formed by the closed neighborhoods of elements of C. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class C) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on C4-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of c log(|V |) for some c > 0. [ABSTRACT FROM AUTHOR]

We propose a computationally efficient fully polynomial-time approximation scheme (FPTAS) to compute an approximation with arbitrary precision of the value function of convex stochastic dynamic programs, using the technique of $K$-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674--685]. This paper deals with the convex case only, and it has the following contributions. First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set. [ABSTRACT FROM AUTHOR]

Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We initiate the study of approximability of the size of the sparsest k-TC-spanner of a given directed graph. We completely resolve the approximability of 2-TC-spanners, showing that it is Θ(log n) unless P = NP. For k > 2, we present a polynomial time algorithm that finds a k-TC-spanner with size within O((n log n)1-1/k) of the optimum. Our techniques also yield algorithms with the first nontrivial approximation ratio for well-studied problems on directed spanners when k > 3: DIRECTED k-SPANNER, CLIENT/SERVER DIRECTED k-SPANNER, and k-DIAMETER SPANNING SUBGRAPH. For constant k ≥ 3, we show that the size of the sparsest k-TC-spanner is hard to approximate within a factor of 2log1-∈ n for any ε ∈ (0, 1) unless NP ⊆ DTIME(npolylog n). Finally, we study the size of the sparsest k-TC-spanners for H-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with O(log² n/ε) queries for any poset whose transitive reduction, when viewed as an undirected graph, is free of a fixed minor. Previously, the best upper bound on the query complexity for such graphs was O(√n/ε). [ABSTRACT FROM AUTHOR]

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages and hence are called multistage stochastic programming problems. Multi stage stochastic programming and, in particular, multi stage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation method, is quite simple and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems. [ABSTRACT FROM AUTHOR]

We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-make span scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees that most of our algorithms achieve are of the order of √n/ln n. We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem f approximating a monotone submodular function everywhere. In addition, we present an algorithm for approximating submodular functions with a special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. [ABSTRACT FROM AUTHOR]

Only recently Goyal, Olver, and Shepherd [PToc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists all optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms. 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPn, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry. [ABSTRACT FROM AUTHOR]

The Nemhauser-Trotter theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely, the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser-Trotter theorem can be applied using our extension to Generalized Vertex Cover. These applications include a (2-2/d)-approximation algorithm for graphs of bounded degree d, a polynomial-time approximation scheme (PTAS) for planar graphs, a (2 - lg lg n/2 lg n)-approximation algorithm for general graphs, and a 2k kernel for the parameterized Generalized Vertex Cover problem. [ABSTRACT FROM AUTHOR]

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity requirements with degree bounds: given a directed graph G = (V,E) with nonnegative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds {av, bv}vϵV on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm for this problem using the natural LP relaxation and show that our guarantee is the best possible relative to this LP relaxation. We also obtain similar results for the (more general) class of crossing supermodular requirements. In the absence of edge-costs, our result gives the first additive O(1)-approximation guarantee for degree-bounded intersecting/crossing supermodular connectivity problems. We also consider the minimum crossing spanning tree problem: Given an undirected edge-weighted graph G, edge-subsets {Ei}k i=1, and nonnegative integers {bi}k i=1, find a minimum-cost spanning tree (if it exists) in G that contains at most bi edges from each set Ei. We obtain a +(r - 1) additive approximation for this problem, when each edge lies in at most r sets. A special case of this problem is the degree-bounded minimum spanning tree, and our techniques give a substantially shorter proof of the recent +1 approximation of Singh and Lau [in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2007, pp. 661-670]. [ABSTRACT FROM AUTHOR]

Let A be a 0/1 matrix of size m × n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ϵ · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175-220] to sparse matrices. As an application, we obtain efficient 1-· approximation algorithms for "bounded" instances of MAX CSP problems. [ABSTRACT FROM AUTHOR]

We present new approximation algorithms for the k-median and k-means clustering problems. To this end, we obtain small coresets for k-median and k-means clustering in general metric spaces and in Euclidean spaces. In ℝd, these coresets are of size with polynomial dependency on the dimension d. This leads to (1 + ϵ)-approximation algorithms to the optimal k-median and k-means clustering in Rd, with running time O(ndk+2(k/ϵ)O(1) d2 logk+2 n), where n is the number of points. This improves over previous results. We use those coresets to maintain a (1+ϵ)-approximate k-median and k-means clustering of a stream of points in ℝd, using O(d2k2ϵ-2 log8 n) space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension. [ABSTRACT FROM AUTHOR]

We study graph properties that are testable for bounded-degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is well known that in the bounded-degree graph model (where two graphs are considered "far" if they differ in ϵn edges for a positive constant ϵ), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded-degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree graph model. [ABSTRACT FROM AUTHOR]

We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of O(log ∣R∣), where R is the set of sources. We also present a better constant approximation to the related Access Network Design problem. Our algorithms are randomized and combinatorial. As a subroutine in our algorithm, we use an interesting variant of facility location with lower bounds on the amount of demand an open facility needs to serve. We call this variant load balanced facility location and present a constant factor approximation for it, while relaxing the lower bounds by a constant factor. [ABSTRACT FROM AUTHOR]

One of the main goals in the analysis of microarray data is to identify groups of genes and groups of experimental conditions (including environments, individuals, and tissues) that exhibit similar expression patterns. This is the so-called biclustering problem. In this paper, we consider two variations of the biclustering problem: the consensus submatrix problem and the bottleneck submatrix problem. The input of the problems contains an m×n matrix A and integers l and k. The consensus submatrix problem is to find an l × k submatrix with l

We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point r ∊ P, and a length constraint B, one needs to find a path starting from r that visits as many points of P as possible and of length not exceeding B. We present a (1 - ϵ)-approximation algorithm for this problem that runs in nO(1/ϵ) time; the computed path visits at least (1 - ϵ)kopt points of P, where kopt is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions. [ABSTRACT FROM AUTHOR]

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than (log N)γ, for some constant γ > 0, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of o(log N) remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is Ω(log N) larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-d circuits are denoted by ACd0. We show that it is hard to approximate the size of ACd0 circuits (for large enough d) under cryptographic assumptions. [ABSTRACT FROM AUTHOR]

Assuming that NP ⊈ ∩ϵ>0 BPTIME(2nϵ), we show that graph min-bisection, dense k-subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values. [ABSTRACT FROM AUTHOR]

We study resource constrained scheduling problems where the objective is to compute feasible preemptive schedules minimizing the makespan and using no more resources than what are available. We present approximation schemes along with some inapproximability results showing how the approximability of the problem changes in terms of the number of resources. The results are based on linear programming formulations (though with exponentially many variables) and some interesting connections between resource constrained scheduling and (multidimensional, multiplechoice, and cardinality constrained) variants of the classical knapsack problem. In order to prove the results we generalize a method by Grigoriadis et al. for the max-min resource sharing problem to the case with weak approximate block solvers (i.e., with only constant, logarithmic, or even worse approximation ratios). Finally, we present applications of the above results in fractional graph coloring and multiprocessor task scheduling. [ABSTRACT FROM AUTHOR]

We adapt a method proposed by Nesterov [Math. Program. Ser. A, 103 (2005), pp. 127–152] to design an algorithm that computes ∊-optimal solutions to fractional packing problems by solving O(∊-1√Knln(m)) separable convex quadratic programs, where n is the number of variables, m is the number of constraints, and K is the maximum number of nonzero elements in any constraint. We show that the quadratic program can be approximated to any degree of accuracy by an appropriately defined piecewise-linear program. For the special case of the maximum concurrent flow problem on a graph G = (V,E) with rational capacities and demands, we obtain an algorithm that computes an ∊-optimal flow by solving shortest path problems, i.e., problems in which the number of shortest paths computed grows as O(∊-1 log(∊-1)) in ∊ and polynomially in the size of the problem. In contrast, previous algorithms required ω(∊-2) iterations. We also describe extensions to the maximum multicommodity flow problem, the pure covering problem, and mixed packing-covering problem. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling n independent tasks on a set of m parallel processors, where the execution time of a task is a function of the subset of processors assigned to the task. For any fixed m, we propose a fully polynomial approximation scheme that for any fixed ε > 0 finds a preemptive schedule of length at most (1 + ε) times the optimum in O(n) time. We also discuss the nonpreemptive variant of the problem, and present for any fixed m a polynomial approximation scheme that computes an approximate solution of any fixed accuracy in linear time. In terms of the running time, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound. [ABSTRACT FROM AUTHOR]

We study directed network design problems with orientation constraints. An orientation constraint on a pair of nodes u and v states that a feasible solution may include at most one of the arcs (u, v) and (v, u). Such constraints arise naturally in many network design problems, since link or edge resources such as fiber can be used to support traffic in one of two possible directions only. Our first result is that the directed network design problem with orientation constraints can be solved in polynomial time in the case where the requirement function $f$ is positively intersecting supermodular. (The case where there are no orientation constraints follows from the work of Frank [Acta Sci. Math. (Szeged), 41 (1979), pp. 63--76].) The second main result of the paper is a 4-approximation algorithm for the minimum cost strongly edge-connected subgraph problem with orientation constraints. Our algorithm shows that the problem of enforcing orientation constraints can be reduced to the minimum cost $2$-edge-connected subgraph problem on undirected graphs. Finally, we study the problem for general crossing supermodular functions and show the following bicriteria approximation result. Let k denote the maximum requirement of any set under the given requirement function f. We give a 2k-approximation algorithm to construct a solution that satisfies a slightly weaker requirement function, namely, f'(S)=max{f (S)-1,0}. [ABSTRACT FROM AUTHOR]

The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic that achieves a best-known approximation ratio of $1 + \frac{\ln 3}{2} \approx 1.55$ for general graphs and best-known approximation ratios of $\approx 1.28$ for both quasi-bipartite graphs (i.e., where no two nonterminals are adjacent) and complete graphs with edge weights 1 and 2. Our method is considerably simpler and easier to implement than previous approaches. We also prove the first known nontrivial performance bound ($1.5 \cdot$ OPT) for the iterated 1-Steiner heuristic of Kahng and Robins in quasi-bipartite graphs. [ABSTRACT FROM AUTHOR]

Extending results of Christie and Irving, we examine the action of reversals and transpositions on finite strings over an alphabet of size k. We show that determining reversal, transposition, or signed reversal distance between two strings over a finite alphabet is NP-hard, while for "dense" instances we give a polynomial-time approximation scheme. We also give a number of extremal results, as well as investigating the distance between random strings and the problem of sorting a string over a finite alphabet. [ABSTRACT FROM AUTHOR]

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs (which could also be easily extended to other geometrically defined graphs). [ABSTRACT FROM AUTHOR]

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of ε-local optimality and show that, for every ε > 0, an ε-local optimum can be identified in time polynomial in the problem size and 1/ε whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a ε-local optimum, a variation of our main algorithm produces a (δ+ ε)-local optimum in time polynomial in the problem size and 1/ε. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

Dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT ≥ LOAD; previous work showed that OPT < 3 LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT = L + O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any &epsiv; > 0, there exists a c > 0 such that for all sufficiently large integers hmax, there is a dynamic storage allocation instance with maximum job height hmax, maximum load at most L, and OPT ≥ L + c(hmax/L)1/2+&epsiv;L, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + &epsiv;)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]

The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights. We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166-177]. [ABSTRACT FROM AUTHOR]

Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers db and dg (db ≤ dg). A frequently occurring problem in computational biology (and other fields) is to find a (distinguishing) substring s of length L that distinguishes the bad strings from good strings, i.e., such that for each string si Ε B there exists a length-L substring ti of si with d(s, ti) ≤ db (close to bad strings), and for every substring ui of length L of every string gi Ε G, d(s, ui) ≥ dg (far from good strings). We present a polynomial time approximation scheme to settle the problem; i.e., for any constant ε > 0, the algorithm finds a string s of length L such that for every si Ε B there is a length-L substring ti of si with d(ti, s) ≤ ( 1 + ε)db, and for every substring ui of length L of every gi ε G, d(ui, s) ≥ (1 − ε)dg if a solution to the original pair (db ≤ dg) exists. Since there is a polynomial number of such pairs (db, dg), we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems. [ABSTRACT FROM AUTHOR]