Search

This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k -Path Splitting Exact Cover (k-PSEC). Both problems receive a digraph G and a set P of paths in G , and their objective is to find a minimum cardinality set S of paths, whose elements are arc-disjoint and cover all arcs of G. Despite the similarities, the solutions for each problem must satisfy different properties. For k-PSEC , the set S must be obtained by splitting the paths in P in order to guarantee that no element of S has length greater than a given integer k. For PCEC , the paths in P cannot be split, and the elements of S are single arcs of G or complete paths of P. PCEC and k-PSEC have practical applications in network design and network monitoring systems, being also natural versions of graph covering problems. However, there are no theoretical studies on their complexity. This work not only presents NP-hardness results for the problems, but also proves that, unless P = NP , PCEC cannot be | P | O (1) -approximated in polynomial-time. Moreover, polynomial-time algorithms are presented for paths, cycles, and trees, and polynomial-time approximation algorithms are proposed for special cases of k-PSEC. [ABSTRACT FROM AUTHOR]

• The smallest minimum color-spanning circle (S-MCSC) problem can be solved in O (n k log ⁡ n) time. • The largest minimum color-spanning circle (L-MCSC) problem is NP-Hard. • A 1 3 -factor (1 2 , if no two distinct color disks intersect) approximation to the L-MCSC problem can be computed in O (n k log ⁡ n) time. Let R be a set of n colored imprecise points, where each point is colored by one of k colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an O (n k log ⁡ n) time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP - Hard and present a 1 3 -factor approximation algorithm. We improve the approximation factor to 1 2 for the case where no two disks of distinct color intersect. [ABSTRACT FROM AUTHOR]

• The first TotP-complete problems under parsimonious reductions. • Hardness of approximation for these problems and some of their generalizations. • A family of hard-to-approximate instances for the complete problem Size-of-Subtree. • Exponential time hardness results for Size-of-Subtree under variants of the Exponential Time Hypothesis. • Approximation preserving reduction of the general #SAT to instances of it that are promised to be self-reducible with easy decision. Hard counting problems with easy decision version, like computing the permanent and counting independent sets, are of particular importance in counting complexity theory. TotP is the class of all self-reducible problems in # P with decision version in P. It has been a long standing open question to determine TotP -complete problems under strong reductions that preserve exactly the values of the functions (Karp), since Cook reductions blur structural differences between counting classes, specifically under Cook reductions TotP -complete problems are also # P -complete. In this paper we present the first such problems and we show some implications of these results to counting complexity. The problems that we prove to be TotP -complete under Karp reductions are: (a) #Tree-Monotone-Circuit-SAT , which further implies that it is hard to compute, both exactly and approximately, the number of satisfying assignments of monotone circuits, where the monotonicity is defined by a partial order which is given as part of the input. (b) Max-Lower-Set-Size , which implies that given a poset it is hard to compute and approximate the size of a principal upper set, and the size of the maximum lower set all elements of which share a given property P. (c) Size-of-Subtree , which directly implies that every problem in TotP admits a polynomial-time approximation algorithm the error of which depends on the amount of imbalance of the respective self-reducibility tree of the problem. We settle the worst case complexity of this problem, we provide a family of instances that are hard to approximate, and we show exponential time hardness results under variants of the exponential time hypothesis (ETH). (d) #Clustered-Monotone-SAT , which implies that approximating #SAT remains hard even on instances for which some kind of navigation among solutions is possible. Thus we narrow down any further research regarding the polynomial-time approximability of #SAT to instances with the aforementioned property. Among other implications, our results show that all these problems do not admit an FPRAS, unless NP = RP , something that we would not be able to conclude by showing them to be TotP -complete under Cook reductions.1 [ABSTRACT FROM AUTHOR]

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant , which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: • Computing ∑ S det ⁡ (A S , S) p exactly for every (fixed) positive even integer p is UP -hard and Mod 3 P -hard, which gives a negative answer to an open question posed by Kulesza and Taskar [51]. • ∑ S det ⁡ (A S , S) det ⁡ (B S , S) det ⁡ (C S , S) is NP -hard to approximate within a factor of 2 O (| I | 1 − ε) or 2 O (n 1 / ε) for any ε > 0 , where | I | is the input size and n is the order of the input matrix. This result is stronger than the # P -hardness for the case of two matrices derived by Gillenwater [36]. • There exists a k O (k) n O (1) -time algorithm for computing ∑ S det ⁡ (A S , S) det ⁡ (B S , S) , where k is the maximum rank of A and B or the treewidth of the graph formed by nonzero entries of A and B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix A of treewidth w : • We can compute a 2 n 2 p − 1 -approximation to ∑ S det ⁡ (A S , S) p for any fractional number p > 1 in w O (w p) n O (1) time. • We can find a 2 n -approximation to unconstrained maximum a posteriori inference in w O (w n) n O (1) time. [ABSTRACT FROM AUTHOR]

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into pairwise disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset, we must select all the points from that subset. We consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. On the contrary, if each subset contains at most t points, where t ≥ 2 , and the intervals are overlapping, we show that the problem becomes NP - Hard. Further, when each subset contains at most t points where t ≥ 3 , and the intervals are disjoint, we prove that the problem is NP - Hard , and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then we prove that the problem is in FPT when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. [ABSTRACT FROM AUTHOR]

• We study a k-wise generalization of the Kemeny rule. • We study the properties of this distance, and of the induced aggregation rule. • We introduce a k-wise counterpart of the majority graph. • We provide computational complexity results for the aggregation problem. • A polytime 2-approximation algorithm is provided for the aggregation problem. In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k -wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k -wise Kemeny aggregation problem, we introduce a k -wise counterpart of the majority graph. This graph reveals useful to divide the aggregation problem into several sub-problems, which enables to speed up the exact computation of a consensus ranking. By introducing a k -wise counterpart of the Spearman distance, we also provide a 2-approximation algorithm for the k -wise Kemeny aggregation problem. We conclude with numerical tests. [ABSTRACT FROM AUTHOR]

• The approximability and the computational complexity of the Maximum Happy Set problem (MaxHS) are studied. • A (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ is presented. • The approximation ratio is improved to Δ if the maximum degree Δ is a constant. • The polynomial-time solvability of MaxHS on block/interval graphs is proved. • The NP-hardness of MaxHS on bipartite/cubic graphs is proved. In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard. [ABSTRACT FROM AUTHOR]

We consider scheduling on identical and unrelated parallel machines with job assignment restrictions. These problems are NP-hard and they do not admit polynomial time approximation algorithms with approximation ratios smaller than 1.5 unless P=NP. However, if we impose limitations on the set of machines that can process a job, the problem sometimes becomes easier in the sense that algorithms with approximation ratios better than 1.5 exist. We introduce a graph framework based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of the resulting graphs, in particular, their tree- and cliquewidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms generalizing and extending previous results in this area. [ABSTRACT FROM AUTHOR]

Given a set B of d -dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP -hard, but as for many similar NP -hard problems (e.g., Box Cover , and Orthogonal Polygon Covering), the problem becomes solvable in polynomial time under restrictions on B. We show that computing minimum coverage kernels remains NP -hard even when restricting the graph induced by the input to a highly constrained class of graphs. Alternatively, we present two polynomial-time approximation algorithms for this problem: one deterministic with an approximation ratio within O (log ⁡ n) , and one randomized with an improved approximation ratio within O (lg ⁡ OPT) (with high probability). [ABSTRACT FROM AUTHOR]

A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to schedule than flow-shops and open-shops, and have been studied since the 1980's. We consider the three machine proportionate mixed shop problem denoted as M 3 | p r p t | C max , in which by "proportionate" each job has equal processing times on all three machines. Koulamas and Kyparisis (2015) [6] showed that the problem is solvable in polynomial time in some very special cases; for the non-solvable case, they proposed a 5/3-approximation algorithm. In this paper, we first present an improved 4/3-approximation algorithm and show that this ratio of 4/3 is asymptotically tight; when the largest job is a flow-shop job, we then present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the F 3 | p r p t | C max problem is polynomial-time solvable, we show an interesting hardness result that adding one open-shop job to the job set makes the problem NP-hard if this open-shop job is larger than any flow-shop job. We are able to design an FPTAS for this special case too. [ABSTRACT FROM AUTHOR]

Inspired by scaffold filling, a recent approach for genome reconstruction from incomplete data, we consider a variant of the well-known longest common subsequence problem for the comparison of two sequences. The new problem, called Longest Filled Common Subsequence, aims to compare a complete sequence with an incomplete one, i.e. with some missing elements. Longest Filled Common Subsequence (LFCS), given a complete sequence A , an incomplete sequence B , and a multiset M of symbols missing in B , asks for a sequence B ⁎ obtained by inserting the symbols of M into B so that B ⁎ induces a common subsequence with A of maximum length. We investigate the computational and approximation complexity of the problem and we show that it is NP-hard and APX-hard when A contains at most two occurrences of each symbol, and we give a polynomial time algorithm when the input sequences are over a constant-size alphabet. We give a 3 5 − approximation algorithm for the Longest Filled Common Subsequence problem. Finally, we present a fixed-parameter algorithm for the problem, when it is parameterized by the number of symbols inserted in B that "match" symbols of A. [ABSTRACT FROM AUTHOR]

A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP -hardness, parameterized complexity, positive and negative approximation results. • An extension variant of the weighted edge cover problem is studied. • The problem is NP -complete in complete graphs while polynomial solvable in bounded tree-width graphs. • For non-negative weights, the minimization version is in-approximable at all while the maximization version is in RAPX. • If weight function satisfies (extended) c -relaxed triangle inequalities, the minimization version is in RAPX. [ABSTRACT FROM AUTHOR]

Abstract We present a (1 + 3 + ϵ) -approximation algorithm for the k -median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k -median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem. [ABSTRACT FROM AUTHOR]

In the Canadian traveler problem, we are given an edge weighted graph with two specified vertices s and t and a probability distribution over the edges that tells which edges are present. The goal is to minimize the expected length of a walk from s to t . However, we only get to know whether an edge is active the moment we visit one of its incident vertices. Under the assumption that the edges are active independently, we show NP-hardness on series-parallel graphs and give results on the adaptivity gap. We further show that this problem is NP-hard on disjoint-path graphs and cactus graphs when the distribution is given by a list of scenarios. We also consider a special case called the multi-target graph search problem. In this problem, we are given a probability distribution over subsets of vertices. The distribution specifies which set of vertices has targets. The goal is to minimize the expected length of the walk until finding a target. For the independent decision model, we show that the problem is NP-hard on trees and give a ( 3.59 + ϵ ) -approximation for trees and a ( 14.4 + ϵ ) -approximation for general metrics. For the scenario model, we show NP-hardness on star graphs. [ABSTRACT FROM AUTHOR]

Latin Hypercube Designs (LHDs) are crucial in the meta-modeling field. An LHD with maximal minimum distance between any pair of points guarantees a high quality of the model. We introduce a generalization of the Maximin LHD construction, the Maximin LHD completion, in which some points of the design are already fixed. We study the complexity of this problem and prove that it is NP-complete and it does not admit any approximation algorithm in most practical cases. [ABSTRACT FROM AUTHOR]

Comparative genomics is a line of study which aims at determining dis/similarities between genomes. One way of doing this is to infer the large scale mutations (also called genome rearrangements ) that are responsible for transforming one genome into another, under the parsimony principle. Numerous efforts have been made over the past years regarding the traditional approach, in which all genome rearrangements have the same unit cost . However, since long rearrangements are more likely to disturb the organism, some works considered the length-weighted approach, in which the cost of each rearrangement is a function of its length. The problem is thus modeled as follows: given two genomes G 1 and G 2 and a set β of allowed genome rearrangements, each with a given cost, determine their distance , i.e., the total cost of a minimum-cost sequence of rearrangements from β that transforms G 1 into G 2 . In this paper, we study length-weighted reversals and transpositions, mainly considering their prefix variants (in which the leftmost part of the genome must always be included). We present approximation algorithms and bounds on the distances and diameters (i.e., maximum possible distance over any two genomes of same length) for eight problems when genomes are represented as permutations, and another eight problems when genomes are represented as binary strings, in each case considering two different cost functions. [ABSTRACT FROM AUTHOR]

We present a general technique for approximating bicriteria minimization problems with positive-valued, polynomially computable objective functions. Given 0 < ϵ ≤ 1 and a polynomial-time α -approximation algorithm for the corresponding weighted sum problem, we show how to obtain a bicriteria ( α ⋅ ( 1 + 2 ϵ ) , α ⋅ ( 1 + 2 ϵ ) ) -approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in 1 ϵ . Moreover, we show that our method can be extended to compute an ( α ⋅ ( 1 + 2 ϵ ) , α ⋅ ( 1 + 2 ϵ ) ) -approximate Pareto curve under the same assumptions. Our technique applies to many minimization problems to which most previous algorithms for computing approximate Pareto curves cannot be applied because the corresponding gap problem is NP -hard to solve. For maximization problems, however, we show that approximation results similar to the ones presented here for minimization problems are impossible to obtain in polynomial time unless P = NP . [ABSTRACT FROM AUTHOR]

In this paper we study parallel-machine scheduling with job rejection, where the total processing time of the rejected jobs is required to be no greater than a predefined bound. The objective is to minimize the makespan of the accepted jobs plus the total penalty cost of the rejected jobs. The scheduling problem is NP-hard in the strong sense. We present a 2-approximation algorithm with a time complexity of O ( n log ⁡ n ) by making use of specific data structure. We also develop a polynomial time approximation scheme (PTAS). Due to the job rejection restriction, some techniques for knapsack problems are applied in the development of our PTAS. [ABSTRACT FROM AUTHOR]

A graph G is weakly semiregular if there are two numbers a , b , such that the degree of every vertex is a or b . The weakly semiregular number of a graph G , denoted by w r ( G ) , is the minimum number of subsets into which the edge set of G can be partitioned so that the subgraph induced by each subset is a weakly semiregular graph. We present a polynomial time algorithm to determine whether the weakly semiregular number of a given tree is two. On the other hand, we show that determining whether w r ( G ) = 2 for a given bipartite graph G with at most three numbers in its degree set is NP -complete. Among other results, for every tree T , we show that w r ( T ) ≤ 2 log 2 ⁡ Δ ( T ) + O ( 1 ) , where Δ ( T ) denotes the maximum degree of T . A graph G is a [ d , d + s ] -graph if the degree of every vertex of G lies in the interval [ d , d + s ] . A [ d , d + 1 ] -graph is said to be semiregular . The semiregular number of a graph G , denoted by s r ( G ) , is the minimum number of subsets into which the edge set of G can be partitioned so that the subgraph induced by each subset is a semiregular graph. We prove that the semiregular number of a tree T is ⌈ Δ ( T ) 2 ⌉ . On the other hand, we show that determining whether s r ( G ) = 2 for a given bipartite graph G with Δ ( G ) ≤ 6 is NP -complete. In the second part of the work, we consider the representation number. A graph G has a representation modulo r if there exists an injective map ℓ : V ( G ) → Z r such that vertices v and u are adjacent if and only if | ℓ ( u ) − ℓ ( v ) | is relatively prime to r . The representation number , denoted by r e p ( G ) , is the smallest r such that G has a representation modulo r . Narayan and Urick conjectured that the determination of r e p ( G ) for an arbitrary graph G is a difficult problem [38] . In this work, we confirm this conjecture and show that if N P ≠ P , then for any ϵ > 0 , there is no polynomial time ( 1 − ϵ ) n 2 -approximation algorithm for the computation of representation number of regular graphs with n vertices. [ABSTRACT FROM AUTHOR]

Given a graph with labels defined on edges and a source-sink pair ( s , t ) , the Label s - t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t . Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l max , the maximum length of any s - t path (only applies to Label s - t Cut ), and f max , the maximum number of appearances of any label in the graph (applies to the two problems). We show that l max = 2 and f max = 2 are two complexity thresholds for Label s - t Cut . Furthermore, we give (i) an O ⁎ ( c k ) time parameterized algorithm for Label s - t Cut with l max bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l max − 1 < c < l max , (ii) a combinatorial l max -approximation algorithm for Label s - t Cut , and (iii) a polynomial time exact algorithm for Global Label Cut with f max bounded from above. [ABSTRACT FROM AUTHOR]

Parameterized Approximation is a topic of considerable interest in the field of Parameterized Complexity. In the past decade, new color coding-related techniques, including the breakthrough representative sets technique, have been proven extremely powerful in the design of fast parameterized algorithms. Furthermore, packing problems, which are often solved via color coding-related techniques, have enjoyed a race towards obtaining the fastest parameterized algorithms that solve them. Therefore, it is natural to ask whether packing problems admit efficient parameterized approximation algorithms. In this paper, we answer this question affirmatively. We present tradeoffs that improve the running times of algorithms for well-known special cases of the 3 -Set k -Packing problem at the cost of their accuracy. Consider a packing problem for which there is no known algorithm with approximation ratio α , and a parameter k . If the value of an optimal solution is at least k , we seek a solution of value at least αk ; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value t runs in time O ⁎ ( f ( t ) ) for some function f , we are interested in running times better than O ⁎ ( f ( α k ) ) . Our main contribution lies in the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: We introduce the definition of “approximate lopsided universal sets”, combine partial executions of representative sets-based algorithms with approximation algorithms, and adapt the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Our ideas are intuitive, and may be relevant to the design of other parameterized approximation algorithms. [ABSTRACT FROM AUTHOR]

Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T − e containing the vertex sought for, while incurring some known cost c ( e ) . The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case. Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O ( log ⁡ n / log ⁡ log ⁡ log ⁡ n ) -approximation algorithm of Cicalese et al. (2012) [4] . We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O ( log ⁡ n log ⁡ log ⁡ n ) -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has degree larger than 2. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the problem of the representation of simplicial complexes by trees. We introduce and analyze local and global tree representations. We prove that the global tree representation is more efficient in terms of time complexity for searching a given simplex and we show that the local tree representation is more efficient in terms of size of the structure. The simplicial complexes are modeled by hypergraphs. We then prove that the associated combinatorial optimization problems are very difficult to solve and to approximate even if the set of maximal simplices induces a planar graph of maximum degree at most three or a bounded degree hypergraph. However, we prove polynomial time algorithms that compute constant factor approximations and optimal solutions for some classes of instances. [ABSTRACT FROM AUTHOR]

We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP -complete, even in planar bipartite graphs. Moreover, we show that there is no subexponential-time algorithm for several related problems unless the Exponential-Time Hypothesis fails. Lastly, we also design two polynomial-time approximation algorithms for complete graphs. [ABSTRACT FROM AUTHOR]

We study the Stackelberg/bilevel knapsack problem as proposed by Chen and Zhang [1] : Consider two agents, a leader and a follower. Each has his own knapsack. (Knapsack capacities are possibly different.) As usual, there is a set of items i = 1 , … , n of given weights w i and profits p i . It is allowed to pack item i into both knapsacks, but in this case the corresponding profit for each player becomes p i + a i , where a i is a given (positive or negative) number. The objective is to find a packing for the leader such that the total profit of the two knapsacks is maximized, assuming that the follower acts selfishly. We present tight approximation algorithms for all settings considered in [1] . [ABSTRACT FROM AUTHOR]

We study the computational complexity of the puzzle Quell. The goal is to collect pearls by sliding a droplet of water over them in a map that is a two-dimensional grid. Each cell of the grid is either a free space (possibly with a pearl in it) or an obstacle. In each move, the droplet slides in one of the four directions to the maximal extent, through the free spaces of the map and collecting all pearls along the way, until it is stopped by an obstacle. We show that any-Moves-all-Pearls (deciding whether it is possible to collect all the pearls using any number of moves) can be solved in polynomial time. In contrast, both any-Moves-max-Pearls (finding the maximum number of pearls that can be collected using any number of moves) and min-Moves-all-Pearls (finding the minimum number of moves required to collect all the pearls) are APX-hard, although the corresponding decision problems are in FPT. We also present a simple 2-approximation for any-Moves-max-Pearls , and leave open the question whether min-Moves-all-Pearls admits a polynomial-time constant approximation. [ABSTRACT FROM AUTHOR]

In Constrained Fault-Tolerant Resource Allocation ( FTRA ) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R i facilities with opening cost f i . Each client j requires an allocation of r j open facilities and connecting j to any facility at site i incurs a connection cost c i j . The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation ( FTRA ∞ ) [1] and the classical Fault-Tolerant Facility Location ( FTFL ) [2] problems: for every site i , FTRA ∞ does not have the constraint R i , whereas FTFL sets R i = 1 . These problems are said to be uniform if all r j 's are the same, and general otherwise. For the general metric FTRA , we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL , implying the ratio of 1.7245 from [3] . For the uniform FTRA , we provide a 1.52-approximation primal–dual algorithm in O ( n 4 ) time, where n is the total number of sites and clients. [ABSTRACT FROM AUTHOR]

Algorithms for answering XPath queries on Xml streams have been studied intensively in the last decade. Nevertheless, there still exists no solution with high efficiency and large coverage. In this paper, we introduce early nested word automata in order to approximate earliest query answering algorithms for nested word automata. Our early query answering algorithm is based on stack-and-state sharing for running early nested word automata on all answer candidates with on-the-fly determinization. We prove tight upper complexity bounds on time and space consumption. We have implemented our algorithm in the QuiXPath system and show that it outperforms all previous tools in coverage on the XPathMark benchmark, while obtaining very high time and space efficiency and scaling to huge Xml streams. Furthermore, it turns out that our early query answering algorithm is earliest in practice on most queries from the XPathMark benchmark. 1 1 Thanks to the QuiXProc project of Inria and Innovimax and the Cnrs Sosp project. [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing K distinct cost scenarios. The Ordered Weighted Averaging (OWA for short) aggregation operator is applied to choose a solution. Some well known criteria used in decision making under uncertainty such as the maximum, minimum, average, Hurwicz and median are special cases of OWA. Furthermore, by using OWA, the traditional robust (min–max) approach to combinatorial optimization problems with uncertain costs can be generalized. The computational complexity and approximability of the problem of minimizing OWA for the considered class of problems are investigated and some new positive and negative results in this area are provided. These results remain valid for many basic problems, such as network or resource allocation problems. [ABSTRACT FROM AUTHOR]

We consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which each agent tries to select a machine for processing that optimizes its own payoff while ignoring the others. We formalize this situation as a game in which the players are job owners, the strategies are machines, and a player's utility is inversely proportional to the total completion time of the machine selected by the agent. The price of anarchy is the ratio between the worst-case equilibrium makespan and the optimal makespan. In this paper, we design a game theoretic approximation algorithm A and prove that it converges to a pure-strategy Nash equilibrium in a linear number of rounds. We also derive the upper bound on the price of anarchy of A and further show that the ratio obtained by A is tight. Finally, we analyze the time complexity of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the selective graph coloring problem. Given an integer and a graph with a partition of V, it consists in deciding whether there exists a set in G such that for all , and such that the graph induced by is k-colorable. We investigate the complexity status of this problem in various classes of graphs. [Copyright &y& Elsevier]

Abstract: The reload cost concept refers to the cost that occurs at a vertex along a path on an edge-colored graph when it traverses an internal vertex between two edges of different colors. This cost depends only on the colors of the traversed edges. Reload costs arise in various applications such as transportation networks, energy distribution networks, and telecommunications. Previous work on reload costs focuses on two problems of finding a spanning tree with minimum cost with respect to two different cost measures. In both problems the cost is associated with a set of paths from a given vertex r to all the leaves of the constructed tree. The first cost measure is the sum of the reload costs of all paths from r to the leaves. The second cost measure is the changeover cost, in which the cost of traversing a vertex by using two specific incident edges is paid only once regardless of the number of paths traversing it. The first problem is inapproximable within any polynomial time computable function of the input size [1], and the second problem is inapproximable within for any [2]. In this paper we show that the first hardness result holds also for the second problem. Given this strong inapproximability result, we study the complexity and approximability properties of numerous special cases of this second problem. We mainly focus on bounded costs, and consider both directed and undirected graphs, bounded and unbounded number of colors, and both bounded and unbounded degree graphs. We also present polynomial time exact algorithms and an approximation algorithm for some special case. To the best of our knowledge, these are the first algorithms with a provable performance guarantee for the problem. Moreover, our approximation algorithm shows a tight bound on the approximability of the problem for a specific family of instances. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the complexity and algorithms of the injective coloring problem. We prove that it is NP-complete to determine the injective chromatic number even restricted to some special bipartite graphs. Furthermore, we show that for every , it is impossible to efficiently approximate the injective chromatic number of any bipartite graph within a factor of unless ZPP=NP. For the max-injective coloring problem, we prove that there is a constant approximation algorithm on power chordal graphs with bounded injective chromatic number. We also devise a constant approximation algorithm for max-injective coloring some bipartite graphs. For the on-line injective coloring problem, we prove that First Fit (FF) injectively colors -free graphs perfectly, where First Fit is an on-line algorithm that simply assigns the smallest available color to each vertex. We also prove that the number of colors used by for bipartite graph is bounded by times the on-line injective chromatic number, where FF is an on-line algorithm equivalent to FF proper coloring the complement of . Moreover, we present an improved algorithm BFF, and prove that it is optimal for on-line injectively coloring bipartite graphs. [Copyright &y& Elsevier]

Abstract: In the highway problem, we are given a path, and a set of buyers interested in buying sub-paths of this path; each buyer declares a non-negative budget, which is the maximum amount of money she is willing to pay for that sub-path. The problem is to assign non-negative prices to the edges of the path such that we maximize the profit obtained by selling the edges to the buyers who can afford to buy their sub-paths, where a buyer can afford to buy her sub-path if the sum of prices in the sub-path is at most her budget. In this paper, we show that the highway problem is strongly NP-hard; this settles the complexity of the problem in view of the existence of a polynomial-time approximation scheme, as was recently shown in Grandoni and Rothvoß (2011) [15]. We also consider the coupon model, where we allow some items to be priced below zero to improve the overall profit. We show that allowing negative prices makes the problem APX-hard. As a corollary, we show that the bipartite vertex pricing problem is APX-hard with budgets in , both in the cases with negative and non-negative prices. [Copyright &y& Elsevier]

Abstract: Video-on-Demand (VoD) services require frequent updates in file configuration on the storage subsystem, so as to keep up with the frequent changes in movie popularity. This defines a natural reconfiguration problem in which the goal is to minimize the cost of moving from one file configuration to another. The cost is incurred by file replications performed throughout the transition. The problem shows up also in production planning, preemptive scheduling with set-up costs, and dynamic placement of Web applications. We show that the reconfiguration problem is NP-hard already on very restricted instances. We then develop algorithms which achieve the optimal cost by using servers whose load capacities are increased by , in particular, by factor for any small when the number of servers is fixed, and by factor of for arbitrary number of servers, for some . To the best of our knowledge, this particular variant of the data migration problem is studied here for the first time. [Copyright &y& Elsevier]

Abstract: Suppose is a simple graph and is a fixed positive integer. A subset is a distance -dominating set of if for every , there exists a vertex such that , where is the distance between and in . A set is a distance -paired-dominating set of if is a distance -dominating set and the induced subgraph contains a perfect matching. Given a graph and a fixed integer , the Min Distance -Paired-Dom Set problem is to find a minimum cardinality distance -paired-dominating set of . In this paper, we show that the decision version of Min Distance -Paired-Dom Set is NP-complete for undirected path graphs. This strengthens the complexity of decision version of Min Distance -Paired-Dom Set problem in chordal graphs. We show that for a given graph , unless NP DTIME , Min Distance -Paired-Dom Set problem cannot be approximated within a factor of for any , where is the number of vertices in . We also show that Min Distance -Paired-Dom Set problem is APX-complete for graphs with degree bounded by . On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance -paired-dominating set of a strongly chordal graph if a strong elimination ordering of is provided. We show that for a given graph , Min Distance -Paired-Dom Set problem can be approximated with an approximation factor of , where denotes the maximum degree of . [Copyright &y& Elsevier]

Abstract: We determine the computational complexity of approximately counting the total weight of variable assignments for every complex-weighted Boolean constraint satisfaction problem (or CSP) with any number of additional unary (i.e., arity ) constraints, particularly, when degrees of input instances are bounded from above by a fixed constant. All degree- counting CSPs are obviously solvable in polynomial time. When the instance’s degree is more than two, we present a dichotomy theorem that classifies all counting CSPs admitting free unary constraints into exactly two categories. This classification theorem extends, to complex-weighted problems, an earlier result on the approximation complexity of unweighted counting Boolean CSPs of bounded degree. The framework of the proof of our theorem is based on a theory of signature developed from Valiant’s holographic algorithms that can efficiently solve seemingly intractable counting CSPs. Despite the use of arbitrary complex weight, our proof of the classification theorem is rather elementary and intuitive due to an extensive use of a novel notion of limited T-constructibility. For the remaining degree- problems, in contrast, they are as hard to approximate as Holant problems, which are a generalization of counting CSPs. [Copyright &y& Elsevier]

Abstract: We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere -dense and average -dense graphs. More precisely, we consider the computational complexity of approximating a generalization of the Minimum Edge Dominating Set problem, the so called Minimum Subset Edge Dominating Set problem. As a direct result, we obtain for the special case of the Minimum Edge Dominating Set problem in everywhere -dense and average -dense graphs by using the techniques of Karpinski and Zelikovsky, the approximation ratios of and of , respectively. On the other hand, we give new approximation lower bounds for the Minimum Edge Dominating Set problem in dense graphs. Assuming the Unique Game Conjecture, we show that it is NP-hard to approximate the Minimum Edge Dominating Set problem in everywhere -dense graphs with a ratio better than with and with in average -dense graphs. [Copyright &y& Elsevier]

Abstract: We study the problem of minimizing the weighted average number of queries to identify an initially unknown object in a poset. We show that for general posets, there cannot be any -approximation algorithm unless . When the Hasse diagram of the partially ordered set has the structure of a tree, the problem is equivalent to the following tree search problem: in a given rooted tree a node has been marked and we want to identify it. In order to locate the marked node, we can perform node queries. A node query asks whether the marked node lies in the subtree rooted at . A function is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper the complexity of this problem had remained open. We prove that the above tree search problem is -complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 we show that the problem is polynomially solvable using a dynamic programming approach. In addition we prove that the problem is -complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in time for trees with degree at most 2 (paths). Our results sharply contrast with those for the variant of the problem where one is interested in minimizing the maximum number of queries. In fact, for the worst case scenario, linear time algorithms are known for finding an optimal search strategy [K. Onak, P. Parys, Generalization of binary search: searching in trees and forest-like partial orders, in: FOCS’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 2006, pp. 379–388; S. Mozes, K. Onak, O. Weimann, Finding an optimal tree searching strategy in linear time, in: SODA’08: Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008, pp. 1096–1105]. [Copyright &y& Elsevier]

Abstract: Given an undirected graph on vertices with weights on its edges, Min WCF () consists of computing a covering forest of minimum weight such that each of its tree components contains at least vertices. It has been proved that Min WCF () is NP-hard for any (Imielinska et al. (1993) ) but -approximable (Goemans and Williamson (1995) ). While Min WCF(2) is polynomial-time solvable, already the unweighted version of Min WCF(3) is NP-hard even on planar bipartite graphs of maximum degree 3. We prove here that for any , the unweighted version is NP-hard, even for planar bipartite graphs of maximum degree 3; moreover, the unweighted version for any has no ptas for bipartite graphs of maximum degree 3. The latter theorem is the first-ever APX-hardness result on this problem. On the other hand, we show that Min WCF () is polynomial-time solvable on graphs with bounded treewidth, and for any bounded by it has a ptas on planar graphs. [Copyright &y& Elsevier]

Abstract: We are given base elements and a finite collection of subsets of them. The size of any subset varies between to (). In addition, we assume that the input contains all possible subsets of size . Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of . The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering new elements, starting from down to . At a final step we cover the remaining base elements by the subsets of size . We derive the exact performance guarantee of this algorithm for all values of and , which is less than , where is the ’th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted -set cover problem (in which subset sizes are only restricted not to exceed ), and hence it serves as a benchmark for our improved algorithm. The improved algorithm for the special case of is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of , and the local search algorithm achieves a better ratio, which is bounded by . [Copyright &y& Elsevier]

Abstract: Given a graph in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum number of steps to capture the fugitive. We introduce the fast edge searching problem in the edge search model, which is the problem of finding the minimum number of steps (called the fast edge-search time) to capture the fugitive. We establish relations between the fast edge searching and the fast searching that is the problem of finding the minimum number of searchers to capture the fugitive in the fast search model. While the family of graphs whose fast search number is at most is not minor-closed for any positive integer , we show that the family of graphs whose fast edge-search time is at most is minor-closed. We establish relations between the fast (fast edge) searching and the node searching. These relations allow us to transform the problem of computing node search numbers to the problem of computing fast edge-search numbers or fast search numbers. Using these relations, we prove that the problem of deciding, given a graph and an integer , whether the fast (edge-)search number of is less than or equal to is NP-complete; and it remains NP-complete for Eulerian graphs. We also prove that the problem of determining whether the fast (edge-)search number of is half of the number of odd vertices in is NP-complete; and it remains NP-complete for planar graphs with maximum degree 4. We present a linear time approximation algorithm for the fast edge-search time that always delivers solutions of at most times the optimal value. This algorithm also gives us a tight upper bound on the fast search number of graphs. We also show a lower bound on the fast search number using the minimum degree and the number of odd vertices. [Copyright &y& Elsevier]

Abstract: A -spanner of a graph is its spanning subgraph such that the distance between every pair of vertices in is at most times their distance in . The sparsest -spanner problem asks to find, for a given graph and an integer , a -spanner of with the minimum number of edges. The problem is known to be NP-hard for all , and, even more, it is NP-hard to approximate it with ratio for every . For , the problem remains NP-hard for planar graphs and the approximability status of the problem on planar graphs was open. We resolve this open issue by showing that the sparsest -spanner problem admits the efficient polynomial time approximation scheme (EPTAS) for every . Our result holds for a much wider class of graphs, namely, the class of apex-minor-free graphs, which contains the classes of planar and bounded genus graphs. Moreover, it is possible to extend our results to weighted apex-minor free graphs, when the maximum edge weight is bounded by some constant. [ABSTRACT FROM AUTHOR]

Abstract: The max-edge-coloring problem is a natural weighted generalization of the classical edge-coloring problem arising in the domain of communication systems. In this problem each color class is assigned the weight of the heaviest edge in this class and the objective is to find a proper edge-coloring of the input graph minimizing the sum of all color classes’ weights. We present new approximation results, that improve substantially the known ones, for several variants of the problem with respect to the class of the underlying graph. In particular, we deal with variants which are known to be NP-hard (general and bipartite graphs) or are proven to be NP-hard in this paper (complete graphs with bi-valued edge weights) or whose complexity question still remains open (trees). [Copyright &y& Elsevier]

Abstract: It is well known that the two simple algorithms for the classic bin packing problem, and both have an approximation ratio of . However, seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used. Using resource augmented analysis, where the output of an approximation algorithm, which can use bins of size , is compared to an optimal packing into bins of size , we give a complete analysis of the asymptotic approximation ratio of and of , and use it to show that is strictly better than for any , while they have the same asymptotic performance guarantee for all , and for . [Copyright &y& Elsevier]

Abstract: We consider a single machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time and the machine is subject to an availability constraint. We consider the non-resumable case. The objectives are to minimize the makespan and the total completion time. We show that both problems are NP-hard and present pseudo-polynomial time optimal algorithms to solve them. Furthermore, for the makespan problem, we present an optimal approximation algorithm for the on-line case, and a fully polynomial time approximation scheme for the off-line case. For the total completion time problem, we provide a heuristic and evaluate its efficiency by computational experiments. [Copyright &y& Elsevier]

Abstract: We consider the problem of finding a schedule for n-independent identical malleable tasks on p identical processors with minimal completion time. This problem arises while using the branch-and-bound or the divide-and-conquer strategy to solve a problem on a parallel system. If nothing is known about the subproblems, then they are assumed to be identical. We assume that the execution time decreases with the number of processors while the computational work increases. We give an algorithm with execution time exponential in p which computes an optimal schedule. In order to approximate an optimal schedule, we use the concept of phase-by-phase schedules. Here schedules consist of phases in which every job uses the same number of processors. We prove that one can approximate an optimal schedule up to a factor of using constant time, and we show that this is optimal. Furthermore, we give an -approximation algorithm if the speed-up is optimal up to a constant factor. [Copyright &y& Elsevier]

In this paper we consider a new optimization problem, called MAX HAMMINGDISTANCE(F) where F is a family of Boolean constraints. This problem consists in finding two satisfying assignments that differ in the maximum number of variable values: in other words, the problem looks for the maximum difference between two models of the constraints given in input. We give a complete classification of the approximability properties of MAX HAMMINGDISTANCE(F) by using a specialization of the criteria introduced by Schaefer in order to classify constraint satisfaction problems and subsequently used by Khanna, Sudan, Trevisan, and Williamson to classify constraint satisfaction optimization problems. [Copyright &y& Elsevier]