On Syntactic versus Computational Views of Approximability
From MaRDI portal
Publication:4210142
DOI10.1137/S0097539795286612zbMath0915.68068OpenAlexW2159579504MaRDI QIDQ4210142
Madhu Sudan, Sanjeev Khanna, Umesh V. Vazirani, Rajeev Motwani
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539795286612
computational complexitylocal searchapproximation algorithmspolynomial reductionscomplete problemscomputational classes
Related Items
On the Complexity of Finding a Potential Community, Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, Improved approximations of independent sets in bounded-degree graphs, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, On approximation properties of the Independent set problem for degree 3 graphs, Approximation of Constraint Satisfaction via local search, Approximability of identifying codes and locating-dominating codes, New local search approximation techniques for maximum generalized satisfiability problems, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, The complexity and approximability of finding maximum feasible subsystems of linear relations, Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem, Polynomial time approximation schemes and parameterized complexity, Improved approximations for maximum independent set via approximation chains, An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem, A note on anti-coordination and social interactions, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Structure in approximation classes, On inverse traveling salesman problems, The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem, New approximation algorithms for RNA secondary structures prediction problems by local search, Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Uniform unweighted set cover: the power of non-oblivious local search, Toward a model for backtracking and dynamic programming, Lexicographic local search and the \(p\)-center problem., Local search: is brute-force avoidable?, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), A survey on the structure of approximation classes, Local approximations for maximum partial subgraph problem., Critical edges for the assignment problem: complexity and exact resolution, A Local-Search Algorithm for Steiner Forest, Genomic Scaffold Filling: A Progress Report, Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees, Finding a potential community in networks, Temporal network optimization subject to connectivity constraints, Complexity and inapproximability results for the power edge set problem, Approximating Max NAE-\(k\)-SAT by anonymous local search, A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Parameterized approximability of maximizing the spread of influence in networks, Structure of polynomial-time approximation, A stronger model of dynamic programming algorithms, Reductions, completeness and the hardness of approximability, On the complexity of fixed parameter clique and dominating set, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?, Completeness in approximation classes beyond APX, Inequity aversion pricing over social networks: approximation algorithms and hardness results, On the Complexity Landscape of the Domination Chain, Parameterizing above or below guaranteed values, Nonoblivious 2-Opt heuristics for the traveling salesman problem, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP, A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem, Integer programming as a framework for optimization and approximability, Covering the edges of bipartite graphs using \(K_{2,2}\) graphs, Structural properties of bounded relations with an application to NP optimization problems, The complexity of finding harmless individuals in social networks, Tight bound on Johnson's algorithm for maximum satisfiability, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Some results on more flexible versions of Graph Motif
