scientific article; zbMATH DE number 1256636

Publication date: 17 January 2002

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

Theory of programming languages (68N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (only showing first 100 items - show all)

On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ RNC-approximation algorithms for the steiner problem ⋮ Probabilistic proof systems — A survey ⋮ Improved approximations of independent sets in bounded-degree graphs ⋮ Recent results in hardness of approximation ⋮ Hard graphs for randomized subgraph exclusion algorithms ⋮ Some recent strong inapproximability results ⋮ Parallel and sequential approximation of shortest superstrings ⋮ The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix ⋮ On approximation properties of the Independent set problem for degree 3 graphs ⋮ Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles) ⋮ Interactive Oracle Proofs ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ On the longest circuit in an alterable digraph ⋮ Random walks on colored graphs ⋮ The complexity of approximating a nonlinear program ⋮ ZK-PCPs from leakage-resilient secret sharing ⋮ A constrained edit distance between unordered labeled trees ⋮ PALO: a probabilistic hill-climbing algorithm ⋮ NP-completeness: A retrospective ⋮ Checking properties of polynomials ⋮ The minimum color sum of bipartite graphs ⋮ A primal-dual approach to approximation of node-deletion problems for matroidal properties ⋮ Simulating BPP using a general weak random source ⋮ Approximation algorithms for tree alignment with a given phylogeny ⋮ A class of spectral bounds for max \(k\)-cut ⋮ On the approximability of some maximum spanning tree problems ⋮ Graph layout problems ⋮ Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties ⋮ Structure in approximation classes ⋮ Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms ⋮ A geometric approach to betweenness ⋮ Succinct classical verification of quantum computation ⋮ Unnamed Item ⋮ Approximating minimum keys and optimal substructure screens ⋮ Unnamed Item ⋮ Max NP-completeness made easy ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ Maximum renamable Horn sub-CNFs ⋮ Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP ⋮ The approximation of maximum subgraph problems ⋮ Polynomially bounded minimization problems which are hard to approximate ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ Multiway cuts in directed and node weighted graphs ⋮ Approximation algorithms for maximum cut with limited unbalance ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Metafinite model theory ⋮ MNP: A class of NP optimization problems ⋮ On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs ⋮ On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs ⋮ Minimization of decision trees is hard to approximate ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ A generalization of maximal independent sets ⋮ Reductions, completeness and the hardness of approximability ⋮ On approximating the longest path in a graph ⋮ On the approximability of the Steiner tree problem in phylogeny ⋮ The ferry cover problem ⋮ On maximum planar induced subgraphs ⋮ An approximation algorithm for alphabet indexing problem ⋮ Completeness in approximation classes beyond APX ⋮ A PTAS for the minimization of polynomials of fixed degree over the simplex ⋮ Partitioning problems in dense hypergraphs ⋮ Approximate evaluations of characteristic polynomials of Boolean functions ⋮ Hardness and methods to solve CLIQUE ⋮ Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles) ⋮ On the complexity of comparing evolutionary trees ⋮ Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits ⋮ Simple heuristics for unit disk graphs ⋮ Worst-case performance of approximation algorithms for tool management problems ⋮ Travelling on graphs with small highway dimension ⋮ Unnamed Item ⋮ A \(2^{|E|/4}\)-time algorithm for MAX-CUT ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ Randomness in distribution protocols ⋮ Lattice-Based SNARGs and Their Application to More Efficient Obfuscation ⋮ Primal-dual approximation algorithms for a packing-covering pair of problems ⋮ Annealed replication: A new heuristic for the maximum clique problem ⋮ The complexity of minimizing and learning OBDDs and FBDDs ⋮ The hardness of approximation: Gap location ⋮ A short note on the approximability of the maximum leaves spanning tree problem ⋮ A note on approximating graph genus ⋮ On the power of multi-prover interactive protocols ⋮ Theorems for a price: Tomorrow's semi-rigorous mathematical culture ⋮ The death of proof? Semi-rigorous mathematics? You've got to be kidding! ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ On the Steiner ratio in 3-space ⋮ Weighted fractional and integral \(k\)-matching in hypergraphs ⋮ On approximation algorithms for the minimum satisfiability problem ⋮ On an approximation measure founded on the links between optimization and polynomial approximation theory ⋮ Inferring a tree from walks ⋮ The hardness of approximate optima in lattices, codes, and systems of linear equations ⋮ On fixed-parameter tractability and approximability of NP optimization problems ⋮ Measure on \(P\): Strength of the notion ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ MNP: A class of NP optimization problems ⋮ Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function

This page was built for publication: