2017-07-27 | Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints

2017-07-27   

Abstract

Given a constraint satisfaction problem (CSP) on n variables, x1,x2,…,xn∈{±1}, and m constraints, a global cardinality constraint has the form of ∑xi = (1−2p)n, where p∈(Ω(1),1−Ω(1)) and pn is an integer. Let AVG 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 (AVG+t) constraints, where t is an input parameter.


In this talk, we present an algorithm that finds a valid assignment satisfying more than (AVG+t) constraints (if there exists one) in time (2^O(t^2)+n^O(d)). Therefore, the CSP above average with the global cardinality constraint problem is fixed-parameter tractable.


Joint work with Xue Chen.

Time

2017年7月27日(周四)15:00 ~ 16:30  

Speaker

Yuan Zhou

Indiana University Bloomington

Room

信息管理与工程学院602室

上海财经大学

上海市杨浦区武东路100号