3 Search Results for "Takhanov, Rustem"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.19
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

Authors: Ian DeHaan, Neng Huang, and Euiwoong Lee

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language Γ which has the dual discriminator operation as a polymorphism, there exists a |D|-approximation algorithm for MinCostCSP(Γ) where D is the domain. Complementing our algorithmic result, we show that any constraint language Γ where MinCostCSP(Γ) admits a constant-factor approximation must have a near-unanimity (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP(Γ) has an NU polymorphism and is |D|-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.
Cite as

Ian DeHaan, Neng Huang, and Euiwoong Lee. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dehaan_et_al:LIPIcs.APPROX/RANDOM.2025.19,
  author =	{DeHaan, Ian and Huang, Neng and Lee, Euiwoong},
  title =	{{On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  URN =		{urn:nbn:de:0030-drops-243851},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  annote =	{Keywords: Constraint satisfaction problems, approximation algorithms, polymorphisms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.65
Hybrid VCSPs with Crisp and Valued Conservative Templates

Authors: Rustem Takhanov

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
A constraint satisfaction problem (CSP) is a problem of computing a homomorphism R -> G between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP(G), in which the right side structure G is fixed and the left side structure R is unconstrained. Recently, the hybrid setting, written CSP_H(G), where both sides are restricted simultaneously, attracted some attention. It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-template CSPs is the so called lifted language. Namely, this is a constraint language G_R that can be constructed from an input R. The tractability of the language G_R for any input R from H is a necessary condition for the tractability of the hybrid problem. In the first part we investigate templates G for which the latter condition is not only necessary, but also is sufficient. We call such templates G widely tractable. For this purpose, we construct from G a new finite relational structure G' and define a maximal structural restriction H_0 as a class of structures homomorphic to G'. For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSP_{H_0}(G). Our proof is based on the key observation that R is homomorphic to G' if and only if the core of G_R is preserved by a Siggers polymorphism. Analogous result is shown for conservative valued CSPs.
Cite as

Rustem Takhanov. Hybrid VCSPs with Crisp and Valued Conservative Templates. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{takhanov:LIPIcs.ISAAC.2017.65,
  author =	{Takhanov, Rustem},
  title =	{{Hybrid VCSPs with Crisp and Valued Conservative Templates}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.65},
  URN =		{urn:nbn:de:0030-drops-82474},
  doi =		{10.4230/LIPIcs.ISAAC.2017.65},
  annote =	{Keywords: constraint satisfaction problem, polymorphisms, algebraic approach, lifted language, hybrid CSPs, closed under inverse homomorphisms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2493
A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem

Authors: Rustem Takhanov

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
In the constraint satisfaction problem ($CSP$), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem ($MinHom$), one is additionally given weights $c_{va}$ for every variable $v$ and value $a$, and the aim is to find an assignment $f$ to the variables that minimizes $\sum_{v} c_{vf(v)}$. Let $MinHom\left( \Gamma \right)$ denote the $MinHom$ problem parameterized by the set of predicates allowed for constraints. $MinHom\left( \Gamma \right)$ is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that $MinHom\left( \Gamma \right)$ can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of $MinHom\left( \Gamma \right)$ for all choices of $\Gamma$. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].
Cite as

Rustem Takhanov. A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 657-668, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{takhanov:LIPIcs.STACS.2010.2493,
  author =	{Takhanov, Rustem},
  title =	{{A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{657--668},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2493},
  URN =		{urn:nbn:de:0030-drops-24936},
  doi =		{10.4230/LIPIcs.STACS.2010.2493},
  annote =	{Keywords: Minimum cost homomorphisms problem, relational clones, constraint satisfaction problem, perfect graphs, supervised learning}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2017
  • 1 2010

  • Refine by Author
  • 2 Takhanov, Rustem
  • 1 DeHaan, Ian
  • 1 Huang, Neng
  • 1 Lee, Euiwoong

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 2 constraint satisfaction problem
  • 2 polymorphisms
  • 1 Constraint satisfaction problems
  • 1 Minimum cost homomorphisms problem
  • 1 algebraic approach
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact