Optimization, approximation, and complexity classes
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3566230 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Approximation algorithms for combinatorial problems
- How well can a graph be n-colored?
- Non deterministic polynomial optimization problems and their approximations
- On the complexity of approximating the independent set problem
- Some Examples of Difficult Traveling Salesman Problems
- Structure preserving reductions among convex optimization problems
- The Complexity of Near-Optimal Graph Coloring
- The complexity of optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
Cited in
(only showing first 100 items - show all)- Class Steiner trees and VLSI-design
- Grothendieck’s Theorem, past and present
- Complexity of majority monopoly and signed domination problems
- Max-leaves spanning tree is APX-hard for cubic graphs
- Orienting graphs to optimize reachability
- Pseudo-Boolean optimization
- A short note on the approximability of the maximum leaves spanning tree problem
- Finding occurrences of protein complexes in protein-protein interaction graphs
- Minimum vertex cover in ball graphs through local search
- On the approximability of some maximum spanning tree problems
- The complexity of multiple sequence alignment with SP-score that is a metric
- Some APX-completeness results for cubic graphs
- The multi-multiway cut problem
- Repetition-free longest common subsequence
- Max NP-completeness made easy
- Minimal multicut and maximal integer multiflow: a survey
- Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
- The transitive minimum Manhattan subnetwork problem in 3 dimensions
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Independent set of intersection graphs of convex objects in 2D
- A simple filter-and-fan approach to the facility location problem
- A mixed integer linear programming formulation of the maximum betweenness problem
- Approximability of the vertex cover problem in power-law graphs
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- The 0-1 inverse maximum stable set problem
- On the approximability of the maximum induced matching problem
- Maximum Motif Problem in Vertex-Colored Graphs
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Complexity issues in vertex-colored graph pattern matching
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- The maximum flow problem with disjunctive constraints
- Some notes on the nearest neighbour interchange distance
- Deterministic and randomized polynomial‐time approximation of radii
- Some MAX SNP-hard results concerning unordered labeled trees
- The labeled perfect matching in bipartite graphs
- On approximation algorithms for the minimum satisfiability problem
- On the approximability of some Maximum Spanning Tree Problems
- On the complexity landscape of the domination chain
- Differential approximation of MIN SAT, MAX SAT and related problems
- Computing the minimum number of hybridization events for a consistent evolutionary history
- Which problems have strongly exponential complexity?
- The longest common subsequence problem for arc-annotated sequences
- Maximum bounded \(H\)-matching is Max SNP-complete
- On the complexity of comparing evolutionary trees
- On the existence of subexponential parameterized algorithms
- Connected domination of regular graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Strong computational lower bounds via parameterized complexity
- Derandomized graph products
- Finding disjoint paths with related path costs
- Cryptography with constant input locality
- Approximability of scheduling problems with resource consuming jobs
- On the hardness of range assignment problems
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- NP-completeness: a retrospective
- A unified approximation algorithm for node-deletion problems
- Approximate solution of NP optimization problems
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Tractability-preserving transformations of global cost functions
- Complexity of approximating bounded variants of optimization problems
- Distinguishing string selection problems.
- Complexity of approximating CSP with balance/hard constraints
- Derandomized parallel repetition via structured PCPs
- The Stackelberg minimum spanning tree game
- \(\mathcal {NPD}\)atalog: A logic language for expressing \(\mathcal {NP}\) search and optimization problems
- Approximability of partitioning graphs with supply and demand
- Online maximum directed cut
- Assortment planning for multiple chain stores
- Multiway cuts in directed and node weighted graphs
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Combinatorial PCPs with short proofs
- Parameterizing above or below guaranteed values
- Computational experience with approximation algorithms for the set covering problem
- Approximate Max \(k\)-Cut with subgraph guarantee
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- A natural family of optimization problems with arbitrarily small approximation thresholds
- The NPO-completeness of the longest Hamiltonian cycle problem
- A tutorial on the cross-entropy method
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Metafinite model theory
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- The hardness of approximation: Gap location
- Randomized approximation of bounded multicovering problems
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Logic minimization techniques with applications to cryptology
- APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
- The complexity of finding harmless individuals in social networks
- Upper domination: complexity and approximation
- Approximability of identifying codes and locating-dominating codes
- Approximation algorithms for NMR spectral peak assignment.
- scientific article; zbMATH DE number 3902037 (Why is no real title available?)
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Interactive and probabilistic proof-checking
- Algorithmic aspects of total Roman and total double Roman domination in graphs
- The approximability of the weighted Hamiltonian path completion problem on a tree
This page was built for publication: Optimization, approximation, and complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186548)
