# Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints

Xue Chen, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

Given a constraint satisfaction problem (CSP) on n variables, x1; x2; : : : ; xn 2 ( ±1), andmconstraints, a global cardinality constraint has the form of Pn i=1 xi = (1 2p)n, where p ∈ ((1); 1 (1)) and pn is an integer. Let AV G be the expected number of constraints satisfied by randomly choosing an assignment to x1; x2; : : : ; xn, complying with the global cardinality constraint. The CSP above average with the global cardinality constraint problem asks whether there is an assignment (complying with the cardinality constraint) that satisfies more than (AV G + t) constraints, where t is an input parameter. In this paper, we present an algorithm that finds a valid assignment satisfying more than (AV G + t) constraints (if there exists one) in time (2O(t2) + nO(d)). Therefore, the CSP above average with the global cardinality constraint problem is fixed-parameter tractable.

Original language English (US) 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 Philip N. Klein Association for Computing Machinery, 358-377 20 9781611974782 https://doi.org/10.1137/1.9781611974782.23 Published - Jan 1 2017 Yes 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, SpainDuration: Jan 16 2017 → Jan 19 2017

### Publication series

Name Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

### Other

Other 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 Spain Barcelona 1/16/17 → 1/19/17

## ASJC Scopus subject areas

• Software
• Mathematics(all)

## Fingerprint

Dive into the research topics of 'Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.77819026,"math_prob":0.6605187,"size":2707,"snap":"2022-27-2022-33","text_gpt3_token_len":746,"char_repetition_ratio":0.1572327,"word_repetition_ratio":0.71954024,"special_character_ratio":0.2958995,"punctuation_ratio":0.15594542,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96768993,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-11T12:58:50Z\",\"WARC-Record-ID\":\"<urn:uuid:b8a66ec8-eb26-4bf2-beb8-2022892256d4>\",\"Content-Length\":\"53225\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:099c6d4b-8b11-4372-a2e7-7442ffbc1bb2>\",\"WARC-Concurrent-To\":\"<urn:uuid:0d1718e6-f934-4d5b-8cf9-f0ca6498cf4f>\",\"WARC-IP-Address\":\"3.90.122.189\",\"WARC-Target-URI\":\"https://experts.illinois.edu/en/publications/parameterized-algorithms-for-constraint-satisfaction-problems-abo\",\"WARC-Payload-Digest\":\"sha1:73D6LCDPQTA5IA5OK2PN2GJC5MUDG6XI\",\"WARC-Block-Digest\":\"sha1:ODNRXX6UPQ54XEDQDTQHZPQZY6DVIM46\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882571284.54_warc_CC-MAIN-20220811103305-20220811133305-00086.warc.gz\"}"}