1,722,215 research outputs found
On the MAX k-VERTEX COVER problem
No full textGiven a graph G(V,E) of order n and a constant k ≤ n, the MAX k-VERTEX COVER problem consists of determining k vertices that cover the maximum number of edges in G. In its (standard) parameterized version, MAX k-VERTEX COVER can be stated as follows: "given G, k and parameter ℓ, does G contain k vertices that cover at least ℓ edges?". We first devise moderately exponential exact algorithms for MAX k-VERTEX COVER, with complexity exponential to n (note that the known results concerned time bounds of the form ) by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, interestingly enough, although MAX k-VERTEX COVER is non fixed parameter tractable with respect to ℓ, it is fixed parameter tractable with respect to the size τ of a minimum vertex cover of G. We also point out that the same happens for a lot of well-known problems quite different from MAX k-VERTEX COVER. We finally study approximation MAX k-VERTEX COVER by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
Full text linkWe give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-k-CSP. For instances with n variables and cn clauses (constraints), we give algorithms running in time poly(n)⋅2n(1−μ) forμ=Ω(1/c) and polynomial space solving MAX-SAT and MAX-k-SAT,μ=Ω(1√c) and exponential space solving MAX-SAT and MAX-k-SAT,μ=Ω(1/ck2) and polynomial space solving MAX-k-CSP,μ=Ω(1/√ck3) and exponential space solving MAX-k-CSP.The previous MAX-SAT algorithms have savings μ=Ω(1/c2log2c) for running in polynomial space [15] and μ=Ω(1/clogc) for exponential space [5]. We also give an algorithm with improved savings for satisfiability of depth-2 threshold circuits with cn wires
Smoothed analysis of Max-k-sat
No full textThe max-k-sat problem asks to find a truth assignment to n Boolean variables that maximizes the total number of satisfied clauses in a conjunctive normal form formula with k variables per clause. We show that, with high probability, a natural local search algorithm finds a locally optimal solution on a randomly weighted formula containing all distinct clauses in time n to the power 5(k+1), thus establishing polynomial smoothed complexity for this variant of max-k-sat. Further analysis improves this bound to n to the power 4k+ sqrt(12k)+2, which also yields a small improvement in the smoothed complexity of the analogous max-cut problem.Le problème max-k-sat consiste à trouver une attribution de valeur de vérité pour n variables booléennes de manière a maximiser le nombre totale de clauses satisfaites dans une formule en forme normale conjonctive à k variables par clause. Nous montrons qu'avec une forte probabilité, un algorithme de recherche locale obtient une solution localement optimale pour une formule avec des poids aléatoires contenant tous les clauses dans un temps de l'ordre de n à la puissance de 5(k+1). Ceci nous permet d'établir une complexité lisse polynomiale pour cette variante du problème max-k-sat. Une analyse plus approfondie nous permet d'améliorer cette borne et d'obtenir un temps de l'ordre n à la puissance de 4k+sqrt(12k)+2, ce qui donne lieu à une amélioration de la complexité lisse du problème analogue max-cut
Complex Semidefinite Programming and Max-k-Cut
Full text linkIn a second seminal paper on the application of semidefinite
programming to graph partitioning problems, Goemans and Williamson
showed in 2004 how to formulate and round a complex semidefinite program to give what is to date still the best-known approximation guarantee of .836008 for Max-3-Cut. (This approximation ratio was also achieved independently around the same time by De Klerk et
al..) Goemans and Williamson left open the problem of how to apply their techniques to Max-k-Cut for general k. They point out that it does not seem straightforward or even possible to formulate a good quality complex semidefinite program for the general Max-k-Cut problem, which presents a barrier for the further application of their techniques.
We present a simple rounding algorithm for the standard semidefinite
programmming relaxation of Max-k-Cut and show that it is equivalent to the rounding of Goemans and Williamson in the case of Max-3-Cut. This allows us to transfer the elegant analysis of Goemans and Williamson for Max-3-Cut to Max-k-Cut. For k > 3, the resulting approximation ratios are about .01 worse than the best known guarantees. Finally, we present a generalization of our rounding algorithm and conjecture (based on computational observations) that it matches the best-known guarantees of De Klerk et al
Approximation algorithm for non-boolean max k-csp
No full textAbstract. In this paper, we present a randomized polynomial-time approximation algorithm for MAX k-CSPd. In MAX k-CSPd, we are given a set of predicates of arity k over an alphabet of size d. Our goal is to find an assignment that maximizes the number of satisfied constraints. Our algorithm has approximation factor Ω(kd/dk) (when k ≥ Ω(log d)). This bound is asymptotically optimal assuming the Unique Games Conjecture. The best previously known algorithm has approxi-mation factor Ω(k log d/dk). We also give an approximation algorithm for the boolean MAX k-CSP2 problem with a slightly improved approximation guarantee.
Efficient Algorithms for the max k -vertex cover Problem
No full textInternational audienceWe first devise moderately exponential exact algorithms for max k -vertex cover, with time-complexity exponential in n but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max k -vertex cover with complexity bounded above by the maximum among c k and γ τ , for some γ < 2, where τ is the cardinality of a minimum vertex cover of G (note that \textsc{maxk-vertex cover}{} \notin \textbf{FPT} with respect to parameter k unless FPT=W[1] ), using polynomial space. We finally study approximation of max k -vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time
Directed plateau search for MAX-k-SAT
No full textLocal search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau “gradient” function using aWalsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.Andrew M. Sutton, Adele E. Howe and L. Darrell Whitle
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Parameterized algorithms for the max k-set cover and related satisfiability problems
No full textGiven a family of subsets S = {S1, . . . , Sm} over a set of elements X = {x1, . . . , xn} and an integer p, max k-set cover consists of finding a set T of at most k subsets covering at least p elements. This problem, when parameterized by k, can be easily shown to be W[2]-hard. Here, we settle the parameterized complexity of max k-set cover under several parameters as max{k,_}, where _ = maxi{|Si|}, p and max{k, f}, where f = maxi |{j|xi 2 Sj}|. We also study parameterized approximability of the problem with respect to parameters k and p. We also study parameterization of a satisfiability problem that is linked to max k-set cover in a sense explained in the paper. Finally, we sketch an enhancement of the classes of the W[*] that seems more appropriate for showing completeness of hard W[*]-problems
- …
