On Syntactic versus Computational Views of Approximability
From MaRDI portal
Recommendations
- A syntactic view of computational adequacy
- scientific article; zbMATH DE number 17534
- scientific article; zbMATH DE number 222191
- Computational complexity of the semantics of some natural language constructions
- The computational complexity of ideal semantics
- scientific article; zbMATH DE number 4028929
- Finite Approximations and Similarity of Languages
- Computational complexity of syntactic agreement and lexical ambiguity
- On computational complexity of contextual languages
- scientific article; zbMATH DE number 569758
Cited in
(75)- Parameterizing above or below guaranteed values
- Covering the edges of bipartite graphs using \(K_{2,2}\) graphs
- Integer programming as a framework for optimization and approximability
- Tight bound on Johnson's algorithm for maximum satisfiability
- New local search approximation techniques for maximum generalized satisfiability problems
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Improved approximations for maximum independent set via approximation chains
- Lexicographic local search and the \(p\)-center problem.
- Local approximations for maximum partial subgraph problem.
- Structural properties of bounded relations with an application to NP optimization problems
- A syntactic view of computational adequacy
- Finding a potential community in networks
- Temporal network optimization subject to connectivity constraints
- Complexity and inapproximability results for the power edge set problem
- Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
- On inverse traveling salesman problems
- Computing unrestricted synopses under maximum error bound
- Complexity of determining the most vital elements for the p-median and p-center location problems
- Reactive local search techniques for the maximum k-conjunctive constraint satisfaction problem (MAX-k-CCSP)
- Inequity aversion pricing over social networks: approximation algorithms and hardness results
- On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Parameterized approximability of maximizing the spread of influence in networks
- The complexity of finding harmless individuals in social networks
- Some results on more flexible versions of Graph Motif
- Approximability of identifying codes and locating-dominating codes
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Critical edges for the assignment problem: complexity and exact resolution
- Reductions, completeness and the hardness of approximability
- Completeness in approximation classes beyond APX
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
- On the complexity landscape of the domination chain
- Nonoblivious 2-opt heuristics for the traveling salesman problem
- Approximation and nonapproximability for the one-sided scaffold filling problem
- Local search to approximate MAX NAE-k-SAT tightly
- A note on anti-coordination and social interactions
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- Toward a model for backtracking and dynamic programming
- Local search: is brute-force avoidable?
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- A survey on the structure of approximation classes
- Genomic scaffold filling: a progress report
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
- Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
- A local-search algorithm for Steiner forest
- Improved approximations of independent sets in bounded-degree graphs
- On approximation properties of the Independent set problem for degree 3 graphs
- Approximation of Constraint Satisfaction via local search
- Approximating Max NAE-\(k\)-SAT by anonymous local search
- A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
- A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
- On the complexity of finding a potential community
- A stronger model of dynamic programming algorithms
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- Structure in approximation classes
- On parallel versus sequential approximation
- 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
- Uniform unweighted set cover: the power of non-oblivious local search
- Ultimate greedy approximation of independent sets in subcubic graphs
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Approximating maximum-size properly colored forests
- Structure of polynomial-time approximation
- A 4/3-approximation for the maximum leaf spanning arborescence problem in DAGs
- On the complexity of fixed parameter clique and dominating set
- The approximation ratio of the 2-Opt heuristic for the Euclidean traveling salesman problem
- A \(\frac{4}{3}\)-approximation for the maximum leaf spanning arborescence problem in DAGs
- Approximating maximum-size properly colored forests
- From worst case to the average: structural guarantees in k-CSP approximation via orthogonal arrays
- Polynomial time approximation schemes and parameterized complexity
This page was built for publication: On Syntactic versus Computational Views of Approximability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210142)
