Search

Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP [ABSTRACT FROM AUTHOR]

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V , E , A) , where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F ⊆ E ( H ⊆ A ) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A . The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = ∅ and H = A For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27 4 -approximation algorithm. This algorithm achieves an approximation ratio of 33 5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition. [ABSTRACT FROM AUTHOR]

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by n , m , w max , and w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature T 0 ≥ w max and multiplicative cooling schedule with factor 1 - 1 / ℓ , where ℓ = ω (m n ln (m)) , with probability at least 1 - 1 / m computes in time O (ℓ (ln ln (ℓ) + ln (T 0 / w min))) a spanning tree with weight at most 1 + κ times the optimum weight, where 1 + κ = (1 + o (1)) ln (ℓ m) ln (ℓ) - ln (m n ln (m)) . Consequently, for any ϵ > 0 , we can choose ℓ in such a way that a (1 + ϵ) -approximation is found in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) with probability at least 1 - 1 / m . In the special case of so-called (1 + ϵ) -separated weights, this algorithm computes an optimal solution (again in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) ), which is a significant speed-up over Wegener's runtime guarantee of O (m 8 + 8 / ϵ) . Our tighter upper bound also admits the result that in some situations a hybridization of simulated annealing and the (1 + 1) EA can lead to stronger runtime guarantees than either algorithm alone. [ABSTRACT FROM AUTHOR]

We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5 / 3 + ε) -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1 + ε) OPT . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the (5 / 3 + ε) -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg's algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of (5 / 3 + ε) OPT . [ABSTRACT FROM AUTHOR]

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]

We give better approximation ratios for two Steiner Tree variants by combining known algorithms: the optimum 3 -decomposition and iterative randomized rounding. The first problem is Steiner Tree with minimum number of Steiner points and bounded edge length problem ( S M T - M S P ). The input consists of a set of terminals R in the Euclidean space R 2 . A feasible solution is a Steiner tree τ spanning R with Steiner points S such that every edge in τ has length at most 1 . The objective is to minimize S . Previously, the best approximation ratio for S M T - M S P was 1 + ln (4) + ϵ ≈ 2.386 . We present a polynomial time algorithm with ratio 2.277 . The second problem is Steiner Tree in quasi-bipartite graphs. It is a Steiner Tree problem on graph G = (V , E , c) with terminal set R when the edge set E does not include any edge between two vertices in V \ R . The best-known approximation ratio for this problem is 73 60 , We improve this ratio to 298 245 . [ABSTRACT FROM AUTHOR]

We study algorithms for the sliding-window model, an important variant of the data-stream model, in which the goal is to compute some function of a fixed-length suffix of the stream. We extend the smooth-histogram framework of Braverman and Ostrovsky (FOCS 2007) to almost-smooth functions, which includes all subadditive functions. Specifically, we show that if a subadditive function can be 1 + ε -approximated in the insertion-only streaming model, then it can be 2 + ε -approximated also in the sliding-window model with space complexity larger by factor O ε - 1 log w , where w is the window size. We demonstrate how our framework yields new approximation algorithms with relatively little effort for a variety of problems that do not admit the smooth-histogram technique. For example, in the frequency-vector model, a symmetric norm is subadditive and thus we obtain a sliding-window 2 + ε -approximation algorithm for it. Another example is for streaming matrices, where we derive a new sliding-window 2 + ε -approximation algorithm for Schatten 4-norm. We then consider graph streams and show that many graph problems are subadditive, including maximum submodular matching, minimum vertex-cover, and maximum k-cover, thereby deriving sliding-window O 1 -approximation algorithms for them almost for free (using known insertion-only algorithms). Finally, we design for every d ∈ 1 , 2 an artificial function, based on the maximum-matching size, whose almost-smoothness parameter is exactly d. [ABSTRACT FROM AUTHOR]

Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p i and the outcomes of the n tests are independent. A patient's score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient's risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions. [ABSTRACT FROM AUTHOR]

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]

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d - H I T T I N G S E T that runs in time n O (d 2 + (d / ϵ)) , uses O ((d 2 + (d / ϵ)) log n) bits of space, and achieves an approximation ratio of O ((d / ϵ) n ϵ) for any positive ϵ ≤ 1 and any d ∈ N . In particular, this yields a factor- O (log n) approximation algorithm which runs in time n O (log n) and uses O (log 2 n) bits of space (for constant d). As a corollary, we obtain similar bounds for V E R T E X C O V E R and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for V E R T E X C O V E R on graphs with maximum degree Δ , and an algorithm for computing maximal independent sets, both of which run in time n O (Δ) and use O (Δ log n) bits of space. For the more general d - H I T T I N G S E T problem, we devise a factor-d approximation algorithm which runs in time n O (d δ 2) and uses O (d δ 2 log n) bits of space on set families where each element appears in at most δ sets. For I N D E P E N D E N T S E T restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O (log n) bits of space. We also devise a factor- O (d 2) approximation algorithm for D O M I N A T I N G S E T on d-degenerate graphs which runs in time n O (log n) and uses O (log 2 n) bits of space. For d-regular graphs, we show how a known randomized factor- O (log d) approximation algorithm can be derandomized to run in time n O (1) and use O (log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms. [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 article, we study some fault-tolerant covering problems in metric spaces. In the metric multi-cover problem (MMC), we are given two point sets Y (servers) and X (clients) in an arbitrary metric space (X ∪ Y , d) , a positive integer k that represents the coverage demand of each client, and a constant α ≥ 1 . Each server can host a single ball of arbitrary radius centered on it. Each client x ∈ X needs to be covered by at least k such balls centered on servers. The objective function that we wish to minimize is the sum of the α -th powers of the radii of the balls. We also study some non-trivial generalizations of the MMC, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the t-MMC, where we require the number of open servers to be at most some given integer t. We present the first constant approximations for these fault-tolerant covering problems. Our algorithms are based on the following paradigm: for each of the three problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding 1-covering problem, where the coverage demand of each client is 1. The reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for 1-covering, we obtain our results for the MMC and these generalizations. [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]

The Maximum Carpool Matching problem is a star packing problem in directed graphs. Formally, given a directed graph G = (V , A) , a capacity function c : V → N , and a weight function w : A → R + , a carpool matching is a subset of arcs, M ⊆ A , such that every v ∈ V satisfies: (1) d M in (v) · d M out (v) = 0 , (2) d M in (v) ≤ c (v) , and (3) d M out (v) ≤ 1 . A vertex v for which d M out (v) = 1 is a passenger, and a vertex for which d M out (v) = 0 is a driver who has d M in (v) passengers. In the Maximum Carpool Matching problem the goal is to find a carpool matching M of maximum total weight. The problem arises when designing an online carpool service, such as Zimride (Zimride by enterprise. https://zimride.com/), which tries to connect between users based on a similarity function. The problem is known to be NP-hard, even in the unweighted and uncapacitated case. The Maximum Group Carpool Matching problem, is an extension of the Maximum Carpool Matching where each vertex represents an unsplittable group of passengers. Formally, each vertex u ∈ V has a size s (u) ∈ N , and the constraint d M in (v) ≤ c (v) is replaced with ∑ u : (u , v) ∈ M s (u) ≤ c (v) . We show that Maximum Carpool Matching can be formulated as an unconstrained submodular maximization problem, thus it admits a 1 2 -approximation algorithm. We show that the same formulation does not work for Maximum Group Carpool Matching, nevertheless, we present a local search (1 2 - ε) -approximation algorithm for Maximum Group Carpool Matching. For the unweighted variant of both problems when the maximum possible capacity, c max , is bounded by a constant, we provide a local search (1 2 + 1 2 c max - ε) -approximation algorithm. We also provide an APX-hardness result, even if the maximum degree and c max are at most 3. [ABSTRACT FROM AUTHOR]

The construction of r-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate r-nets with respect to Euclidean distance. For any fixed ϵ > 0 , the approximation factor is 1 + ϵ and the complexity is polynomial in the dimension and subquadratic in the number of points; the algorithm succeeds with high probability. Specifically, we improve upon the best previously known (LSH-based) construction of Eppstein et al. (Approximate greedy clustering and distance selection for graph metrics, 2015. CoRR arxiv: abs/1507.01555) in terms of complexity, by reducing the dependence on ϵ , provided that ϵ is sufficiently small. Moreover, our method does not require LSH but follows Valiant's (J ACM 62(2):13, 2015. 10.1145/2728167) approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which r-nets are computed efficiently and the error can be controlled. Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the (1 + ϵ) -approximate k-th nearest neighbor distance in time subquadratic in the size of the input. [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]

The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class # RH Π 1 . It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in # RH Π 1 , and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms. [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]

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]

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]

For a graph $$G=(V,E)$$ the minimum line-distortion problem asks for the minimum k such that there is a mapping f of the vertices into points of the line such that for each pair of vertices x, y the distance on the line $$|f(x) - f(y)|$$ can be bounded by the term $$d_G(x, y)\le |f(x)-f(y)|\le k \, d_G(x, y)$$ , where $$d_G(x, y)$$ is the distance in the graph. The minimum bandwidth problem minimizes the term $$\max _{uv\in E}|f(u)-f(v)|$$ , where f is a mapping of the vertices of G into the integers $$\{1, \ldots , n\}$$ . We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson-Seymour's path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show: [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]

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]

Since Tinhofer proposed the MinGreedy algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MinGreedy cannot improve on the trivial approximation ratio of $$\frac{1}{2}$$ whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree $$\varDelta $$ : we show that MinGreedy achieves a $${\frac{{\varDelta }-1}{2{\varDelta }-3}} $$ -approximation for graphs with $${\varDelta } {=} 3$$ and for $$\varDelta $$ -regular graphs, and a guarantee of $${\frac{{\varDelta }-1/2}{2{\varDelta }-2}} $$ for graphs with maximum degree $${\varDelta } $$ . Interestingly, our bounds even hold for the deterministic MinGreedy that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a $${\frac{{\varDelta }-1}{2{\varDelta }-3}}$$ -inapproximability result for graphs with maximum degree $${\varDelta } $$ ; thus, these greedy algorithms do not achieve a $$\frac{1}{2} {+} \varepsilon $$ -approximation and in particular the $$\frac{2}{3}$$ -approximation obtained by the deterministic MinGreedy for $${\varDelta } {=} 3$$ is optimal in this class. For k-uniform hypergraphs we show a tight $$\frac{1}{k}$$ -inapproximability bound. We also study fully randomized priority algorithms and give a $$\frac{5}{6}$$ -inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms. [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 study the exponential time complexity of approximate counting satisfying assignments of CNFs. We reduce the problem to deciding satisfiability of a CNF. Our reduction preserves the number of variables of the input formula and thus also preserves the exponential complexity of approximate counting. Our algorithm is also similar to an algorithm which works particularly well in practice and for which no approximation guarantee is known. [ABSTRACT FROM AUTHOR]

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant $$l$$ , outputs a directed Steiner tree of cost no larger than $$2(l-1)(\ln n+1)$$ times the cost of any $$l$$ -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most $$l$$ arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of $$O(\log n)$$ , and (2) the tree cover problem on directed graphs can also be approximated within a factor of $$O(\log n)$$ . [ABSTRACT FROM AUTHOR]

Given an interval graph and integer $$k$$ , we consider the problem of finding a subgraph of size $$k$$ with a maximum number of induced edges, called densest k -subgraph problem in interval graphs. This problem is NP-hard even for chordal graphs (Perl and Corneil in Discret Appl Math 9(1):27-39, ), and there is probably no PTAS for general graphs (Khot and Subhash in SIAM J Comput 36(4):1025-1071, ). However, the exact complexity status for interval graphs is a long-standing open problem (Perl and Corneil in Discret Appl Math 9(1):27-39, ), and the best known approximation result is a $$ 3 $$ -approximation algorithm (Liazi et al. in Inf Process Lett 108(1):29-32, ). We shed light on the approximation complexity of finding a densest $$ k $$ -subgraph in interval graphs by presenting a polynomial-time approximation scheme (PTAS), that is, we show that there is an $$ (1+\epsilon ) $$ -approximation algorithm for any $$ \epsilon > 0 $$ , which is the first such approximation scheme for the densest $$ k $$ -subgraph problem in an important graph class without any further restrictions. [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]

We consider Degree Constrained Survivable Network problems. For the directed Degree Constrained k -Edge-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof. Our main contribution is giving a framework to handle node-connectivity degree constrained problems with the iterative rounding method. In particular, for the degree constrained versions of the Element-Connectivity Survivable Network problem on undirected graphs, and of the k -Outconnected Subgraph problem on both directed and undirected graphs, our algorithm computes a solution J of cost O(log k) times the optimal, with degrees O(2)⋅ b( v). Similar result are obtained for the k -Connected Subgraph problem. The latter improves on the only degree approximation O( klog n)⋅ b( v) in O( n) time on undirected graphs by Feder, Motwani, and Zhu. [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]

The Lovász ϑ-function (Lovász in IEEE Trans. Inf. Theory, 25:1-7, ) of a graph G=( V, E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr( X) equals 1, and X=0 whenever { i, j}∈ E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale's primal-dual method for SDP to design an algorithm to approximate the ϑ-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$, where ϑ= ϑ( G) and M= O( n) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ϑ( G) exactly in time O( ϑ nlog n). Moreover, our techniques generalize to the weighted Lovász ϑ-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+ ϵ) in time O( ϵ nlog n). [ABSTRACT FROM AUTHOR]

The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, ) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively. We consider the problem of building approximate squares in TAM. Given any $\varepsilon \in (0,\frac{1}{4}]$ we show how to construct squares whose sides are within (1± ε) N of any given positive integer N using $O( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types. We prove a matching lower bound by showing that $\varOmega( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types are necessary almost always to build squares of required approximate dimensions. In comparison, the optimal construction for a square of side exactly N in TAM uses $O(\frac{\log N}{\log \log N})$ tile types. The question of constructing approximate squares has been recently studied in a modified tile assembly model involving concentration programming. All our results are trivially translated into the concentration programming model by assuming arbitrary (non-zero) concentrations for our tile types. Indeed, the non-zero concentrations could be chosen by an adversary and our results would still hold. Our construction can get highly accurate squares using very few tile types and are feasible starting from values of N that are orders of magnitude smaller than the best comparable constructions previously suggested. At an accuracy of ε=0.01, the number of tile types used to achieve a square of size 10 is just 58 and our constructions are proven to work for all N≥13130. If the concentrations of the tile types are carefully chosen, we prove that our construction assembles an L× L square in optimal assembly time O( L) where (1− ε) N≤ L≤(1+ ε) N. [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 introduce and study the donation center location problem, which has an additional application in network testing and may also be of independent interest as a general graph-theoretic problem. Given a set of agents and a set of centers, where agents have preferences over centers and centers have capacities, the goal is to open a subset of centers and to assign a maximum-sized subset of agents to their most-preferred opened centers, while respecting the capacity constraints. We prove that in general, the problem is hard to approximate within n for any ϵ>0. In view of this, we investigate two special cases. In one, every agent has a bounded number of centers on its preference list, and in the other, all preferences are induced by a line-metric. We present constant-factor approximation algorithms for the former and exact polynomial-time algorithms for the latter. [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]

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r+1.357. In particular, the composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3. Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs. Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case. [ABSTRACT FROM AUTHOR]

We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model. We give an algorithm that, given a task system and ε>0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2−1/ m+ ε) machines, or that the system is not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/ ε. We also provide a generalized tight bound that trades off speed with additional machines. [ABSTRACT FROM AUTHOR]