scientific article; zbMATH DE number 1559516

Publication date: 28 February 2001

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Related Items (71)

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 ⋮ Tree-edges deletion problems with bounded diameter obstruction sets ⋮ On the optimality of the random hyperplane rounding technique for MAX CUT ⋮ On a class of optimization problems with no ``efficiently computable solution ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ Some recent strong inapproximability results ⋮ Semidefinite programming in combinatorial optimization ⋮ A primal-dual approach to approximation of node-deletion problems for matroidal properties ⋮ On the difficulty of approximately maximizing agreements. ⋮ Max-Cut via Kuramoto-Type Oscillators ⋮ Maximum gap labelings of graphs ⋮ Worst-case study of local search for MAX-$k$-SAT. ⋮ On Nash-solvability in pure stationary strategies of the deterministic $n$-person games with perfect information and mean or total effective cost ⋮ On the hardness of efficiently approximating maximal non-$L$ submatrices. ⋮ Max NP-completeness made easy ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Dominance guarantees for above-average solutions ⋮ FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension ⋮ Approximating Max NAE-$k$-SAT by anonymous local search ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ Maximally stable Gaussian partitions with discrete applications ⋮ Semidefinite programming and combinatorial optimization ⋮ Pseudo-Boolean optimization ⋮ An approximation of the minimum vertex cover in a graph ⋮ A new Lagrangian net algorithm for solving max-bisection problems ⋮ A multiple penalty function method for solving max-bisection problems ⋮ Project scheduling with irregular costs: complexity, approximability, and algorithms ⋮ Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ Complexity classification of some edge modification problems ⋮ Polynomial time approximation schemes for dense instances of minimum constraint satisfaction ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ MAX SAT approximation beyond the limits of polynomial-time approximation ⋮ Inoculation strategies for victims of viruses and the sum-of-squares partition problem ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ A combinatorial algorithm for MAX CSP ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ On approximating four covering and packing problems ⋮ A unified approximation algorithm for node-deletion problems ⋮ k-SAT Is No Harder Than Decision-Unique-k-SAT ⋮ Complexity results for some global optimization problems ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ On ε‐biased generators in NC⁰ ⋮ 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}$ ⋮ Polynomial time approximation schemes for dense instances of $ \mathcal{NP}$-hard problems ⋮ MAX3SAT is exponentially hard to approximate if NP has positive dimension. ⋮ The computational complexity of some problems of linear algebra ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ The nonapproximability of OBDD minimization ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Lemmings is PSPACE-complete ⋮ 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 ⋮ Shunting minimal rail car allocation ⋮ The hardness of placing street names in a Manhattan type map ⋮ Recognizing DNA graphs is difficult. ⋮ On local search for the generalized graph coloring problem ⋮ Maximizing agreements and coagnostic learning

This page was built for publication: