Search

In this paper, we consider a testing setting where the set of possible definitions of the Implementation Under Test (IUT), as well as the behavior of each of these definitions in all possible interactions, are extensionally defined, i.e., on an element-by-element and case-by-case basis. Under this setting, the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not (i.e., whether it necessarily belongs to the set of possible correct definitions or not) is studied in four possible problem variants: with or without non-determinism; and with or without more than one possible definition in the sets of possible correct and incorrect definitions. The computational complexity of these variants is studied, and properties such as PSPACE-completeness and Log-APX-hardness are identified. [ABSTRACT FROM AUTHOR]

Stackelberg pricing games are pricing problems over a set of items. One player, the leader , sets prices for the items and the second player, the follower , buys a subset of items at minimal total cost subject to feasibility constraints. The constraints are determined by an optimization problem. For example, the Stackelberg shortest path game is used to optimize the income from road tolls (cf. [21]). The items are edges in a network graph and the follower buys a subset of edges forming a path. The Stackelberg pricing games studied in the literature are formulated on top of covering problems. In this paper, we introduce pricing games based on packing problems. We are interested in the complexity of computing leader-optimal prices depending on different types of follower-constraints. We show that optimal prices can be computed in polynomial time if the follower-constraints are determined by the well-known interval scheduling problem. This problem is equivalent to the independent set problem on interval graphs. In case the follower-constraints are based on the independent set problem on perfect graphs or on the bipartite matching problem, we prove APX-hardness for the pricing problem. On a more general note, we prove Σ 2 p -completeness if the follower-constraints are given by a packing problem that is NP-complete, i.e., the leader's pricing problem is hard even if she has an NP-oracle at hand. [ABSTRACT FROM AUTHOR]

The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low occurrence of Constraint Satisfaction problems as intermediate steps in the NP-hard gap reductions. Allowing the weights in intermediate problems is rather natural for the edge-weighted problems as Travelling Salesman or Steiner Tree. We demonstrate the technique for Travelling Salesman and use the parametrised weighted amplifiers in the gap reductions to allow more flexibility in fine-tuning their expanding parameters. The purpose of this paper is to point out effectiveness of these ideas, rather than to optimise the expander's parameters. Nevertheless, we show that already slight improvement of known expander values modestly improve the current best approximation hardness value for TSP from 123 122 (Karpinski et al. in J Comput Syst Sci 81(8):1665–1677, 2015) to 117 116 . This provides a new motivation for study of expanding properties of random graphs in order to improve approximation lower bounds of TSP and other edge-weighted optimisation problems. [ABSTRACT FROM AUTHOR]

Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min‐Cost‐Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min‐Cost‐Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP‐hard. Further, we prove that MaxMCF is APX‐hard if a connectedness‐condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min‐Cost‐Flow Problem (MinMCF) can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show that under the exponential time hypothesis, there are no exact algorithms running in 2o(n) time or in f (d) ⋅ n O (1) time for any computable function f. We also show that the special case of connecting c network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size cO(1) unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects O(log n)-connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c. Summary of Contribution: Wireless sensor networks are used to monitor air pollution, water pollution, and machine health; in forest fire and landslide detection; and in natural disaster prevention. Sensors in wireless sensor networks are often battery-powered and disposable, so one may be interested in lowering the energy consumption of the sensors in order to achieve a long lifetime of the network. We study the min-power symmetric connectivity problem, which models the task of assigning transmission powers to sensors so as to achieve a connected communication network with minimum total power consumption. The problem is NP-hard. We provide perhaps the first parameterized complexity study of optimal and approximate solutions for the problem. Our algorithms work in polynomial time in the scenario where one has to reconnect a sensor network with n sensors and O(log n)-connected components by means of a minimum transmission power increase or if one can find transmission power lower bounds that already yield a network with O(log n)-connected components. In experiments, we show that, in this scenario, our algorithms outperform previously known exact algorithms based on ILP formulations. [ABSTRACT FROM AUTHOR]

Line of Sight (LoS) networks provide a model of wireless communication which incorporates visibility constraints. Vertices of such networks can be embedded onto the cube { (x 1 , x 2 , ... , x d) : x i ∈ { 1 , ... , n } , 1 ≤ i ≤ d } so that two vertices are adjacent if and only if their images lay on a line parallel to one of the cube edges and their distance is less than a given range parameter ω. In this paper we study large independent sets in LoS networks. We prove that the computational problem of finding a maximum independent set can be solved optimally in polynomial time for one dimensional LoS networks. However, for d ≥ 2 , the (decision version of) the problem becomes NP-complete for any fixed ω ≥ 3. In addition, we show that the problem is APX-hard when ω = n for d ≥ 3. On the positive side, we show that LoS networks generalize chordal graphs. This implies that there exists a simple d -approximation algorithm for the maximum independent set problem in LoS networks. Finally, we describe a polynomial time approximation scheme for the maximum independent set problem in LoS networks for the case when ω is a constant and present an improved heuristic algorithm for the problem in the case ω = n. [ABSTRACT FROM AUTHOR]

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. [ABSTRACT FROM AUTHOR]

We propose funnels as a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analogue to trees for directed graphs, being more restrictive than DAGs but more expressive than mere in-/out-trees. Computational problems such as finding vertex-disjoint paths or tracking the origin of memes remain NP-hard on DAGs while on funnels they become solvable in polynomial time. Our main focus is the algorithmic complexity of finding out how funnel-like a given DAG is. To this end, we identify the NP-hard problem of computing the arc-deletion distance of a given DAG to a funnel. We develop efficient exact and approximation algorithms for the problem and test them on synthetic random graphs and real-world graphs. [ABSTRACT FROM AUTHOR]

We study the problem of covering the vertices of an undirected weighted graph with a given number of trees (cycles, paths) to minimize the weight of the maximum weight tree (cycle, path). Improved inapproximability lower bounds are proved and better approximation algorithms are designed for several variants of this problem. [ABSTRACT FROM AUTHOR]

Langton’s ant is a deterministic cellular automaton studied in many fields, artificial life, computational complexity, cryptography, emergent dynamics, Lorents lattice gas, and so forth, motivated by the hardness of predicting the ant’s macroscopic behavior from an initial microscopic configuration. Gajardo, Moreira, and Goles (2002) proved that Langton’s ant is PTIME -hard for reachability. On a twisted torus, we demonstrate that it is PSPACE hard to determine whether the ant will ever visit almost all vertices or nearly none of them.

Line graphs constitute a rich and well-studied class of graphs. In this paper, we focus on three different topics related to line graphs of subcubic triangle-free graphs. First, we show that any such graph G has an independent set of size at least 3 | V ( G ) | ∕ 10 , the bound being sharp. As an immediate consequence, we have that any subcubic triangle-free graph G , with n i vertices of degree i , has a matching of size at least 3 n 1 ∕ 20 + 3 n 2 ∕ 10 + 9 n 3 ∕ 20 . Then we provide several approximate min-max theorems relating cycle-transversals and cycle-packings of line graphs of subcubic triangle-free graphs. This enables us to prove Jones’ Conjecture for claw-free graphs with maximum degree 4 . Finally, we concentrate on the computational complexity of Feedback Vertex Set , Hamiltonian Cycle and Hamiltonian Path for subclasses of line graphs of subcubic triangle-free graphs. [ABSTRACT FROM AUTHOR]

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k -uniform k -partite hypergraphs. [ABSTRACT FROM AUTHOR]

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for t-interval graphs when t≥3 and polynomial-time solvable when t=1. The problem is also known to be NP-complete in t-track graphs when t≥4 and polynomial-time solvable when t≤2. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called t-circular interval graphs and t-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time t-approximation algorithm for MAXIMUM WEIGHTED CLIQUE on t-interval graphs, improving earlier work with approximation ratio 4 t. [ABSTRACT FROM AUTHOR]

Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable emphasis is placed on the analyzing the cause and effect of such threats. The financial crisis in the current and past decade has shown that one important cause of instability in global markets is the so-called financial contagion, namely the spreadings of instabilities or failures of individual components of the network to other, perhaps healthier, components. This leads to a natural question of whether the regulatory authorities could have predicted and perhaps mitigated the current economic crisis by effective computations of some stability measure of the banking networks. Motivated by such observations, we consider the problem of defining and evaluating stabilities of both homogeneous and heterogeneous banking networks against propagation of synchronous idiosyncratic shocks given to a subset of banks. We formalize the homogeneous banking network model of Nier et al. (J. Econ. Dyn. Control 31:2033-2060, ) and its corresponding heterogeneous version, formalize the synchronous shock propagation procedures outlined in (Nier et al. J. Econ. Dyn. Control 31:2033-2060, ; M. Eboli Mimeo, ), define two appropriate stability measures and investigate the computational complexities of evaluating these measures for various network topologies and parameters of interest. Our results and proofs also shed some light on the properties of topologies and parameters of the network that may lead to higher or lower stabilities. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes whose fitness is a function of the statistical significance of the pairwise interactions of nodes in the module. The topic of this paper is a model-based community finding approach, commonly referred to as modularity clustering, that was originally proposed by Newman (Leicht and Newman, 2008 [25]) and has subsequently been extremely popular in practice (e.g., see Agarwal and Kempe, 2008 [1], Guimer‘a et al., 2007 [20], Newman, 2006 [28], Newman and Girvan, 2004 [30], Ravasz et al., 2002 [32]). Various heuristic methods are currently employed for finding the optimal solution. However, as observed in Agarwal and Kempe (2008) [1], the exact computational complexity of this approach is still largely unknown. To this end, we initiate a systematic study of the computational complexity of modularity clustering. Due to the specific quadratic nature of the modularity function, it is necessary to study its value on sparse graphs and dense graphs separately. Our main results include a -inapproximability for dense graphs and a logarithmic approximation for sparse graphs. We make use of several combinatorial properties of modularity to get these results. These are the first non-trivial approximability results beyond the NP-hardness results in Brandes et al. (2007) [10]. [Copyright &y& Elsevier]

Abstract: We consider the Minimum Vertex Cover problem in hypergraphs in which every hyperedge has size k (also known as Minimum Hitting Set problem, or minimum set cover with element frequency k). Simple algorithms exist that provide k-approximations, and this is believed to be the best approximation achievable in polynomial time. We show how to exploit density and regularity properties of the input hypergraph to break this barrier. In particular, we provide a randomized polynomial-time algorithm with approximation factor , where and Δ are the average and maximum degree, and Δ must be . The proposed algorithm generalizes the recursive sampling technique of Imamura and Iwama (SODAʼ05) for vertex cover in dense graphs. As a corollary, we obtain an approximation factor arbitrarily close to for subdense regular hypergraphs, which is shown to be the best possible under the Unique Games conjecture. [Copyright &y& Elsevier]

Abstract: This paper studies a min–max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min–max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless , it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature. [Copyright &y& Elsevier]

We investigate a natural combinatorial optimization problem called the Label Cut problem. Given an input graph G with a source s and a sink t, the edges of G are classified into different categories, represented by a set of labels. The labels may also have weights. We want to pick a subset of labels of minimum cardinality (or minimum total weight), such that the removal of all edges with these labels disconnects s and t. We give the first non-trivial approximation and hardness results for the Label Cut problem. Firstly, we present an $O(\sqrt{m})$ -approximation algorithm for the Label Cut problem, where m is the number of edges in the input graph. Secondly, we show that it is NP-hard to approximate Label Cut within $2^{\log ^{1-1/\log\log^{c}n}n}$ for any constant c<1/2, where n is the input length of the problem. Thirdly, our techniques can be applied to other previously considered optimization problems. In particular we show that the Minimum Label Path problem has the same approximation hardness as that of Label Cut, simultaneously improving and unifying two known hardness results for this problem which were previously the best (but incomparable due to different complexity assumptions). [ABSTRACT FROM AUTHOR]

The article focuses on the min-max path cover problems of vehicle routing. It highlights on the improved approximation algorithms and first approximation hardness results presented for the four typical variants of the cover problems wherein the vehicles have shown unlimited and limited capacities. It also discusses the possible extensions of the techniques developed for other min-max problems of vehicle routing.

Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that can be represented as the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the Cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum integer such that can be represented as the intersection graph of a collection of -cubes. The threshold dimension of a graph is the smallest integer such that can be covered by threshold spanning subgraphs of . In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on vertices with a factor of for any unless . From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on vertices with factor for any unless . In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is -complete to determine whether a given split graph has boxicity at most 3. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results in [A. Caprara, R. Rizzi, Packing triangles in bounded degree graphs, Inform. Process. Lett. 84 (4) (2002) 175–180; J. Chlebíková, M. Chlebík, Complexity of approximating bounded variants of optimization problems, Theoret. Comput. Sci. 354 (3) (2006) 320–338]; this is done by directly transforming the inapproximability gap of Håstad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [J. Håstad, Some optimal inapproximability results, in: Proc. of the 29th Annual ACM Symp. on Theory of Computing, 1997, pp. 1–10] and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. [T.Y. Berger-Wolf, B. DasGupta, W. Chaovalitwongse, M.V. Ashley, Combinatorial reconstruction of sibling relationships, in: Proc. of the 6th International Symposium on Computational Biology and Genome Informatics, 2005, pp. 1252–1255; T.Y. Berger-Wolf, S. Sheikh, B. DasGupta, M.V. Ashley, I. Caballero, W. Chaovalitwongse, S.L. Putrevu, Reconstructing sibling relationships in wild populations, Bioinformatics 23 (13) (2007) i49–i56] and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or [R. Hassin, E. Or, A maximum profit coverage algorithm with application to small molecules cluster identification, in: 5th International Workshop Experimental Algorithms, in: Lecture Notes in Comput. Sci., vol. 4007, Springer-Verlag, 2006, pp. 265–276]. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: Maximum Agreement SubTree (MAST) and Maximum Compatible Tree (MCT). Both problems take as input a label set and a collection of trees whose leaf sets are each bijectively labeled with the label set. Define the size of a tree as the number of its leaves. The well-known MAST problem consists of finding a maximum-sized tree that is topologically embedded in each input tree, under label-preserving embeddings. Its variant MCT is less stringent, as it allows the input trees to be arbitrarily refined. Our results are as follows. We show that MCT is -hard to approximate within bound on rooted trees, where denotes the size of each input tree; the same approximation lower bound was already known for MAST [J. Jansson, Consensus algorithms for trees and strings, Ph. D. Thesis, Lund University, 2003]. Furthermore, we prove that MCT on two rooted trees is not approximable within bound , unless all problems in are solvable in quasi-polynomial time; the same result was previously established for MAST on three rooted trees [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1–3) (1996) 153–169] (note that MAST on two trees is solvable in polynomial time [M.A. Steel, T.J. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, Information Processing Letters 48 (2) (1993) 77–82]). Let CMAST, resp. CMCT, denote the complement version of MAST, resp. MCT: CMAST, resp. CMCT, consists of finding a tree that is a feasible solution of MAST, resp. MCT, and whose leaf label set excludes a smallest subset of the input labels. The approximation threshold for CMAST, resp. CMCT, on rooted trees is shown to be the same as the approximation threshold for CMAST, resp. CMCT, on unrooted trees; it was already known that both CMAST and CMCT are approximable within ratio three on rooted and unrooted trees [V. Berry, F. Nicolas, Maximum agreement and compatible supertrees, in: S.C. Sahinalp, S. Muthukrishnan, U. Dogrusoz (Eds.), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM’04, in: LNCS, vol. 3109, Springer-Verlag, 2004, pp. 205–219; G. Ganapathy, T.J. Warnow, Approximating the complement of the maximum compatible subset of leaves of trees, in: K. Jansen, S. Leonardi, V. V. Vazirani (Eds.), Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX’02, in: LNCS, vol. 2462, Springer-Verlag, 2002, pp. 122–134]. The latter results are completed by showing that CMAST is -hard on three rooted trees and that CMCT is -hard on two rooted trees. [Copyright &y& Elsevier]

Abstract: We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a stable matching of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals/Residents problem. We show that stable matchings can have different sizes, which motivates max-spa-p, the problem of finding maximum cardinality stable matching. We prove that max-spa-p is NP-hard and not approximable within δ, for some , unless . On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p. [Copyright &y& Elsevier]

Abstract: The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems Khanna et al. [Constraint satisfaction: the approximability of minimization problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24–27 June, 1997, pp. 282–296], and its approximability is largely open. We prove a lower approximation bound of , improving the previous bound of by Dinur and Safra [The importance of being biased, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), May 2002, pp. 33–42, also ECCC Report TR01-104, 2001]. For highly restricted instances with exactly four occurrences of every variable we provide a lower bound of . Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated). We further prove that any k-approximation algorithm for the MINIMUM 2SAT-DELETION problem polynomially reduces to a -approximation algorithm for the MINIMUM VERTEX COVER problem. One ingredient of these improvements is our proof that the MINIMUM VERTEX COVER problem is hardest to approximate on graphs with perfect matching. More precisely, the problem to design a -approximation algorithm for the MINIMUM VERTEX COVER on general graphs polynomially reduces to the same problem on graphs with perfect matching. This improves also on the results by Chen and Kanj [On approximating minimum vertex cover for graphs with perfect matching, Proceedings of the 11st ISAAC, Taipei, Taiwan, Lecture Notes in Computer Science, vol. 1969, Springer, Berlin, 2000, pp. 132–143]. [Copyright &y& Elsevier]

Abstract: The general asymmetric TSP with triangle inequality is known to be approximable only within logarithmic factors. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics, i.e., metrics where the distances are integers between one and some constant upper bound. In this case, the problem is known to be approximable within a constant factor. We prove that it is NP-hard to approximate the asymmetric TSP with distances one and two within and that it is NP-hard to approximate the symmetric TSP with distances one and two within for every constant . Recently, Papadimitriou and Vempala announced improved approximation hardness results for both symmetric and asymmetric TSP with graph metric. We show that a similar construction can be used to obtain only slightly weaker approximation hardness results for TSP with triangle inequality and distances that are integers between one and eight. This shows that the Papadimitriou–Vempala construction is “local” in nature and, intuitively, indicates that it cannot be used to obtain hardness factors that grow with the size of the instance. [Copyright &y& Elsevier]

Abstract: We study low degree graph problems such as Maximum Independent Set and Minimum Vertex Cover. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, . We prove, for example, that it is NP-hard to achieve an approximation factor of for Max-3-DM, and a factor of for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element. [Copyright &y& Elsevier]

Constraint satisfaction programs where each constraint depends on a constant number of variables have the following property: The randomized algorithm that guesses an assignment uniformly at random satisfies an expected constant fraction of the constraints. Combining constructions from interactive proof systems with harmonic analysis over finite Abelian groups, Håstad [J. A CM, 48 (2001), PP. 798-859] showed that for several constraint satisfaction programs this naive algorithm is essentially the best possible unless P = NP. While most of the predicates analyzed by Håstad depend on a small number of variables, Samorodnitsky and Trevisan [Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 191-199] recently extended Håstad's result to predicates depending on an arbitrarily large, but still constant, number of Boolean variables. We combine ideas from these two constructions and prove that there exists a large class of predicates on finite non-Boolean domains such that for predicates in the class, the naive randomized algorithm that guesses a solution uniformly is essentially the best possible unless P = NP. As a corollary, we show that it is NP-hard to approximate the Maximum k-CSP problem over domains with size d within dk-2k½ - &epsiv;, for every constant &epsiv; > 0, unless P = NP. This lower bound extends the previously known bound for the case d = 2 and matches well with the best known upper bound, dk-1, of Serna, Trevisan, and Xhafa [Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 1373, M. Morvan, C. Meinel, and D. Krob, eds., Springer-Verlag, Berlin, 1998, pp. 488-498]. [ABSTRACT FROM AUTHOR]

The inapproximability of non-NP-hard optimization problems is investigated. Techniques are given to show that the problems LOG DOMINATING SET and LOG HYPERGRAPH VERTEX COVER cannot be approximated to a constant ratio in polynomial time unless the corresponding NP-hard versions are also approximable in deterministic subexponential time. A direct connection is established between non-NP-hard problems and a PCP characterization of NP. Reductions from the PCP characterization show that LOG CLIQUE is not approximable in polynomial time and MAX SPARSE SAT does not have a FPTAS under the assumption that NP⊈DTIME(2O(√ of n log n)). A number of nontrivial approximation-preserving reductions are also presented, making it possible to extend inapproximability results to more natural non-NP-hard problems such as TOURNAMENT DOMINATING SET and RICH HYPERGRAPH VERTEX COVER. [Copyright &y& Elsevier]

Langton's ant is a deterministic cellular automaton studied in many fields, artificial life, computational complexity, cryptography, emergent dynamics, Lorents lattice gas, and so forth, motivated by the hardness of predicting the ant's macroscopic behavior from an initial microscopic configuration. Gajardo, Moreira, and Goles (2002) proved that Langton's ant is PTIME -hard for reachability. On a twisted torus, we demonstrate that it is PSPACE hard to determine whether the ant will ever visit almost all vertices or nearly none of them. [ABSTRACT FROM AUTHOR]