scientific article; zbMATH DE number 1559516
From MaRDI portal
Publication:4526964
Recommendations
Cited in
(81)- A combinatorial algorithm for MAX CSP
- On approximating four covering and packing problems
- Complexity results for some global optimization problems
- A unified approximation algorithm for node-deletion problems
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- The computational complexity of some problems of linear algebra
- Semidefinite programming in combinatorial optimization
- On the difficulty of approximately maximizing agreements.
- Worst-case study of local search for MAX-\(k\)-SAT.
- On the hardness of efficiently approximating maximal non-\(L\) submatrices.
- On the limits of nonapproximability of lattice problems
- Interactive and probabilistic proof-checking
- Approximating minimum feedback vertex sets in hypergraphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- A note on approximating Max-Bisection on regular graphs
- The computational complexity of densest region detection
- On bounded occurrence constraint satisfaction
- The hardness of placing street names in a Manhattan type map
- Maximally stable Gaussian partitions with discrete applications
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- MAX3SAT is exponentially hard to approximate if NP has positive dimension.
- On weighted vs unweighted versions of combinatorial optimization problems
- The nonapproximability of OBDD minimization
- Recognizing DNA graphs is difficult.
- On local search for the generalized graph coloring problem
- Maximum gap labelings of graphs
- Max NP-completeness made easy
- Improved non-approximability results for minimum vertex cover with density constraints
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- An approximation of the minimum vertex cover in a graph
- Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
- Gaussian bounds for noise correlation of resilient functions
- Lemmings is PSPACE-complete
- Tree-edges deletion problems with bounded diameter obstruction sets
- On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost
- Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
- A multiple penalty function method for solving max-bisection problems
- Inoculation strategies for victims of viruses and the sum-of-squares partition problem
- On a class of optimization problems with no ``efficiently computable solution
- 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
- k-SAT Is No Harder Than Decision-Unique-k-SAT
- Local search to approximate MAX NAE-k-SAT tightly
- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- Gadgets, Approximation, and Linear Programming
- On the optimality of the random hyperplane rounding technique for MAX CUT
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Some recent strong inapproximability results
- Approximating Max NAE-\(k\)-SAT by anonymous local search
- Separating sets of strings by finding matching patterns is almost always hard
- Inapproximability Results for Computational Problems on Lattices
- Definable inapproximability: new challenges for duplicator
- Near optimal bounds in Freiman's theorem
- Some optimal inapproximability results
- A new Lagrangian net algorithm for solving max-bisection problems
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- On ε‐biased generators in NC0
- On approximating minimum vertex cover for graphs with perfect matching
- scientific article; zbMATH DE number 7053310 (Why is no real title available?)
- Semidefinite programming and combinatorial optimization
- Maximizing agreements with one-sided error with applications to heuristic learning
- Maximizing agreements with one-sided error with applications to heuristic learning
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Complexity classification of some edge modification problems
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Max-Cut via Kuramoto-Type Oscillators
- On the NP-hardness approximation curve for Max-2Lin(2)
- Pseudo-Boolean optimization
- Project scheduling with irregular costs: complexity, approximability, and algorithms
- Finding an optimal alphabet ordering for Lyndon factorization is hard
- Triangles improve 0.878 approximation for Maxcut
- Shunting minimal rail car allocation
- Maximizing agreements and coagnostic learning
- On short paths interdiction problems: Total and node-wise limited interdiction
- Dominance guarantees for above-average solutions
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4526964)
