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)- Cost minimization in wireless networks with a bounded and unbounded number of interfaces
- Exact algorithms and applications for tree-like Weighted Set Cover
- Polynomial time approximation schemes and parameterized complexity
- Revisiting the minimum breakpoint linearization problem
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Online admission control and embedding of service chains
- On the complexity of variations of mixed domination on graphs
- Approximability of scheduling problems with resource consuming jobs
- PCPs and the hardness of generating synthetic data
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Acyclic Matching in Some Subclasses of Graphs
- Improved approximations of independent sets in bounded-degree graphs
- Recent results in hardness of approximation
- A simple filter-and-fan approach to the facility location problem
- On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
- scientific article; zbMATH DE number 1496577 (Why is no real title available?)
- Approximation Classes for Real Number Optimization Problems
- The approximability of the weighted Hamiltonian path completion problem on a tree
- On the Hamming distance of constraint satisfaction problems.
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
- On Approximating an Implicit Cover Problem in Biology
- Assortment planning for multiple chain stores
- Classical symmetries and the quantum approximate optimization algorithm
- On the power of multi-prover interactive protocols
- On the hardness of range assignment problems
- Normal forms for second-order logic over finite structures, and classification of NP optimization problems
- Approximation algorithms for partial vertex covers in trees
- Roman \(\{3\}\)-domination in graphs: complexity and algorithms
- Approximating minimum feedback vertex sets in hypergraphs
- Double vertex-edge domination in graphs: complexity and algorithms
- On defensive alliances and strong global offensive alliances
- scientific article; zbMATH DE number 2230213 (Why is no real title available?)
- A note on the descriptive complexity of maximization problems
- Order Scheduling Models: Hardness and Algorithms
- Intractability of assembly sequencing: unit disks in the plane
- Combinatorial PCPs with short proofs
- Approximation algorithms for connected graph factors of minimum weight
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Some recent strong inapproximability results
- Complexities of efficient solutions of rectilinear polygon cover problems
- Reoptimization of max \(k\)-cover: approximation ratio threshold
- Metafinite model theory
- An improved lower bound on approximation algorithms for the closest substring problem
- On the approximability of some maximum spanning tree problems
- Orienting graphs to optimize reachability
- Power optimization for connectivity problems
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Deterministic and randomized polynomial‐time approximation of radii
- Algorithmic aspects of total Roman and total double Roman domination in graphs
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Optimization problems in multiple subtree graphs
- On the terminal Steiner tree problem.
- On parallel versus sequential approximation
- Partition into cliques for cubic graphs: Planar case, complexity and approximation
- Non-oblivious local search for graph and hypergraph coloring problems
- Complexity of majority monopoly and signed domination problems
- Max-leaves spanning tree is APX-hard for cubic graphs
- Parallel approximation of optimization problems
- A Logical Approach to Constraint Satisfaction
- Algorithmic aspect of minus domination on small-degree graphs
- Improved MAX SNP-hard results for finding an edit distance between unordered trees
- Limitations of semidefinite programs for separable states and entangled games
- Interactive and probabilistic proof-checking
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- Using fractional primal-dual to schedule split intervals with demands
- Combinatorial upper bounds for the smallest eigenvalue of a graph
- Reactive local search techniques for the maximum k-conjunctive constraint satisfaction problem (MAX-k-CCSP)
- APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
- On the complexity of finding emerging patterns
- Grothendieck’s Theorem, past and present
- Complexity and approximation ratio of semitotal domination in graphs
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- On fixed-parameter tractability and approximability of NP optimization problems
- The approximability of partial vertex covers in trees
- On Dinur’s proof of the PCP theorem
- The complexity of minimizing and learning OBDDs and FBDDs
- Derandomized parallel repetition via structured PCPs
- Maximizing business value by optimal assignment of jobs to resources in grid computing
- Improved approximation algorithms for MAX k-cut and MAX BISECTION
- Randomized approximation of bounded multicovering problems
- Finding a potential community in networks
- Finding a most parsimonious or likely tree in a network with respect to an alignment
- The task allocation problem with constant communication.
- Complexity of maximum cut on interval graphs
- Deciding the existence of a cherry-picking sequence is hard on two trees
- Pseudo-Boolean optimization
- Partial vertex cover and budgeted maximum coverage in bipartite graphs
- Minimal multicut and maximal integer multiflow: a survey
- A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
- On the approximability and hardness of minimum topic connected overlay and its special instances
- Tight lower bounds for certain parameterized NP-hard problems
- The full Steiner tree problem
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)
