Approximability of the Firefighter Problem

We provide approximation algorithms for several variants of the Firefighter problem on general graphs. The Firefighter problem models the case where a diffusive process such as an infection (or an idea, a computer virus, a fire) is spreading through a network, and our goal is to contain this infection by using targeted vaccinations. Specifically, we are allowed to vaccinate at most a fixed number (called the budget) of nodes per time step, with the goal of minimizing the effect of the infection. The difficulty of this problem comes from its temporal component, since we must choose nodes to vaccinate at every time step while the infection is spreading through the network, leading to notions of “cuts over time”. We consider two versions of the Firefighter problem: a “non-spreading” model, where vaccinating a node means only that this node cannot be infected; and a “spreading” model where the vaccination itself is an infectious process, such as in the case where the infection is a harmful idea, and the vaccine to it is another infectious beneficial idea. We look at two measures: the MaxSave measure in which we want to maximize the number of nodes which are not infected given a fixed budget, and the MinBudget measure, in which we are given a set of nodes which we have to save and the goal is to minimize the budget. We study the approximability of these problems in both models.     

Approximability of Minimum AND-Circuits

Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not polynomial-time approximable within a factor of less than 1.0051 unless \(\mathsf{P}=\mathsf{NP}\), even if the monomials are restricted to be of degree at most three. For the latter case, we devise several efficient approximation algorithms, yielding an approximation ratio of 1.278. For the general problem, we achieve an approximation ratio of d?3/2, where d is the degree of the largest monomial. In addition, we prove that the problem is fixed parameter tractable with the number of monomials as parameter. Finally, we discuss generalizations of the Minimum AND-Circuit problem and relations to addition chains and grammar-based compression.     

Approximability of Clausal Constraints

We study a family of problems, called Maximum Solution (Max Sol), where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e. restricted to {0,1}), the maximum solution problem is identical to the well-studied Max Ones problem, and the complexity and approximability is completely understood for all restrictions on the underlying constraints. We continue this line of research by considering the Max Sol problem for relations defined by regular signed logic over finite subsets of the natural numbers; the complexity of the corresponding decision problem has recently been classified by Creignou et al. (Theory Comput. Syst. 42(2):239–255, 2008). We give sufficient conditions for when such problems are polynomial-time solvable and we prove that they are APX-hard otherwise. Similar dichotomies are also obtained for variants of the Max Sol problem.     

Approximability of identifying codes and locating-dominating codes

We study the approximability and inapproximability of finding identifying codes and locating-dominating codes of the minimum size. In general graphs, we show that it is possible to approximate both problems within a logarithmic factor, but sublogarithmic approximation ratios are intractable. In bounded-degree graphs, there is a trivial constant-factor approximation algorithm, but arbitrarily low approximation ratios remain intractable. In so-called local graphs, there is a polynomial-time approximation scheme. We also consider fractional packing of codes and a related problem of finding minimum-weight codes.     

Complexity and Approximability of the Cover Polynomial

The cover polynomial and its geometric version introduced by Chung & Graham and D??Antona & Munarini, respectively, are two-variate graph polynomials for directed graphs. They count the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, can be thought of as interpolations between determinant and permanent, and are proposed as directed analogues of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #P-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomials: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial and its geometric version is #P-hard under polynomial time Turing reductions, while only three points in the cover polynomial and two points in the geometric cover polynomial are easy. We also study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ?? NP and RFP ?? #P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within any polynomial factor is not possible.     

The Parameterized Approximability of TSP with Deadlines

Modern algorithm theory includes numerous techniques to attack hard problems, such as approximation algorithms on the one hand and parameterized complexity on the other hand. However, it is still uncommon to use these two techniques simultaneously, which is unfortunate, as there are natural problems that cannot be solved using either technique alone, but rather well if we combine them. The problem to be studied here is not only natural, but also practical: Consider TSP, generalized as follows. We impose deadlines on some of the vertices, effectively constraining them to be visited prior to a given point of time. The resulting problem DlTSP (a special case of the well-known TSP with time windows) inherits its hardness from classical TSP, which is both well known from practice and renowned to be one of the hardest problems with respect to approximability: Within polynomial time, not even a polynomial approximation ratio (let alone a constant one) can be achieved (unless P = NP). We will show that DlTSP is even harder than classical TSP in the following sense. Classical TSP, despite its hardness, admits good approximation algorithms if restricted to metric (or near-metric) inputs. Not so DlTSP (and hence, neither TSP with time windows): We will prove that even for metric inputs, no constant approximation ratio can ever be achieved (unless P = NP). This is where parameterization becomes crucial: By combining methods from the field of approximation algorithms with ideas from the theory of parameterized complexity, we apply the concept of parameterized approximation. Thereby, we obtain a 2.5-approximation algorithm for DlTSP with a running time of k! · poly(|G|), where k denotes the number of deadlines. Furthermore, we prove that there is no fpt-algorithm with an approximation guarantee of 2-ε for any ε > 0, unless P = NP. Finally, we show that, unlike TSP, DlTSP becomes much harder when relaxing the triangle inequality. More precisely, for an arbitrary small violation of the triangle inequality, DlTSP does not admit an fpt-algorithm with approximation guarantee ((1-ε)/2)|V| for any ε > 0, unless P = NP.     

Logspace Optimization Problems and Their Approximability Properties

Logspace optimization problems are the logspace analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties even though their underlying decision problems have the same computational complexity. Natural problems - including the shortest path problems for directed graphs, undirected graphs, tournaments, and forests - exhibit such a varying complexity. In order to study the approximability of logspace optimization problems in a systematic way, polynomial-time approximation classes and polynomial-time reductions between optimization problems are transferred to logarithmic space. It is proved that natural problems are complete for different logspace approximation classes. This is used to show that under the assumption L ≠ NL some logspace optimization problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but optimal solutions cannot be computed in logarithmic space.     

Disjoint pattern database heuristics

We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases [J. Culberson, J. Schaeffer, Comput. Intelligence 14 (3) (1998) 318–334]. While many heuristics, such as Manhattan distance, compute the cost of solving individual subgoals independently, pattern databases consider the cost of solving multiple subgoals simultaneously. Existing work on pattern databases allows combining values from different pattern databases by taking their maximum. If the subgoals can be divided into disjoint subsets so that each operator only affects subgoals in one subset, then we can add the pattern-database values for each subset, resulting in a more accurate admissible heuristic function. We used this technique to improve performance on the Fifteen Puzzle by a factor of over 2000, and to find optimal solutions to 50 random instances of the Twenty-Four Puzzle.     

Output-Sensitive Reporting of Disjoint Paths

A k -path query on a graph consists of computing k vertex-disjoint paths between two given vertices of the graph, whenever they exist. In this paper we study the problem of performing k -path queries, with , in a graph G with n vertices. We denote with the total length of the reported paths. For , we present an optimal data structure for G that uses O(n) space and executes k -path queries in output-sensitive time. For triconnected planar graphs, our results make use of a new combinatorial structure that plays the same role as bipolar (st ) orientations for biconnected planar graphs. This combinatorial structure also yields an alternative construction of convex grid drawings of triconnected planar graphs. Received August 24, 1996; revised April 8, 1997.     

Local Approximability of Max-Min and Min-Max Linear Programs

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ _I positive elements, and each row c _k of C has at most Δ _K positive elements.     

On Finding Min-Min Disjoint Paths

The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard and admits no K-approximation for any K>1 in the general case (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006). In this paper, we first show that Bhatia et al.’s NP-hardness proof (Bhatia et al. in J. Comb. Optim. 12:83–96, 2006), a claim of correction to Xu et al.’s proof (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006), for the edge-disjoint Min-Min problem in the general undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in the proof of Bhatia et al. (J. Comb. Optim. 12:83–96, 2006). We then gave a correct proof of NP-hardness of this problem in undirected graphs. Finally we give a polynomial-time algorithm for the vertex disjoint Min-Min problem in planar graphs by showing that the vertex disjoint Min-Min problem is polynomially solvable in st-planar graph G=(V,E) whose corresponding auxiliary graph G(V,E∪{e(st)}) can be embedded into a plane, and a planar graph can be decomposed into several st-planar graphs whose Min-Min paths collectively contain a Min-Min disjoint-path pair between s and t in the original graph G. To the best of our knowledge, these are the first polynomial algorithms for the Min-Min problems in planar graphs.     

Approximability Properties for Second-Order Sliding Mode Control Systems

New definitions of approximability are presented for nonlinear second-order sliding mode control systems. Such robustness properties are compared with those already known for first-order methods. Sufficient conditions are obtained for second-order regularization, a sliding error estimate is derived, and some relevant examples are discussed.     

独立路径问题的算法设计

根据网络中可供选择的路由数目,提出独立路径的一个新问题,即求网络中最多同时存在多少条相互独立的路径。同时,针对选择最优路由,研究求权值和最小的K(K＞1, K为整数)条独立路径的问题,发现和证明独立路径与网络流的关系,并采用网络流方法设计简单算法。应用结果表明,该算法的复杂度较小,可用于解决网络通信中的多径路由问题。     

Disjoint pattern matching and implication in strings

We deal with the problem of deciding whether a given set of string patterns implies the presence of a fixed pattern. While checking whether a set of patterns occurs in a string is solvable in polynomial time, this implication problem is well known to be intractable. Here we consider a version of the problem when patterns in the set are required to be disjoint. We show that for such a version of the problem the situation is reversed: checking whether a set of patterns occurs in a string is NP-complete, but the implication problem is solvable in polynomial time.