Search

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

In this article we present and analyse new multilevel adaptations of classical stochastic approximation algorithms for the computation of a zero of a function f : D → R d defined on a convex domain D ⊂ R d , which is given as a parameterised family of expectations. The analysis of the error and the computational cost of our method is based on similar assumptions as used in Giles (Oper Res 56(3):607–617, 2008) for the computation of a single expectation. Additionally, we essentially only require that f satisfies a classical contraction property from stochastic approximation theory. Under these assumptions we establish error bounds in pth mean for our multilevel Robbins–Monro and Polyak–Ruppert schemes that decay in the computational time as fast as the classical error bounds for multilevel Monte Carlo approximations of single expectations known from Giles (Oper Res 56(3):607–617, 2008). Our approach is universal in the sense that having multilevel implementations for a particular application at hand it is straightforward to implement the corresponding stochastic approximation algorithm. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is to develop new techniques in approximate dynamic programming, along with the notions of rounded distributions and inventory filtering, to devise a quasi-PTAS for the capacitated assortment planning problem, recently studied by Goyal et al. (Oper Res 64(1):219-235, 2016). Motivated by real-life applications, their nested preference lists model stands as the only setting in dynamic assortment optimization where provably ϵ-optimal inventory levels can be efficiently computed. However, these findings crucially depend on certain distributional assumptions, leaving the general problem wide open in terms of approximability prior to this work. In addition to proposing the first rigorous approach for handling the nested preference lists model in its utmost generality, from a technical perspective, we augment the existing literature on dynamic programming with a number of promising ideas. These are novel algorithmic tools for efficiently keeping approximate distributions as part of the state description, while losing very little information and while accumulating only small approximation errors throughout the overall computation. From a conceptual perspective, at the cost of losing an ϵ-factor in optimality, we show how to dramatically improve on the truly exponential nature of standard dynamic programs, which seem essential for the purpose of computing optimal inventory levels. [ABSTRACT FROM AUTHOR]

In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a (2k-1)-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%. [ABSTRACT FROM AUTHOR]

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, we define v-coverH(G) (resp. e-coverH(G)) as the minimum number of vertices (resp. edges) whose removal from G produces a graph without any minor isomorphic to H. Also v-packH(G) (resp. e-packH(G)) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of G that contain a minor isomorphic to H. We denote by θr the graph with two vertices and r parallel edges between them. When H=θr, the parameters v-coverH, e-coverH, v-packH, and e-packH are NP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large θr-girth, 2015, arXiv:1510.03041), we give an algorithmic proof that if v-packθr(G)≤k, then v-coverθr(G)=O(klogk), and similarly for e-packθr and  e-coverθr. In other words, the class of graphs containing θr as a minor has the vertex/edge Erdős-Pósa property, for every positive integer r. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an O(logOPT)-approximation algorithm for v-packθr, v-coverθr, e-packθr, and e-coverθr that runs in O(n·log(n)·m) steps. Also, we derive several new Erdős-Pósa-type results from the techniques that we introduce. [ABSTRACT FROM AUTHOR]

Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, and one seeks to schedule the jobs to minimize the total sum of these costs. The framework captures many important scheduling objectives such as weighted flow time or weighted tardiness. Still, the general case as well as the mentioned special cases are far from being very well understood yet, even for only one machine. Aiming for better general understanding of this problem, in this paper we focus on the case of uniform job release dates on one machine for which the state of the art is a 4-approximation algorithm. This is true even for a special case that is equivalent to the covering version of the well-studied and prominent unsplittable flow on a path problem, which is interesting in its own right. For that covering problem, we present a quasi-polynomial time (1+ε)-approximation algorithm that yields an (e+ε)-approximation for the above scheduling problem. Moreover, for the latter we devise the best possible resource augmentation result regarding speed: a polynomial time algorithm which computes a solution with optimal cost at 1+ε speedup. Finally, we present an elegant QPTAS for the special case where the cost functions of the jobs fall into at most logn many classes. This algorithm allows the jobs even to have up to logn many distinct release dates. All proposed quasi-polynomial time algorithms require the input data to be quasi-polynomially bounded. [ABSTRACT FROM AUTHOR]

We consider the generalized minimum Manhattan network problem (GMMN). The input to this problem is a set R of n pairs of terminals, which are points in R2. The goal is to find a minimum-length rectilinear network that connects every pair in R by a Manhattan path, that is, a path of axis-parallel line segments whose total length equals the pair’s Manhattan distance. This problem is a natural generalization of the extensively studied minimum Manhattan network problem (MMN) in which R consists of all possible pairs of terminals. Another important special case is the well-known rectilinear Steiner arborescence problem (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. We obtain an O(logn)-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple O(logd+1n)-approximation algorithm for the problem in arbitrary fixed dimension d. As a corollary, we obtain an exponential improvement upon the previously best O(nε)-ratio for MMN in d dimensions (ESA 2011). En route, we show that an existing O(logn)-approximation algorithm for 2D-RSA generalizes to higher dimensions. [ABSTRACT FROM AUTHOR]

The edge dominating set problem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and connected dominations combined. In the b-EDS problem, each edge needs to be dominated b times. Connected EDS requires an edge dominating set to be connected while it has to form a tree in Tree Cover. Although each of EDS, b-EDS, and Connected EDS (or Tree Cover) has been well studied, each known to be approximable within 2 (or 8/3 for b-EDS in general), nothing is known when these extensions are imposed simultaneously on EDS unlike in the case of the (vertex) dominating set problem. We consider Connected 2-EDS and 2-Tree Cover (i.e., a combination of 2-EDS and Tree Cover), and present a polynomial algorithm approximating each within 2. Moreover, it will be shown that the single tree computed is no larger than twice the optimum for (not necessarily connected) 2-EDS, thus also approximating 2-EDS equally well. It also implies that 2-EDS with clustering properties can be approximated within 2 as well. [ABSTRACT FROM AUTHOR]

In the Independent Set of Convex Polygons problem we are given a set of weighted convex polygons in the plane and we want to compute a maximum weight subset of non-overlapping polygons. This is a very natural and well-studied problem with applications in many different areas. Unfortunately, there is a very large gap between the known upper and lower bounds for this problem. The best polynomial time algorithm we know has an approximation ratio of nϵ and the best known lower bound shows only strong NP-hardness. In this paper we close this gap, assuming that we are allowed to shrink the polygons a little bit, by a factor 1-δ for an arbitrarily small constant δ>0, while the compared optimal solution cannot do this (resource augmentation). In this setting, we improve the approximation ratio of nϵ to (1+ϵ) which matches the above lower bound that still holds if we can shrink the polygons. [ABSTRACT FROM AUTHOR]

Local computation algorithms (LCAs) produce small parts of a single (possibly approximate) solution to a given search problem using time and space sublinear in the size of the input. In this work we present LCAs whose time complexity (and usually also space complexity) is independent of the input size. Specifically, we give (1) a (1 - ϵ)-approximation LCA to the maximum weight acyclic edge set, (2) LCAs for approximating multicut and integer multicommodity flow on trees, and (3) a local reduction of weighted matching to any unweighted matching LCA, such that the running time of the weighted matching LCA is d times (where d is the maximal degree) the running time of the unweighted matching LCA, (and therefore independent of the edge weight function). [ABSTRACT FROM AUTHOR]

Given a graph $$G=(V,E)$$ with a label set $$L = \{\ell _1, \ell _2, \ldots , \ell _q \}$$ , in which each edge has a label from L, and a source $$s \in V$$ together with a sink $$t \in V$$ , the Minimum Label s- t Cut problem asks to pick a set $$L' \subseteq L$$ of labels with minimized cardinality, such that the removal of all edges with labels in $$L'$$ from G disconnects s and t. Let $$n = |V|$$ and $$m = |E|$$ . The previous best known approximation ratio for this problem in literature is $$O(m^{1/2})$$ . We present two simple and purely combinatorial approximation algorithms for the problem with ratios $$O(n^{2/3}/\text {OPT}^{1/3})$$ and $$O(m^{1/2} / \text {OPT}^{1/2})$$ , where $$\text {OPT}$$ is the optimal value of the input instance. The former result gives the first approximation ratio which is sublinear in n for the problem, and in particular applies to the instances with dense graphs (e.g., $$m = \varTheta (n^2)$$ ). The latter result improves the previous ratio $$O(m^{1/2})$$ , as we can always assume that $$\text {OPT}$$ is a super-constant. [ABSTRACT FROM AUTHOR]

In several applications of automatic diagnosis and active learning, a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general, the process of reading the value of a variable might involve some cost. This cost should be taken into account when deciding the next variable to read. The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables' assignments). Our algorithm builds a strategy (decision tree) which attains a logarithmic approximation simultaneously for the expected and worst cost spent. This is best possible under the assumption that $${{{\mathcal {P}}}} \ne \mathcal{NP}$$ . [ABSTRACT FROM AUTHOR]

We consider the Set Once Strip Cover problem, in which n wireless sensors are deployed over a one-dimensional region. Each sensor has a fixed battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The problem is to find an assignment of radii and activation times that maximizes the length of time during which the entire region is covered. We show that this problem is NP-hard. In addition, we show that RoundRobin, the algorithm in which the sensors take turns covering the entire region, has a tight approximation guarantee of $$\frac{3}{2}$$ . This result also applies to the more general Strip Cover problem, in which each radius may be set finitely-many times. Moreover, we show that the more general class of duty cycle algorithms, in which groups of sensors take turns covering the entire region, can do no better. Finally, we give an $$O(n^2 \log {n})$$ -time optimization algorithm for the related Set Radius Strip Cover problem, in which sensors must be activated immediately. [ABSTRACT FROM AUTHOR]

This paper investigates a meta-heuristic (MH) for the Pareto-optimal dissimilar path problem (DPP) (PDPP) whose solution is a set composed of at least two different paths. The objective vector of a PDPP includes some conflicting objectives: on the one hand, the average path measures such as the length and risk of paths in a solution must be kept low and, on the other hand, the dissimilarity among these paths should be kept high. The dissimilarity of the DPP is a measure of a paths set with cardinality no less than two. However, just one path can be extracted from a chromosome in the existing MHs for various path problems. This results in a great difficulty to evaluate the chromosome in the existing MHs when we apply them to solve DPP and, consequently, there exists no MH for solving the DPP so far. In this paper, a new decoding approach of a chromosome is first explored and, with this approach, a set of paths can be extracted from a chromosome. By combining the simulated annealing (SA), in which the new decoding approach is adopted, with the well-known greedy randomized adaptive search procedure (GRASP), a SA-based GRASP for the PDPP is proposed. The proposed algorithm is compared against a most recent heuristic, whose performance is better than all of the early approaches, for the PDPP and the experimental results show that the proposed algorithm is able to quickly create superior approximation of the efficient set of the PDPP than the existing solution approaches for the PDPP. [ABSTRACT FROM AUTHOR]

In the numerical approximation of fractional order derivatives, the crucial point is to balance the computing complexity and the computing accuracy. We proposed a piecewise memory principle for fractional derivatives, in which the past history is divided into several segments instead of discarded. The piecewise approximation is performed on each segment. Error estimation of piecewise memory principle is analyzed also. Numerical examples show that the contradiction of computing accuracy and complexity is effectively relaxed and the piecewise memory principle is superior to the existing short, variable and equal-weight memory principles. The impacts of the memory length, step size and segment size are also discussed. [ABSTRACT FROM AUTHOR]

Complete-linkage clustering is a very popular method for computing hierarchical clusterings in practice, which is not fully understood theoretically. Given a finite set $$P\subseteq \mathbb {R}^d$$ of points, the complete-linkage method starts with each point from P in a cluster of its own and then iteratively merges two clusters from the current clustering that have the smallest diameter when merged into a single cluster. We study the problem of partitioning P into k clusters such that the largest diameter of the clusters is minimized and we prove that the complete-linkage method computes an O(1)-approximation for this problem for any metric that is induced by a norm, assuming that the dimension d is a constant. This improves the best previously known bound of $$O(\log {k})$$ due to Ackermann et al. (Algorithmica 69(1):184-215, 2014). Our improved bound also carries over to the k-center and the discrete k-center problem. [ABSTRACT FROM AUTHOR]

Given an n-vertex digraph $$D = (V, A)$$ the Max- $$k$$ - Ordering problem is to compute a labeling $$\ell : V \rightarrow [k]$$ maximizing the number of forward edges, i.e. edges ( u, v) such that $$\ell (u) < \ell (v)$$ . For different values of k, this reduces to maximum acyclic subgraph ( $$k=n$$ ), and Max-DiCut ( $$k=2$$ ). This work studies the approximability of Max- $$k$$ - Ordering and its generalizations, motivated by their applications to job scheduling with soft precedence constraints. We give an LP rounding based 2-approximation algorithm for Max- $$k$$ - Ordering for any $$k=\{2,\ldots , n\}$$ , improving on the known $$\left. 2k\big /(k-1)\right. $$ -approximation obtained via random assignment. The tightness of this rounding is shown by proving that for any $$k=\{2,\ldots , n\}$$ and constant $$\varepsilon > 0$$ , Max- $$k$$ - Ordering has an LP integrality gap of $$2 - \varepsilon $$ for $$n^{\varOmega \left( \left. 1\big /\log \log k\right. \right) }$$ rounds of the Sherali-Adams hierarchy. A further generalization of Max- $$k$$ - Ordering is the restricted maximum acyclic subgraph problem or RMAS, where each vertex v has a finite set of allowable labels $$S_v \subseteq \mathbb {Z}^+$$ . We prove an LP rounding based $$\left. 4\sqrt{2}\big /\left( \sqrt{2}+1\right) \right. \approx 2.344$$ approximation for it, improving on the $$2\sqrt{2} \approx 2.828$$ approximation recently given by Grandoni et al. (Inf Process Lett 115(2): 182-185, 2015). In fact, our approximation algorithm also works for a general version where the objective counts the edges which go forward by at least a positive offset specific to each edge. The minimization formulation of digraph ordering is DAG edge deletion or DED $$(k)$$ , which requires deleting the minimum number of edges from an n-vertex directed acyclic graph (DAG) to remove all paths of length k. We show that a simple rounding of the LP relaxation as well as a local ratio approach for DED $$(k)$$ yields k-approximation for any $$k\in [n]$$ . A vertex deletion version was studied earlier by Paik et al. (IEEE Trans Comput 43(9): 1091-1096, 1994), and Svensson (Proceedings of the APPROX, 2012). [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]

In this letter, an ultra-low-power capacitor-splitting switching algorithm for successive approximation register analog-to-digital converters is proposed. To achieve low power, the first three bit cycles consume no power from the reference by introducing minus energy during the third bit cycle and proper switching algorithm. To further reduce the switching energy, only single-side capacitors are switched from the forth bit cycle. Besides, to add one bit, the dummy capacitor is realized by four unit capacitors and switched to generate the least significant bit. Compared to the Sanyal and Sun switching technique, the proposed capacitor switching method achieves 94.19% energy saving and 47.66% capacitor area reduction. [ABSTRACT FROM AUTHOR]

High utility sequential pattern (HUSP) mining has emerged as an important topic in data mining. A number of studies have been conducted on mining HUSPs, but they are mainly intended for non-streaming data and thus do not take data stream characteristics into consideration. Streaming data are fast changing, continuously generated unbounded in quantity. Such data can easily exhaust computer resources (e.g., memory) unless a proper resource-aware mining is performed. In this study, we explore the fundamental problem of how limited memory can be best utilized to produce high quality HUSPs over a data stream. We design an approximation algorithm, called MAHUSP, that employs memory adaptive mechanisms to use a bounded portion of memory, in order to efficiently discover HUSPs over data streams. An efficient tree structure, called MAS-Tree, is proposed to store potential HUSPs over a data stream. MAHUSP guarantees that all HUSPs are discovered in certain circumstances. Our experimental study shows that our algorithm can not only discover HUSPs over data streams efficiently, but also adapt to memory allocation with limited sacrifices in the quality of discovered HUSPs. Furthermore, in order to show the effectiveness and efficiency of MAHUSP in real-life applications, we apply our proposed algorithm to a web clickstream dataset obtained from a Canadian news portal to showcase users' reading behavior, and to a real biosequence database to identify disease-related gene regulation sequential patterns. The results show that MAHUSP effectively discovers useful and meaningful patterns in both cases. [ABSTRACT FROM AUTHOR]

The order estimates of the best M-term trigonometric approximations of functions $$ {D}_{\beta}^{\psi } $$ and the classes of ( ψ , β)-differentiable periodic multivariate functions in the space L, 2 ≤ q < ∞ are obtained. It is shown that, under certain conditions imposed on the parameter q; the best M-term trigonometric approximations $$ {e}_M{\left({L}_{\beta, 1}^{\psi}\right)}_q $$ have better order than the best orthogonal trigonometric approximations $$ e\frac{1}{M}{\left({L}_{\beta, 1}^{\psi}\right)}_q $$. [ABSTRACT FROM AUTHOR]

In this paper, we propose a query relaxation approach to handle the problem of empty or too little answers returned from RDF query. We apply RDF entailment to triple patterns in the original query to get more general answers. We propose the notion of semantic similarity degree so that the returned answers are semantically close to the original query. We present how to compute the semantic similarity degree of a relaxed query with respect to the original query. With the semantic similarity degrees, we can choose the relaxed queries that are semantically close to the original query. On this basis, we give the query relaxation algorithm. We verify our approach by experiments. It is shown that our approach of RDF query relaxation based on the semantic similarity degree has some good performances and is feasible. [ABSTRACT FROM AUTHOR]

We deduce asymptotic equalities for the least upper bounds of the approximations of functions from the classes $$ {W}_{\beta}^r{H}^{\alpha } $$ and H by biharmonic Poisson integrals in the uniform metric. [ABSTRACT FROM AUTHOR]

We introduce the concept of a computability component on an admissible set and consider minimal and maximal computability components on hereditarily finite superstructures as well as jumps corresponding to these components. It is shown that the field of real numbers Σ-reduces to jumps of the maximal computability component on the least admissible set ℍ픽(∅). Thus we obtain a result that, in terms of Σ-reducibility, connects real numbers, conceived of as a structure, with real numbers, conceived of as an approximation space. Also we formulate a series of natural open questions. [ABSTRACT FROM AUTHOR]

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3. [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]

This paper addresses the problem of capturing nondominated points on non-convex pareto frontier, which are encountered in E-[0,1] convex multi-objective programming problems. We use E-[0,1] map to transfer non-convex pareto frontier to convex pareto frontier, then An algorithm to find a piecewise linear approximation of the nondominated set of convex pareto frontier are applied. Finally, the inverse map of E-[0,1] is used to get the nondominated set of non-convex pareto frontier. [ABSTRACT FROM AUTHOR]

The genome median problem is an important problem in phylogenetic reconstruction under rearrangement models. It can be stated as follows: Given three genomes, find a fourth that minimizes the sum of the pairwise rearrangement distances between it and the three input genomes. In this paper, we model genomes as matrices and study the matrix median problem using the rank distance. It is known that, for any metric distance, at least one of the corners is a $$\frac{4}{3}$$ -approximation of the median. Our results allow us to compute up to three additional matrix median candidates, all of them with approximation ratios at least as good as the best corner, when the input matrices come from genomes. We also show a class of instances where our candidates are optimal. From the application point of view, it is usually more interesting to locate medians farther from the corners, and therefore, these new candidates are potentially more useful. In addition to the approximation algorithm, we suggest a heuristic to get a genome from an arbitrary square matrix. This is useful to translate the results of our median approximation algorithm back to genomes, and it has good results in our tests. To assess the relevance of our approach in the biological context, we ran simulated evolution tests and compared our solutions to those of an exact DCJ median solver. The results show that our method is capable of producing very good candidates. [ABSTRACT FROM AUTHOR]

In the Basic Resource Replication problem, we are given a graph, embedded into a distance metric, and a set of data items. The goal is to assign one data item to each vertex so as to minimize the maximum distance any vertex has to travel to access all the data items. We consider several variants of this problem in this paper, and propose new approximation results for them. These problems are of fundamental interest in the areas of P2P networks, sensor networks and ad hoc networks, where placement of replicas is the main bottleneck on performance. We observe that the threshold graph technique, which has been applied to several $$k$$ -center type problems, yields simple and efficient approximation algorithms for resource replication problems. Our results range from positive (efficient, small constant factor, approximation algorithms) to extremely negative (impossibility of existence of any algorithm with non-trivial approximation guarantee, i.e., with positive approximation ratio) for different versions of the problem. [ABSTRACT FROM AUTHOR]

In the set cover problem (SCP), a set of elements $${X = \{x_{1}, x_{2}, \ldots, x_{n}\}}$$ and a collection $${F = \{S_{1}, S_{2}, \ldots, S_{m}\}}$$ of subsets of X, for some integers $${n, m \geq 1}$$ , are given. In addition, each element of $${X}$$ belongs to at least one member of F. The problem is to find a sub-collection $${C \subseteq F}$$ such that $${\bigcup\nolimits_{S\in C} S = X}$$ and C has the minimum cardinality. When $${|S| \leq k}$$ for all $${S \in F}$$ , the k-set cover problem ( k-SCP) is obtained. For all $${k \geq 3}$$ , the k-SCP is an NP-complete optimization problem (Karp in Complexity of computer computations. Plenum Press, New-York, pp 85-103, 1972). It is well known that a greedy algorithm for the k-SCP is a $${h_{k}}$$ -approximation algorithm, where $${h_{k} = \sum\nolimits_{i=1}^k {\frac{1}{i}}}$$ is the $${k^{th}}$$ harmonic number. Since the SCP is a fundamental problem, so there is a research effort to improve this approximation ratio. In this paper, the authors propose an approximation algorithm which accepts any instance of the k-SCP problem as an input. This approximation algorithm is a $${(1 + \frac{1}{k})}$$ -algorithm with a polynomial running time for $${k \geq 6}$$ that improves the previous best approximation ratio $${h_{k} - 0.5902}$$ for all values of $${k \geq 6}$$ . [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]

Let $$b\in {\mathbb {N}}_{\ge 1}$$ and let $${\mathcal {H}}=(V,{\mathcal {E}})$$ be a hypergraph with maximum vertex degree $${\varDelta }$$ and maximum edge size $$l$$ . A set $$b$$ -multicover in $${\mathcal {H}}$$ is a set of edges $$C \subseteq {\mathcal {E}}$$ such that every vertex in $$V$$ belongs to at least $$b$$ edges in $$C$$ . $${\textsc {set }}\, b\text {-}{\textsc {multicover}}$$ is the problem of finding a set $$b$$ -multicover of minimum cardinality, and for $$b=1$$ it is the fundamental set cover problem. Peleg et al. (Algorithmica 18(1):44-66, ) gave a randomized algorithm achieving an approximation ratio of $$\delta \cdot \big (1-\big (\frac{c}{n}\big )^\frac{1}{\delta }\big )$$ , where $$\delta := {\varDelta }- b + 1$$ and $$c>0$$ is a constant. As this ratio depends on the instance size $$n$$ and tends to $$\delta $$ as $$n$$ tends to $$\infty $$ , it remained an open problem whether an approximation ratio of $$\delta \alpha $$ with a constant $$\alpha < 1$$ can be proved. In fact, the authors conjectured that for any fixed $${\varDelta }$$ and $$b$$ , the problem is not approximable within a ratio smaller than $$\delta $$ , unless $${\mathcal {P}}={\mathcal {NP}}$$ . We present a randomized algorithm of hybrid type for $${\textsc {set }}\, b\text {-}{\textsc {multicover}}$$ , $$b \ge 2$$ , combining LP-based randomized rounding with greedy repairing, and achieve an approximation ratio of $$\delta \cdot \left( 1 - \frac{11({\varDelta }- b)}{72l} \right) $$ for hypergraphs with maximum edge size $$l \in {\mathcal {O}}\left( \max \big \{(nb)^\frac{1}{5},n^\frac{1}{4}\big \}\right) $$ . In particular, for all hypergraphs where $$l$$ is constant, we get an $$\alpha \delta $$ -ratio with constant $$\alpha < 1$$ . Hence the above stated conjecture does not hold for hypergraphs with constant $$l$$ and we have identified the boundedness of the maximum hyperedge size as a relevant parameter responsible for approximations below $$\delta $$ . [ABSTRACT FROM AUTHOR]

We study the two-dimensional bin packing problem: Given a list of $$n$$ rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. Our problem consists of two versions; in the first version it is not allowed to rotate the rectangles while in the other it is allowed to rotate the rectangles by $$90^{\circ }$$ , i.e. to exchange the widths and the heights. Two-dimensional bin packing is a generalization of its one-dimensional counterpart and is therefore strongly $$\mathcal {NP}$$ -hard. Furthermore Bansal et al. (Math Oper Res 31(1):31-49, ) showed that even an $$\mathcal {APTAS}$$ is ruled out for this problem, unless $$\mathcal {P}=\mathcal {NP}$$ . This lower bound of asymptotic approximability was improved by Chlebík and Chlebíková (J Discrete Algorithms 7(3):291-305, ) to values $$1+1/3792$$ and $$1+1/2196$$ for the version with and without rotations, respectively. On the positive side there is an asymptotic 1.69.. approximation by Caprara (Math Oper Res 33:203-215, ) without rotations and an asymptotic 1.52... approximation by Bansal et al. (SIAM J Comput 39(4):1256-1278, ) for both versions. We give a new asymptotic upper bound for both versions of our problem: For any fixed $$\varepsilon $$ and any instance that fits optimally into $$\mathrm {OPT}$$ bins, our algorithm computes a packing into $$(3/2+\varepsilon )\cdot \mathrm {OPT}+69$$ bins in the version without rotations and $$(3/2+\varepsilon )\cdot \mathrm {OPT}+39$$ bins in the version with rotations. The algorithm has polynomial running time in the input length. In our new technique we consider an optimal packing of the rectangles into the bins. We cut a small vertical or horizontal strip out of each bin and move the intersecting rectangles into additional bins. This enables us to either round the widths of all wide rectangles, or the heights of all long rectangles in this bin. After this step we round the other unrounded side of these rectangles and we achieve a solution with a simple structure and only few types of rectangles. Our algorithm initially rounds the instance and computes a solution that nearly matches the modified optimal solution. [ABSTRACT FROM AUTHOR]

In the Fixed Cost k-Flow problem, we are given a graph G = ( V, E) with edge-capacities { u∣ e ∈ E} and edge-costs { c∣ e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = ( A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ⊆ A ∪ B of minimum size | S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an $O(\sqrt {k\log k})$ approximation for this problem. We also show that we can compute a solution of optimum size with Ω( k/polylog( n)) paths, where n = | A| + | B|. In the Generalized-P2P problem we are given an undirected graph G = ( V, E) with edge-costs and integer charges { b : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design []. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log n approximation scheme for it using Group Steiner Tree techniques. [ABSTRACT FROM AUTHOR]

Given a directed acyclic graph with non-negative edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem of counting the s- t paths of length at most L. This is best possible, as we also show that the problem is #P-complete. We then show that, unless P=NP, there is no finite approximation to the bi-criteria version of the problem: count the number of s- t paths of length at most L in the first criterion, and of length at most L in the second criterion. On the positive side, we extend the approximation scheme for the relaxed version of the problem, where, given thresholds L and L, we relax the requirement of the s- t paths to have length exactly at most L, and allow the paths to have length at most L : = (1+ δ) L, for any δ > 0. [ABSTRACT FROM AUTHOR]

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same factor. By applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to $$1+\phi $$ , where $$\phi $$ is the golden ratio. Since this bound remains tight for the seemingly stronger machine configuration LP, we propose a new job configuration LP that is based on an infinite continuum of fractional assignments of each job to the machines. We prove that this LP has a finite representation and can be solved in polynomial time up to any accuracy. Interestingly, we show that our problem cannot be approximated within a factor better than $$\frac{e}{e-1}\approx 1.582\, (\hbox {unless } \mathcal {P}=\mathcal {NP})$$ , which is larger than the inapproximability bound of 1.5 for the original problem. [ABSTRACT FROM AUTHOR]

We consider the capacitated $$k$$ -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) $$k$$ locations (called centers) and assign each location to an open center to minimize the maximum, over all locations, of the distance of the location to its assigned center. The number of locations assigned to a center cannot exceed the center's capacity. The uncapacitated $$k$$ -center problem has a simple tight $$2$$ -approximation from the 80's. In contrast, the first constant factor approximation for the capacitated problem was obtained only recently by Cygan, Hajiaghayi and Khuller who gave an intricate LP-rounding algorithm that achieves an approximation guarantee in the hundreds. In this paper we give a simple algorithm with a clean analysis and prove an approximation guarantee of $$9$$ . It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either $$7, 8$$ or $$9$$ . The algorithm proceeds by first reducing to special tree instances, and then uses our best-possible algorithm to solve such instances. Our concept of tree instances is versatile and applies to natural variants of the capacitated $$k$$ -center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are the same. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We focus on scheduling problems on a single machine where the objective is to minimize the total weighted completion time. In this paper, we design 2-approximation algorithms for special cases of the problem that run in polynomial time. [ABSTRACT FROM AUTHOR]

The Joint Replenishment Problem ( $${\hbox {JRP}}$$ ) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of $${\hbox {JRP-D}}$$ , the version of $${\hbox {JRP}}$$ with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of $$1.207$$ , a stronger, computer-assisted lower bound of $$1.245$$ , as well as an upper bound and approximation ratio of $$1.574$$ . The best previous upper bound and approximation ratio was $$1.667$$ ; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of $$1.5$$ , a lower bound of $$1.2$$ , and show APX-hardness. [ABSTRACT FROM AUTHOR]

The article focuses on determination of solution for subsets approximation. Topics include interpretation of approximation involved in image processing theory, analysis of several algorithms for estimation of approximation, utilization of greedy algorithms in selection of subset, validation of inequality as a result of Nikol'skii's inequality for trigonometric analysis and elimination of points from approximation after subsets selection through greedy algorithms at different functions.

We study the problem of designing truthful mechanisms for makespan minimization in scheduling. In particular, we consider randomized mechanisms for a restriction of the general multi-dimensional domain (i.e., unrelated machines). In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information. Some of the impossibility results for deterministic mechanisms carry over our setting as well. We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms. [ABSTRACT FROM AUTHOR]

In this note, we develop fast and deterministic dimensionality reduction techniques for a family of subspace approximation problems. We then utilize these dimensionality reduction techniques to help rapidly and accurately approximate the $$n$$ -widths of point sets. Let $$P \subset \mathbb {R}^N$$ be a given set of $$M$$ points. The techniques developed herein find an $$O(n \log M)$$ -dimensional subspace that is guaranteed to always contain a near-best fit $$n$$ -dimensional hyperplane $$\mathcal {H}$$ for $$P$$ with respect to the cumulative projection error $$\left( \sum _{\mathbf{x} \in P} \Vert \mathbf{x} - \Pi _{\mathcal {H}} \mathbf{x} \Vert ^p_2 \right) ^{1/p}$$ , for any chosen $$p > 2$$ . The deterministic algorithm runs in $$\tilde{O} \left( MN^2 \right) $$ -time, and can be randomized to run in only $$\tilde{O} \left( MNn \right) $$ -time while maintaining its error guarantees with high probability. In the important $$p = \infty $$ case, the dimensionality reduction techniques are then combined with efficient algorithms for computing the John ellipsoid of a data set in order to produce an $$n$$ -dimensional subspace whose maximum $$\ell _2$$ -distance to any point in the convex hull of $$P$$ is minimized. The resulting algorithm remains in $$\tilde{O} \left( MNn \right) $$ -time. [ABSTRACT FROM AUTHOR]

We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT $$4$$ -approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The main object of this paper is to propose a product approximation for the gamma function. The estimates derived here are studied via the theory of completely monotonic functions. Sharp inequalities are stated. [ABSTRACT FROM AUTHOR]

The paper presents an experimental and numerical investigation of the low-frequency motions of a simple geometry floater subjected to bichromatic waves and to long crested irregular seas. The body is axis-symmetric about the vertical axis and it is restrained from drifting away by a linear mooring system. The investigation is carried out for three water depths representing deep water, intermediate water depth and shallow water. The objective is to assess the water depth influence on the second-order low-frequency motions. A second objective is to assess the results of different approximations for the second-order difference frequency wave exciting forces on the second-order motions. The quadratic transfer functions are calculated with a boundary element method using several levels of approximation for the second-order forces: (a) the most complete approximation solves the boundary value problem completely up to the second order, (b) the first-order approximation neglects the free surface forcing in the 2nd order boundary value problem solution, (c) Newman's approximation is of zeroth-order with respect to the difference frequency, (d) a fourth method combines Newman's approximation with a contribution from the second-order incident wave potential, (e) the fifth method is applied to the heave forces only and it combines Newman's approximation corrected by an additional set down. This study shows that the contribution from the second-order velocity potential must be considered for shallow water calculations to achieve accurate results. For small difference frequencies, second-order scattering potential effects are small; therefore, in this case, a good practical approximation consists on considering the second-order potential is contributed by the incident waves only. [ABSTRACT FROM AUTHOR]

In the capacitated survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood; even in very restricted settings no known algorithm achieves a o( m) approximation, where m is the number of edges in the graph. In this paper, we obtain several new results and insights into the approximability of Cap-SNDP. We give an O(log n) approximation for a special case of Cap-SNDP where the global minimum cut is required to be at least R. (Note that this problem generalizes the min-cost λ-edge-connected subgraph problem, which is the special case of our problem when all capacities are unit.) Our result is based on a rounding of a natural cut-based LP relaxation strengthened with knapsack-cover (KC) inequalities. Our technique extends to give a similar approximation for a new network design problem that captures global minimum cut as a special case. We then show that as we move away from global connectivity, even for the single pair case (that is, when only one pair ( s, t) has positive connectivity requirement), this strengthened LP has Ω( n) integrality gap. We also consider a variant of Cap-SNDP in which multiple copies of an edge can be bought: we give an O(log k) approximation for this case, where k is the number of vertex pairs with non-zero connectivity requirement. This improves upon the previously known O(min{ k,log R})-approximation when R is large; here R is the largest requirement. On the other hand, we observe that the multiple copy version of Cap-SNDP is Ω(loglog n)-hard to approximate even for the single-source version of the problem. [ABSTRACT FROM AUTHOR]

We initiate studying the Remote Set Problem ( $${\mathsf{RSP}}$$ ) on lattices, which given a lattice asks to find a set of points containing a point which is far from the lattice. We show a polynomial-time deterministic algorithm that on rank n lattice $${\mathcal{L}}$$ outputs a set of points, at least one of which is $${\sqrt{\log n / n} \cdot \rho(\mathcal{L})}$$ -far from $${\mathcal{L}}$$ , where $${\rho(\mathcal{L})}$$ stands for the covering radius of $${\mathcal{L}}$$ (i.e., the maximum possible distance of a point in space from $${\mathcal{L}}$$ ). As an application, we show that the covering radius problem with approximation factor $${\sqrt{n / \log n}}$$ lies in the complexity class $${\mathsf{NP}}$$ , improving a result of Guruswami et al. (Comput Complex 14(2): 90-121, ) by a factor of $${\sqrt{\log n}}$$ . Our results apply to any $${\ell_p}$$ norm for $${2 \leq p \leq \infty}$$ with the same approximation factors (except a loss of $${\sqrt{\log \log n}}$$ for $${p = \infty}$$ ). In addition, we show that the output of our algorithm for $${\mathsf{RSP}}$$ contains a point whose $${\ell_2}$$ distance from $${\mathcal{L}}$$ is at least $${(\log n/n)^{1/p} \cdot \rho^{(p)}(\mathcal{L})}$$ , where $${\rho^{(p)}(\mathcal{L})}$$ is the covering radius of $${\mathcal{L}}$$ measured with respect to the $${\ell_p}$$ norm. The proof technique involves a theorem on balancing vectors due to Banaszczyk (Random Struct Algorithms 12(4):351-360, ) and the 'six standard deviations' theorem of Spencer (Trans Am Math Soc 289(2):679-706, ). [ABSTRACT FROM AUTHOR]