Search

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p -Edge-Connected and p -Vertex-Connected VC problem (where p ≥ 2 is a fixed integer). We obtain an 2 O (p k) n O (1) -time algorithm for p -Edge-Connected VC and an 2 O (k 2) n O (1) -time algorithm for p -Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP ⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2 (p + 1) -approximation algorithm for the p -Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p -vertex/edge-connected subgraphs of a p -vertex/edge-connected graph by Nishizeki and Poljak (1994) [30] and Nagamochi and Ibaraki (1992) [27]. [ABSTRACT FROM AUTHOR]

We study two generalizations of classic clustering problems called dynamic ordered k-median and dynamic k-supplier , where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k -median under mild assumptions on the input. We give a 3-approximation for dynamic k -supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results. [ABSTRACT FROM AUTHOR]

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. [ABSTRACT FROM AUTHOR]

We show that a constant factor approximation of the shortest and closest lattice vector problem in any ℓ p -norm can be computed in time 2 (0.802 + ε) n. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem in the ℓ 2 norm. To obtain our result, we combine the latter algorithm for ℓ 2 with geometric insights related to coverings. [ABSTRACT FROM AUTHOR]

Given a set of n integer-valued coin types and a target value t , the well-known change-making problem asks for the minimum number of coins that sum to t , assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j , for every j = 0 , ... , t. We obtain a number of new results on these problems, including (i) an algorithm for the all-targets problem with running time O ˜ (t 4 / 3) (improving a previous O ˜ (t 3 / 2) -time algorithm), (ii) a very simple O ˜ (u 2 + t) -time algorithm for the all-targets problem, where u denotes the maximum coin value, and (iii) an algorithm for the original (single-target) problem with running time O ˜ (u) (improving a previous O ˜ (t) -time algorithm by Chan and He (SOSA'20)). We also describe applications to the (single-capacity) unbounded knapsack problem and the minimum word break problem. [ABSTRACT FROM AUTHOR]

A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph G and weight function w : V (G) → Q ≥ 0 , the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices X such that G − X is a split graph. It is easy to show that a graph is a split graph if and only if it does not contain a 4-cycle, 5-cycle, or a two edge matching as an induced subgraph. Therefore, SVD admits an easy 5-approximation algorithm. On the other hand, for every δ > 0 , SVD does not admit a (2 − δ) -approximation algorithm, unless P=NP or the Unique Games Conjecture fails. For every ϵ > 0 , Lokshtanov, Misra, Panolan, Philip, and Saurabh (Lokshtanov et al., 2020) recently gave a randomized (2 + ϵ) -approximation algorithm for SVD. In this work we give an extremely simple deterministic (2 + ϵ) -approximation algorithm for SVD. [ABSTRACT FROM AUTHOR]

Given a digraph G = (V , E) , the k -path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k , to cover all the vertices. The problem has various applications. Its special case on undirected graphs is NP-hard when k ≥ 3 , and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k / 2 -approximation algorithm, based on a novel concept of enlarging walk to minimize the number of singletons. Secondly, for k = 3 , we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k ≥ 7 , we present an improved (k + 2) / 3 -approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process. [ABSTRACT FROM AUTHOR]

This work firstly studies the Steiner tree problem with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of d ln ⁡ 4 d + ln ⁡ 4 − 1 + ϵ for general graphs and approximation ratio of 73 ⋅ d 60 ⋅ d + 13 + ϵ for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + ϵ for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G , the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. [ABSTRACT FROM AUTHOR]

Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes. • We consider the resource provision problem for users with cost minimization and model the identified problem by considering two types of cost: replication cost and transmission cost. We first discuss a simple case, and one optimal solution is proposed. We then consider a more complicated case in which each user can upload multiple replications on fog nodes in the provisioning process. Two models are discussed: the 0–1 transmission cost model and the different transmission cost model. • We propose an optimal solution for the 0–1 transmission cost model. Then we prove that the problem under the different transmission cost model is NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. • Various simulations were conducted to compare our joint optimization methods with several state-of-the-art ones based on two real datasets: the Mobike dataset and the Microsoft GPS trajectory dataset. The results are shown from different perspectives to provide conclusions. [ABSTRACT FROM AUTHOR]

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

Abstract It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a (non-negatively) weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. In particular, this allows for an effective treatment of polynomials with rational coefficients. In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum of squares decomposition for univariate polynomials with rational coefficients. The first algorithm, due to the third author, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition, but its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition, and was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. Finally, we report on our implementations of both algorithms and compare them in practice on several application benchmarks. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energy-consumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the AVerage Rate (AVR) online algorithm in the heterogeneous setting. [ABSTRACT FROM AUTHOR]

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]

• A cost function vector of the simultaneous perturbation stochastic approximation algorithm is proposed. • The proposed method reaches a good convergence performance. • The vibration of the inlet pipeline is eliminated by using the proposed method. Active vibration control of stable rotating machinery with a time-variant structure is a research priority in the field. Simultaneous perturbation stochastic approximation (SPSA), a model-free active control strategy, has attracted a lot of attention from researchers. This paper studies the cost function of the SPSA algorithm to improve its performance in controlling periodic vibration. After the weight vector being perturbed by a perturbation vector, the existing cost functions of the SPSA algorithm can reveal the overall energy variation but hardly detail the variation of each harmonic wave. Therefore, the adaptive notch filter with the SPSA algorithm using these cost functions shows a low convergence speed and a bad control effect in active periodic disturbance controlling. In order to detail the energy variation of each harmonic, this paper proposes a cost function using the weighted cross correlation function. When the algorithm calculates the energy of each harmonic wave, the disturbances from other harmonics and background noise are reduced. The interference noises in the estimated gradient of the cost function are reduced indirectly. The algorithm convergence performance improves. To illustrate that, the simulations of controlling harmonic waves and the experiments of eliminating the vibration of the pump inlet pipeline are conducted. The results indicate that the adaptive notch filter with the proposed cost function has reached the fastest convergence speed and the best control effect so far among the use of other cost functions mentioned in this paper. [ABSTRACT FROM AUTHOR]

Given a collection of multisets { X 1 , X 2 , ... , X k } (k ≥ 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset X i , 1 ≤ i ≤ k. The minimum common integer partition (k -MCIP) problem is defined as to find a CIP for { X 1 , X 2 , ... , X k } with the minimum cardinality. We present a 6 5 -approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio 5 4 designed by Chen et al. in 2006. We then extend it to obtain an absolute 0.6 k -approximation algorithm for k -MCIP when k is even (when k is odd, the approximation ratio is 0.6 k + 0.4). [ABSTRACT FROM AUTHOR]

Abstract: In this paper modified variants of the sparse Fourier transform algorithms from Iwen (2010) [32] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, , in time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented. [Copyright &y& Elsevier]

Abstract: Node-Weighted Steiner Forest is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider the restriction to planar graphs where the problem remains NP-complete. Demaine et al. showed that the generic primal-dual algorithm of Goemans and Williamson is a 6-approximation on planar graphs. We present (1) two different analyses to prove an approximation factor of 3, (2) show that our analysis is best possible for the chosen proof strategy, and (3) generalize this result to feedback problems on planar graphs. We give a simple proof for the first result using contraction techniques and following a standard proof strategy for the generic primal-dual algorithm. Given this proof strategy our analysis is best possible which implies that proving a better upper bound for this algorithm, if possible, would require different proof methods. Then, we give a reduction on planar graphs of Feedback Vertex Set to Node-Weighted Steiner Tree, and Subset Feedback Vertex Set to Node-Weighted Steiner Forest. This generalizes our result to the feedback problems studied by Goemans and Williamson. For the opposite direction, we show how our constructions can be combined with the proof idea for the feedback problems to yield an alternative proof of the same approximation guarantee for Node-Weighted Steiner Forest. [Copyright &y& Elsevier]

Abstract: This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires time and space, where is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires time and space, and the presented approximation scheme requires time and space, where ϵ is the given approximation parameter and M is the length of the longest path in an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: Let be a compact, smooth, connected, Riemannian manifold without boundary, be a kernel. Analogous to a radial basis function network, an eignet is an expression of the form , where , , . We describe a deterministic, universal algorithm for constructing an eignet for approximating functions in for a general class of measures μ and kernels G. Our algorithm yields linear operators. Using the minimal separation among the centers as the cost of approximation, we give modulus of smoothness estimates for the degree of approximation by our eignets, and show by means of a converse theorem that these are the best possible for every individual function. We also give estimates on the coefficients in terms of the norm of the eignet. Finally, we demonstrate that if any sequence of eignets satisfies the optimal estimates for the degree of approximation of a smooth function, measured in terms of the minimal separation, then the derivatives of the eignets also approximate the corresponding derivatives of the target function in an optimal manner. [Copyright &y& Elsevier]

Abstract: When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness). We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O''Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios. [Copyright &y& Elsevier]

Abstract: Fischer proposes in [T. Fischer, Optimizing the degree of minimum weight spanning trees, Technical Report 93–1338, Department of Computer Science, Cornell University, Ithaca, NY, USA, 1993] a sequential algorithm to compute a minimum weight spanning tree of maximum degree at most in time for any constant , where is the maximum degree value of an optimal solution and n is the number of nodes in the network. In the present paper, we propose a distributed version of Fischer''s sequential algorithm with time complexity , requiring messages and space per node, where is the maximum degree of an initial minimum weight spanning tree. [Copyright &y& Elsevier]

Abstract: A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring of trees arises in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. Research on perfect phylogeny is usually focused on finding a tree so that few predetermined partial colorings of its vertices are convex. When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one. In [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218–232; J. Comput. System Sci., submitted for publication], a natural measure for this distance, called the recoloring distance was defined: the minimal number of color changes at the vertices needed to make the coloring convex. This can be viewed as minimizing the number of “exceptional vertices” w.r.t. a closest convex coloring. The problem was proved to be NP-hard even for colored strings. In this paper we continue the work of [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218–232; J. Comput. System Sci., submitted for publication], and present a 2-approximation algorithm of convex recoloring of strings whose running time , where c is the number of colors and n is the size of the input, and an 3-approximation algorithm for convex recoloring of trees. [Copyright &y& Elsevier]

Abstract: We consider the problem of optimizing the total flow time of a stream of jobs that are released over time in a multiprocessor setting. This problem is NP-hard even when there are only two machines and preemption is allowed. Although the total (or average) flow time is widely accepted as a good measurement of the overall quality of service, no approximation algorithms were known for this basic scheduling problem. This paper contains two main results. We first prove that when preemption is allowed, Shortest Remaining Processing Time (SRPT) is an approximation algorithm for the total flow time, where n is the number of jobs, m is the number of machines, and P is the ratio between the maximum and the minimum processing time of a job. We also provide an lower bound on the (worst case) competitive ratio of any randomized algorithm for the on-line problem in which jobs are known at their release times. Thus, we show that up to a constant factor SRPT is an optimal on-line algorithm. Our second main result addresses the non-preemptive case. We present a general technique that allows to transform any preemptive solution into a non-preemptive solution at the expense of an factor in the approximation ratio of the total flow time. Combining this technique with our previous result yields an approximation algorithm for this case. We also show an lower bound on the approximability of this problem (assuming ). [Copyright &y& Elsevier]

Abstract: We study the problem of scheduling unit size jobs on n processors connected by a ring. We show a distributed algorithm for this problem with an approximation ratio of . [Copyright &y& Elsevier]

Abstract: The effectiveness of a distributed system hinges on the manner in which tasks and data are assigned to the underlying system resources. Moreover, today''s large-scale distributed systems must accommodate heterogeneity in both the offered load and in the makeup of the available storage and compute capacity. The ideal resource assignment must balance the utilization of the underlying system against the loss of locality incurred when individual tasks or data objects are fragmented among several servers. In this paper we describe this locality-maximizing placement problem and show that an optimal solution is NP-hard. We then describe a polynomial-time algorithm that generates a placement within an additive constant of two from optimal. [Copyright &y& Elsevier]

Abstract: We consider a directed network in which every edge possesses a latency function that specifies the time needed to traverse the edge given its congestion. Selfish, noncooperative agents constitute the network traffic and wish to travel from a source vertex s to a destination t as quickly as possible. Since the route chosen by one network user affects the congestion experienced by others, we model the problem as a noncooperative game. Assuming that each agent controls only a negligible portion of the overall traffic, Nash equilibria in this noncooperative game correspond to s–t flows in which all flow paths have equal latency. A natural measure for the performance of a network used by selfish agents is the common latency experienced by users in a Nash equilibrium. Braess''s Paradox is the counterintuitive but well-known fact that removing edges from a network can improve its performance. Braess''s Paradox motivates the following network design problem: given a network, which edges should be removed to obtain the best flow at Nash equilibrium? Equivalently, given a network of edges that can be built, which subnetwork will exhibit the best performance when used selfishly? We give optimal inapproximability results and approximation algorithms for this network design problem. For example, we prove that there is no approximation algorithm for this problem with approximation ratio less than , where n is the number of network vertices, unless . We further show that this hardness result is the best possible, by exhibiting an -approximation algorithm. We also prove tight inapproximability results when additional structure, such as linearity, is imposed on the network latency functions. Moreover, we prove that an optimal approximation algorithm for these problems is the trivial algorithm: given a network of candidate edges, build the entire network. As a consequence, we show that Braess''s Paradox—even in its worst-possible manifestations—is impossible to detect efficiently. En route to these results, we give a fundamental generalization of Braess''s Paradox: the improvement in performance that can be effected by removing edges can be arbitrarily large in large networks. Even though Braess''s Paradox has enjoyed 35 years as a textbook example, our result is the first to extend its severity beyond that in Braess''s original four-node network. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the Internet are confluent since Internet routing is destination based. We consider the single-commodity confluent flow problem, in which we are given an -node directed network , a sink and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge (and node) congestion , where C is the node congestion of a splittable flow with minimum node congestion; here the node congestion of a flow is the maximum, over all nodes other than , of the congestion at a node. This implies an approximation algorithm for the problem with uniform supplies. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest. For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of . We also establish a lower bound on the gap between confluent and splittable flows, and consider multi-commodity and fractional versions of confluent flow problems. [Copyright &y& Elsevier]

Abstract: In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the problem of scheduling n jobs on a single machine with controllable processing times. Each job has a release date when it becomes available for processing, and, after completing its processing, requires an additional delivery time. Feasible schedules are further restricted by job precedence constraints. We develop a polynomial time approximation scheme whose running time depends only linearly on the input size. This improves and generalizes the previous -approximation algorithm by Zdrzalka. Moreover, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound obtained by Hall and Shmoys for the special case without controllable processing times. [Copyright &y& Elsevier]

Abstract: The main result of this paper is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach (see [M. Lanthier, A. Maheshwari, J.-R. Sack, Approximating weighted shortest paths on polyhedral surfaces, in: Proceedings of the 13th Annual ACM Symposium on Coputational Geometry, 1997, pp. 274–283; L. Aleksandrov, M. Lanthier, A. Maheshwari, J.-R. Sack, An ɛ-approximation algorithm for weighted shortest paths on polyhedral surfaces, in: Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, in: Lecture Notes in Comput. Sci., vol. 1432, 1998, pp. 11–22; L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295]) that converts the original continuous geometric search space into a discrete graph by placing representative points on boundary edges. However, by exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently as it accesses only a sparse subgraph of . Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295], BUSHWHACK can compute an ɛ-approximation in time. By reducing complexity dependency on ɛ, this result improves on all previous results with the same discretization approach. We also provide an improvement over the discretization scheme of [L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295] so that the size of is no longer dependent on unit weight ratio, the ratio between the maximum and minimum unit weights. This leads to the first ɛ-approximation algorithm whose time complexity does not depend on unit weight ratio. [Copyright &y& Elsevier]

Abstract: Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given , finds a solution of cost times optimal, meeting the covering constraints () and multiplicity constraints (), and satisfying , where is the vector of row sums . Here m denotes the number of rows of . This gives an -approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints . The previous best approximation ratio has been since 1982. CIP contains the set cover problem as a special case, so -approximation is the best possible unless . [Copyright &y& Elsevier]

Abstract: In TSP with neighborhoods (TSPN) we are given a collection of regions in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN is APX-hard and cannot be approximated within a factor of in polynomial time, unless . [Copyright &y& Elsevier]

Abstract: Given a simple connected graph and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph remains simple and has at least two internally disjoint paths between u and v for each pair . The problem is known to be NP-hard, and a -approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an time -approximation algorithm to the problem. [Copyright &y& Elsevier]

Abstract: We consider the data migration problem, which is the problem of finding an efficient schedule to migrate data in a network. The data layout of a large storage server needs to be computed based on the expected data access pattern for load balancing. As the data access pattern changes over time, we need to recompute a new layout and then migrate the data from its current layout to the new layout. Our objective is to minimize the total completion time over all storage devices. We develop a 3-approximation algorithm when each migration job needs the same amount of time and a 9-approximation when the times required for different migration jobs are different. Another interesting objective is to minimize the total completion time over all data migration jobs. We present a 10-approximation algorithm when each migration job has a different processing time. We extend our results to the resource constrained scheduling problem where each job requires at most m resources. We obtain -approximations for both resource and job completion times. [Copyright &y& Elsevier]

Abstract: We study integrated prefetching and caching in single and parallel disk systems. In the first part of the paper we investigate approximation algorithms for the single disk problem. There exist two very popular approximation algorithms called Aggressive and Conservative for minimizing the total elapsed time. We give a refined analysis of the Aggressive algorithm, improving the original analysis by Cao et al. We prove that our new bound is tight. Additionally we present a new family of prefetching and caching strategies and give algorithms that perform better than Aggressive and Conservative. In the second part of the paper we investigate the problem of minimizing stall time in parallel disk systems. We present a polynomial time algorithm for computing a prefetching/caching schedule whose stall time is bounded by that of an optimal solution. The schedule uses at most extra memory locations in cache. This is the first polynomial time algorithm that, using a small amount of extra resources, computes schedules whose stall times are bounded by that of optimal schedules not using extra resources. Our algorithm is based on the linear programming approach of [Journal of the ACM, 47 (2000) 969]. However, in order to achieve minimum stall times, we introduce the new concept of synchronized schedules in which fetches on the disks are performed completely in parallel. [Copyright &y& Elsevier]

We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks. [Copyright &y& Elsevier]

Motivated by a scheduling problem in multicast environments, we consider the problem of arranging a weighted graph around a circle so as to minimize the total weighted arc length. We describe the first polynomial-time approximation algorithms for this problem, and specifically an O(logn)-approximation algorithm for undirected circular arrangements and an O(√ of n)-approximation algorithm for directed circular arrangements. We will also conduct an experimental evaluation of our algorithms and show that a simple heuristic has the best performance in simulations based on busy Web server logs. [Copyright &y& Elsevier]

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115–1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu−xv≡c (mod 3) and inequations xu−xv≢c (mod 3), where xu∈{0,1,2} for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee of 7/12+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3 arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+10−8 for the general problem (by Andersson et al. (J. Algorithms 39 (2001) 162–204)). It matches the guarantee of 0.836008 for Max-3-Cut found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the ϑ-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of Max-3-Cut, and that our algorithm is the same as that of Andersson et al. in the more general case. [Copyright &y& Elsevier]

Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P of size n is not worse than at least a fraction q of the feasible solutions of I. We describe a deterministic, polynomial-time algorithm with domination ratio 1−o(1) for the partition problem, and a deterministic, polynomial-time algorithm with domination ratio Ω(1) for the MaxCut problem and for some far-reaching extensions of it, including Max-r-Sat, for each fixed r. The techniques combine combinatorial and probabilistic methods with tools from harmonic analysis. [Copyright &y& Elsevier]

We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source–sink pairs (si,ti), 1⩽i⩽k, and the goal is to find a largest subset of source–sink pairs that can be simultaneously connected in an edge-disjoint manner. We show that in directed networks, for any ϵ>0, EDP is NP-hard to approximate within m1/2−ϵ. We also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of EDP. Another related class of routing problems that we study concerns EDP with the additional constraint that the routing paths be of bounded length. We show that, for any ϵ>0, bounded length EDP is hard to approximate within m1/2−ϵ even in undirected networks, and give an O(√ of m)-approximation algorithm for it. For directed networks, we show that even the single source–sink pair case (i.e. find the maximum number of paths of bounded length between a given source–sink pair) is hard to approximate within m1/2−ϵ, for any ϵ>0. [Copyright &y& Elsevier]

We obtain the following new coloring results:

Let G be an undirected graph with nonnegative edge lengths. Given two vertices as sources and all vertices as destinations, we investigated the problem how to construct a spanning tree of G such that the sum of distances from sources to destinations is minimum. In the paper, we show the NP-hardness of the problem and present a polynomial time approximation scheme. For any ϵ>0, the approximation scheme finds a (1+ϵ)-approximation solution in O(n⌈1/ϵ+1⌉) time. We also generalize the approximation algorithm to the weighted case for distances that form a metric space. [Copyright &y& Elsevier]

Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. Assume that we are given n DNA sequences s1, …, sn. The Consensus Patterns problem, which has been widely studied in bioinformatics research, in its simplest form, asks for a region of length L in each si, and a median string s of length L so that the total Hamming distance from s to these regions is minimized. We show that the problem is NP-hard and give a polynomial time approximation scheme (PTAS) for it. We then present an efficient approximation algorithm for the consensus pattern problem under the original relative entropy measure. As an interesting application of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important consensus alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence. [Copyright &y& Elsevier]

Kernel based methods provide a way to reconstruct potentially high-dimensional functions from meshfree samples, i.e., sampling points and corresponding target values. A crucial ingredient for this to be successful is the distribution of the sampling points. Since the computation of an optimal selection of sampling points may be an infeasible task, one promising option is to use greedy methods. Although these methods may be very effective, depending on the specific greedy criterion the chosen points might quickly lead to instabilities in the computation. To circumvent this problem, we introduce and investigate a new class of stabilized greedy kernel algorithms, which can be used to create a scale of new selection strategies. We analyze these algorithms, and in particular we prove convergence results and quantify in a precise way the distribution of the selected points. These results allow to prove, in the case of certain Sobolev kernels, that the algorithms have optimal stability and optimal convergence rates, including for functions outside the native space of the kernel. The results also apply to the case of the usual P -greedy algorithm, significantly improving state-of-the-art results available in the literature. Illustrative experiments are presented that support the theoretical findings and show improvements of the stabilized algorithms in terms of accuracy due to improved stability. [ABSTRACT FROM AUTHOR]

Results on two different settings of asymptotic behavior of approximation characteristics of individual functions are presented. First, we discuss the following classical question for sparse approximation. Is it true that for any individual function from a given function class its sequence of errors of best sparse approximations with respect to a given dictionary decays faster than the corresponding supremum over the function class? Second, we discuss sparse approximation by greedy type algorithms. We show that for any individual function from a given class we can improve the upper bound on the rate of convergence of the error of approximation by a greedy algorithm if we use some information from the previous iterations of the algorithm. Bounds of this type fall in the category of a posteriori bounds. [ABSTRACT FROM AUTHOR]