Q5091252
type: Item
instance of: scholarly article
author: Akbar Rafiey
author: Arash Rafiey
author: Thiago R. Santos
publication date: 2022-07-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1902.02201
Mathematics Subject Classification ID: 68Nxx
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7561584
zbMATH Keywords: approximation algorithms
zbMATH Keywords: minimum cost homomorphism
zbMATH Keywords: randomized rounding
MaRDI profile type: MaRDI publication profile
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Efficient enumeration for conjunctive queries over X-underbar structures
cites work: On chromatic sums and distributed resource allocation
cites work: Q4993594
cites work: Near-Unanimity Functions and Varieties of Reflexive Graphs
cites work: \(H\)-coloring dichotomy revisited
cites work: Complexity of conservative constraint satisfaction problems
cites work: Conservative constraint satisfaction re-revisited
cites work: Binarisation for valued constraint satisfaction problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Towards a characterization of constant-factor approximable finite-valued CSPs
cites work: Local distribution and the symmetry gap: approximability of multiway partitioning problems
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: Retractions to Pseudoforests
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Q4411283
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: A dichotomy for minimum cost graph homomorphisms
cites work: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
cites work: Level of repair analysis and minimum cost homomorphisms of graphs
cites work: Polynomial graph-colorings
cites work: Q4780787
cites work: Some optimal inapproximability results
cites work: Interval-like graphs and digraphs
cites work: Approximation of minimum cost homomorphisms
cites work: On the complexity of H-coloring
cites work: Q4828516
cites work: The dichotomy of list homomorphisms for digraphs
cites work: Monotone proper interval digraphs and Min-Max orderings
cites work: The dichotomy of minimum cost homomorphism problems for digraphs
cites work: Approximation Results for the Optimum Cost Chromatic Partition Problem
cites work: Coloring of trees with minimum sum of colors
cites work: Introduction to the Maximum Solution Problem
cites work: The approximability of constraint satisfaction problems
cites work: Q4737518
cites work: The \(C_{k}\)-extended graft construction
cites work: Approximation Algorithms for CSPs
cites work: On the approximation of minimum cost homomorphism to bipartite graphs
cites work: Q3549708
cites work: A dichotomy theorem for the general minimum cost homomorphism problem
cites work: The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
cites work: Computational complexity of the extended minimum cost homomorphism problem on three-element domains
DOI: 10.4230/LIPICS.ICALP.2019.91
Recommended article: \(H\)-coloring dichotomy revisited
Recommended article: Logical Approaches to Computational Barriers
Recommended article: Dichotomy for bounded degree \(H\)-colouring
Recommended article: Approximability Distance in the Space of H-Colourability Problems
Recommended article: A new proof of the \(H\)-coloring dichotomy
Recommended article: A Complexity Trichotomy for Approximately Counting List H -Colorings
Recommended article: Q4252044
Recommended article: On the complexity of H-coloring
Recommended article: Q3758852
Recommended article: A complexity trichotomy for approximately counting list \(H\)-colourings
description: scientific article; zbMATH DE number 7561584