Improved parameterized algorithms for above average constraint satisfaction
type: Item
instance of: scholarly article
title: Improved Parameterized Algorithms for above Average Constraint Satisfaction
zbMATH Open document ID: 1352.68115
DOI: 10.1007/978-3-642-28050-4_10
published in: Parameterized and Exact Computation
publication date: 2012-06-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/1008.0213
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6046501
describes a project that uses: Outward rotations
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2108633592
cites work: Q5417644
cites work: A note on exact algorithms for vertex ordering problems on graphs
cites work: Kernelization: new upper and lower bound techniques
cites work: Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
cites work: Beating the random ordering is hard: every ordering CSP is approximation resistant
cites work: Approximating Bounded Occurrence Ordering CSPs
cites work: Betweenness parameterized above tight lower bound
cites work: A probabilistic approach to problems parameterized above or below tight bounds
cites work: All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
cites work: Some optimal inapproximability results
cites work: On the power of unique 2-prover 1-round games
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Parameterizing above or below guaranteed values
cites work: Q5710169
cites work: Q5302081
cites work: Confronting hardness using a hybrid approach
author: Eun Jung Kim
author: Ryan Williams
Recommended article: Parameterized constraint satisfaction problems: a survey
Recommended article: Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
Recommended article: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
Recommended article: Solving MAX-\(r\)-SAT above a tight lower bound
description: scientific article; zbMATH DE number 6046501