scientific article; zbMATH DE number 1559516

Publication date: 28 February 2001

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

Related Items

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