We address item relocation problems in graphs in this paper. We assume items placed in vertices of an undirected graph with at most one item per vertex. Items can be moved across edges while various constraints depending on the type of relocation problem must be satisfied. We introduce a general problem formulation that encompasses known types of item relocation problems such as multi-agent path finding (MAPF) and token swapping (TSWAP). In this formulation we express two new types of relocation problems derived from token swapping that we call token rotation (TROT) and token permutation (TPERM). Our solving approach for item relocation combines satisfiability modulo theory (SMT) with conflict-based search (CBS). We interpret CBS in the SMT framework where we start with the basic model and refine the model with a collision resolution constraint whenever a collision between items occurs in the current solution. The key difference between the standard CBS and our SMT-based modification of CBS (SMT-CBS) is that the standard CBS branches the search to resolve the collision while in SMT-CBS we iteratively add a single disjunctive collision resolution constraint. Experimental evaluation on several benchmarks shows that the SMT-CBS algorithm significantly outperforms the standard CBS. We also compared SMT-CBS with a modification of the SAT-based MDD-SAT solver that uses an eager modeling of item relocation in which all potential collisions are eliminated by constrains in advance. Experiments show that lazy approach in SMT-CBS produce fewer constraint than MDD-SAT and also achieves faster solving run-times.
Feasible solution of a solvable MAPF instance can be found in polynomial time @cite_14 @cite_35 ; precisely the worst case time complexity of most practical algorithms for finding feasible solutions is @math (asymptotic size of the solution is also @math ) @cite_11 @cite_29 @cite_26 @cite_3 @cite_17 @cite_45 . This is also asymtotically best what can be done as there are MAPF instances requiring @math moves. As with TSWAP, finding optimal MAPF solutions with respect to various cummulative objectives is NP-hard @cite_43 @cite_10 @cite_12 .
@cite_35 @cite_14 @cite_26 @cite_29 @cite_17 @cite_3 @cite_43 @cite_45 @cite_10 @cite_12 @cite_11
2567804199 2008724760 1533811829 1982713256
An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1 + ϵ)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1 ϵ, i.e., Ω(n221 ϵ). A double or triple exponential dependence on 1 ϵ is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+ϵ)-approximation algorithm with a running time of Oϵ(1)·nO(1). In particular, the exponent of n in the running time does not depend on ϵ at all! Since there can be no FPTAS for the problem (unless P = NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Ω(221 ϵ) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Ω(n221 ϵ) and we improve both to Oϵ(1) · nO(1). We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1 + ϵ)-resource augmentation. In this setting, we also improve the best known running time of Ω(n1 ϵ1 ϵ) to Oϵ(1) · nO(1) and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well. In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP ⊆ naPCP1,s[O(log n),3]? In the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems ("3-CSPs") is NP-hard. The previous best upper bound and lower bound for s are 20 27+µ by Khot and Saket [KS06], and 5 8 (assuming NP subseteq BPP) by Zwick [Zwi98]. In this paper we close the gap assuming Khot's d-to-1 Conjecture. Formally, we prove that if Khot's d-to-1 Conjecture holds for any finite constant integer d, then NP naPCP1,5 8+ µ[O(log n),3] for any constant µ > 0. Our conditional result also solves Hastad's open question [Has01] on determining the inapproximability of satisfiable Max-NTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5 8-approximation algorithm for satisfiable 3-CSPs is optimal. We consider worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a, b)-CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2, 3)-CSP while 3-coloring and various related problems are special cases of (3, 2)-CSP; there is also a natural duality transformation from (a, b)-CSP to (b, a)-CSP. We show that n-variable (3, 2)-CSP instances can be solved in time O(1.3645n), that satisfying assignments to (d, 2)-CSP instances can be found in randomized expected time O((0.4518d)n); that 3-coloring of n-vertex graphs can be solved in time O(1.3289n); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645n); that 3-edge-coloring of n-vertex graphs can be solved in time O(2n 2), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(nO(1) + 1.3645t). We consider the minimum spanning tree problem with conflict constraints (MSTC). The problem is known to be strongly NP-hard and computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded whereas the optimization version is still NP-hard. When the conflict graph is a collection of disjoint cliques, (equivalently, when the conflict relation is transitive) we observe that MSTC can be solved in polynomial time. We also identify other special cases of MSTC that can be solved in polynomial time. Exploiting these polynomially solvable special cases we derive strong lower bounds. Also, various heuristic algorithms and feasibility tests are discussed along with preliminary experimental results. As a byproduct of this investigation, we show that if an @e-optimal solution to the maximum clique problem can be obtained in polynomial time, then a ([email protected])-optimal solution to the maximum edge clique partitioning (Max-ECP) problem can be obtained in polynomial time. As a consequence, we have a polynomial time approximation algorithm for the Max-ECP with performance ratio O(n(loglogn)^2log^3n), improving the best previously known bound of O(n).