Search

They give fixed parameter tractable algorithms for the problem parameterized by various structural parameters. The authors give a greedy loop-free algorithm for the exhaustive generation, a successor algorithm that runs in constant amortized time, among other algorithms, as well as results for the fixed spin generalization of this problem. IWOCA (International Workshop on Combinatorial Algorithms) is an annual conference series covering all aspects of combinatorial algorithms. [Extracted from the article]

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to k jobs at the end for some limited number k. For m identical machines, Albers and Hellwig (Algorithmica 79(2):598–623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ≈ 1.4659 . They show that k = O (m) is sufficient to achieve this bound and no k = o (n) can result in a better bound. We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a δ = Θ (1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + δ with k = o (n) . We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ≈ 1.7992 with k = O (m) . We also show that k = Ω (m) is necessary to achieve a competitive ratio below 2. Our algorithm is based on maintaining a specific imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines. [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as k-center, k-median, and k-means. Such algorithms need to be both time and and space efficient. In this paper, we address the problem of correlation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O (n · polylog n) -space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the "quality" of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. Unfortunately, the standard LP and SDP formulations are not obviously solvable in O (n · polylog n) -space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. [ABSTRACT FROM AUTHOR]

In this paper we consider the classical connected dominating set problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem—a centralized greedy approach with an approximation guarantee of H (Δ) + 2 , and a local information greedy approach with an approximation guarantee of 2 (H (Δ) + 1) (where H() is the harmonic function, and Δ is the maximum degree in the graph). A local information greedy algorithm uses significantly less knowledge about the graph, and can be useful in a variety of contexts. However, a fundamental question remained—can we get a local information greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative. [ABSTRACT FROM AUTHOR]

Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands { d io j } i ∈ { 1 , ... , m } , o ∈ { 1 , ... , m } that is said to be complete once all of its requisite flows have been scheduled. We consider the offline coflow scheduling problem with and without release times to minimize the total weighted completion time. Coflow scheduling generalizes the well studied concurrent open shop scheduling problem and is thus NP-hard. Qiu et al. (in: ACM Symposium on parallelism in algorithms and architectures. ACM, New York, pp 294–303, 2015) obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic 67 3 -approximation and a randomized (9 + 16 2 3) ≈ 16.54 -approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm for coflow scheduling with release times, and a deterministic 4-approximation for the case without release times. As for concurrent open shop problem with release times, we give a combinatorial 3-approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.363 - ε) -approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4 - ε) -approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and ε . [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover's distance between two sets of weighted points A and B in $${\mathbb {R}}^{d}$$ under rigid transformation. EMDRT is an important problem in both theory and applications and has received considerable attentions in recent years. Previous research on this problem has resulted in only constant factor approximations and it has been an open problem for a long time to achieve PTAS solution. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithm runs roughly in $$O((nm)^{d+2}(\log nm)^{2d})$$ time (which is close to a lower bound on any PTAS for this problem), where n and m are the sizes of A and B, respectively. Our result is based on several new techniques, such as the Sequential Orthogonal Decomposition and Optimum Guided Base, and can be extended to several related problems, such as the problem of earth mover's distance under similarity transformation and the alignment problem, to achieve FPTAS for each of them. [ABSTRACT FROM AUTHOR]

The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190-206, 2011). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound. [ABSTRACT FROM AUTHOR]

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the STABLE EXTENSION OF PARTIAL MATCHING (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale-Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui (Algorithmica 58:151-169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2O(n), where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2o(n). Our algorithm is a non-trivial combination of a parameterized algorithm for SUBGRAPH ISOMORPHISM, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete. [ABSTRACT FROM AUTHOR]

Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications $$\mathcal {X}$$ , which are distinct pairs $$(s,t)\subseteq S\times T$$ , (typically S is the set of sources and T the set of destinations), and a port function $$\pi :\mathcal {X} \rightarrow P$$ where P is the set of ports. A routing list $$\mathcal {R}$$ is an ordered list of triples which are of the form ( s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ with $$s\in S$$ , $$t\in T$$ and $$p\in P$$ . It routes the communication ( s, t) to the port $$r(s,t) =p$$ which appears on the first triple in the list $$\mathcal {R}$$ that is of the form ( s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ . If $$r(s,t)=\pi (s,t)$$ , then we say that ( s, t) is properly routed by $$\mathcal {R}$$ and if all communications of $$\mathcal {X}$$ are properly routed, we say that $$\mathcal {R}$$ emulates $$(\mathcal {X}, \pi )$$ . The aim is to find a shortest routing list emulating $$(\mathcal {X}, \pi )$$ . In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication $$\mathcal {X}$$ , a port function $$\pi $$ and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating $$(\mathcal {X}, \pi )$$ of size at most k (resp. $$|\mathcal {X}| -k$$ ). We prove that both problems are NP-complete. We then give a 3-approximation for List Reduction, which can be generalized to higher dimensions. We also give a 4-approximation for Routing List in the fundamental case when there are only two ports (i.e. $$|P|=2$$ ), $$\mathcal {X}=S\times T$$ and $$|S|=|T|$$ . [ABSTRACT FROM AUTHOR]

The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin Theory, Ser B, 110:47-66, 2015) with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2 w, in time $$2^{O(w^2\log w)} \cdot n^2$$ . Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known. [ABSTRACT FROM AUTHOR]

A covering problem is an integer linear program of type $$\min \{c^Tx\mid Ax\ge D,\ 0\le x\le d,\ x \in \mathbb {Z}\}$$ where $$A\in \mathbb {Z}^{m\times n}_+$$ , $$D\in \mathbb {Z}_+^m$$ , and $$c,d\in \mathbb {Z}_+^n$$ . In this paper, we study covering problems with additional precedence constraints $$\{x_i\le x_j \ \forall j\preceq i \in \mathcal {P}\}$$ , where $$\mathcal {P}=([n], \preceq )$$ is some arbitrary, but fixed partial order on the items represented by the column-indices of A. Such precedence constrained covering problems ( PCCPs) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem, that is, where $$m=1$$ and $$d\equiv 1$$ . Our main result is a strongly-polynomial primal-dual approximation algorithm for PCCP with $$d\equiv 1$$ . Our approach generalizes the well-known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of $$\mathcal {P}$$ , that is, by the size of a maximum antichain in $$\mathcal {P}$$ . Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets $$\mathcal {P}$$ . For the general case with $$d\not \equiv 1$$ , we present pseudo-polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions. [ABSTRACT FROM AUTHOR]

Mutation region detection is the first step of searching for a disease gene and has facilitated the identification of several hundred human genes that can harbor mutations leading to a disease phenotype. Recently, the closest shared center problem (CSC) was proposed as a core to solve the mutation region detection problem when the pedigree is not given (Ma et al. in IEEE ACM Trans Comput Biol Bioinform 9(2):372-384, 2012). A ratio-2 approximation algorithm was proposed for the CSC problem in Ma et al. (IEEE ACM Trans Comput Biol Bioinform 9(2):372-384, 2012). In this paper, we will design a polynomial time approximation scheme for this problem. [ABSTRACT FROM AUTHOR]

The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. (2014) presented a randomized algorithm for the OCFL and proved that it is $$\mathrm {O}(\log ^2 n)$$ -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is $$\mathrm {O}(\log n)$$ -competitive. Since there is a lower bound of $$\mathrm {\Omega }(\log n)$$ for this problem, our result achieves the best possible competitive ratio, asymptotically. [ABSTRACT FROM AUTHOR]

We first consider the problem of finding a maximum size stable matching if incomplete lists and ties are both allowed, but ties are on one side only. For this problem we give a simple, linear time 3/2-approximation algorithm, improving on the best known approximation factor 5/3 of Irving and Manlove (J. Comb. Optim., doi:, ). Next, we show how this extends to the Hospitals/Residents problem with the same ratio if the residents have strict orders. We also give a simple linear time algorithm for the general problem with approximation factor 5/3, improving the best known 15/8-approximation algorithm of Iwama, Miyazaki and Yamauchi (SODA '07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 288-297, ). For the cases considered in this paper it is NP-hard to approximate within a factor of 21/19 by the result of Halldórsson et al. (ACM Transactions on Algorithms 3(3):30, ). Our algorithms not only give better approximation ratios than the cited ones, but are much simpler and run significantly faster. Also we may drop a restriction used in (J. Comb. Optim., doi:, ) and the analysis is substantially more moderate. Preliminary versions of this paper appeared in (Király, Egres Technical Report TR-2008-04, , ; Király in Proceedings of MATCH-UP 2008: Matching Under Preferences-Algorithms and Complexity, Satellite Workshop of ICALP, July 6, 2008, Reykjavík, Iceland, pp. 36-45, ; Király in ESA 2008, Lecture Notes in Computer Science, vol. 5193, pp. 623-634, ). For the related results obtained thenceforth see Sect. 5. [ABSTRACT FROM AUTHOR]

The subset sum algorithm is a natural heuristic for the classical Bin Packing problem: In each iteration, the algorithm finds among the unpacked items, a maximum size set of items that fits into a new bin. More than 35 years after its first mention in the literature, establishing the worst-case performance of this heuristic remains, surprisingly, an open problem. Due to their simplicity and intuitive appeal, greedy algorithms are the heuristics of choice of many practitioners. Therefore, better understanding simple greedy heuristics is, in general, an interesting topic in its own right. Very recently, Epstein and Kleiman (Proc. ESA 2008, pp. 368-380) provided another incentive to study the subset sum algorithm by showing that the Strong Price of Anarchy of the game theoretic version of the Bin Packing problem is precisely the approximation ratio of this heuristic. In this paper we establish the exact approximation ratio of the subset sum algorithm, thus settling a long standing open problem. We generalize this result to the parametric variant of the Bin Packing problem where item sizes lie on the interval $$(0, \alpha ]$$ for some $$\alpha \le 1$$ , yielding tight bounds for the Strong Price of Anarchy for all $$\alpha \le 1$$ . Finally, we study the pure Price of Anarchy of the parametric Bin Packing game for which we show nearly tight upper and lower bounds for all $$\alpha \le 1$$ . [ABSTRACT FROM AUTHOR]

The minimum cost subset k-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph G=( V, E) with costs on edges and a set of terminals T⊆ V. The goal is to find a minimum cost subgraph such that every pair of terminals are connected by k openly (vertex) disjoint paths. In this paper, we present an approximation algorithm for the subset k-connected subgraph problem which improves on the previous best approximation guarantee of O( klog k) by Nutov (ACM Trans. Algorithms 9(1):1, ). Our approximation guarantee, α(| T|), depends upon the number of terminals: So, when the number of terminals is large enough, the approximation guarantee improves significantly. Moreover, we show that, given an approximation algorithm for | T|= k, we can obtain almost the same approximation guarantee for any instances with | T|> k. This suggests that the hardest instances of the problem are when | T|≈ k. [ABSTRACT FROM AUTHOR]

Given two sets in the plane, R of n (terminal) points and S of m (Steiner) points, a full Steiner tree is a Steiner tree in which all points of R are leaves. In the bottleneck full Steiner tree (BFST) problem, one has to find a full Steiner tree T (with any number of Steiner points from S), such that the length of the longest edge in T is minimized, and, in the k-BFST problem, has to find a full Steiner tree T with at most k≤ m Steiner points from S such that the length of the longest edge in T is minimized. The problems are motivated by wireless network design. In this paper, we present an exact algorithm of ${{{\mathcal {O}}}}((n+m)\log^{2}{m})$ time to solve the BFST problem. Moreover, we show that the k-BFST problem is NP-hard and that there exists a polynomial-time approximation algorithm for the problem with performance ratio 4. [ABSTRACT FROM AUTHOR]

A spanning tree T of a graph G is called a tree t- spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. In this paper, we present an algorithm which constructs for an n-vertex m-edge unweighted graph G: For the latter result we use a new necessary condition for a graph to have a tree t-spanner: if a graph G has a tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most ⌈ t/2⌉ and diameter at most t in G. [ABSTRACT FROM AUTHOR]

This paper describes a simple greedy Δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables of the problem. (A simple example is Vertex Cover, with Δ=2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems. [ABSTRACT FROM AUTHOR]

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. (Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 367-378, ), Golovin et al. (Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), ), and Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439-453, ), 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. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439-453, ) 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 (see later elaboration). 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. in Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 367-378, ) and (Golovin et al. in Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), ). [ABSTRACT FROM AUTHOR]

In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k- Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et al. (Proceedings of the 49th annual IEEE symposium on foundations of computer science, FOCS, pp. 115-124, ) for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs; see Sect. 1.3. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case). In fact, this conjecture was later proved by Bateni, Hajiaghayi and Marx ( [abs], ). [ABSTRACT FROM AUTHOR]

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx: Ax≥ b, 0≤ x≤ d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A, b, c, d are nonnegative.) For any k≥2 and ε>0, if P≠ NP this ratio cannot be improved to k−1− ε, and under the unique games conjecture this ratio cannot be improved to k− ε. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx: Ax≤ b, 0≤ x≤ d} where A has at most k nonzeroes per column, we give a (2 k+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A is small compared to b. Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column. [ABSTRACT FROM AUTHOR]

We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, ), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios. For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, ) gave online strategies that have nearly optimal competitive ratios in several cost models. In this paper we first present a deterministic online algorithm that achieves an optimal competitiveness, for the most general cost model and all cache sizes. We then investigate the offline problem, which is NP-hard in general. We develop the first polynomial time algorithms that can manage arbitrary cache sizes. Our strategies achieve small constant factor approximation ratios. The algorithms are based on a general technique that reduces web caching with request reordering to a problem of computing batched service schedules. Our approximation result for the Fault Model also improves upon the best previous approximation guarantee known for web caching without request reordering. We remark that, unlike Feder et al., we assume that bypassing is allowed, i.e. referenced documents do not necessarily have to be brought into cache to serve their requests. [ABSTRACT FROM AUTHOR]