An improved algorithm for the (n,3)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$(n, 3)$$\\end{document}-MaxSAT problem: asking branchings to satisfy the clauses - 成果

首页 > 成果 > 详情

An improved algorithm for the (n,3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n, 3)$$\end{document}-MaxSAT problem: asking branchings to satisfy the clauses

认领

导出

Link by DOI

反馈

作者信息关键词期刊信息会议信息基础信息归属信息摘要

成果类型：

期刊论文、会议论文

作者：

Xu, Chao;Li, Wenjun;Wang, Jianxin;Yang, Yongjie*

通讯作者：

Yang, Yongjie

作者机构：

[Yang, Yongjie; Xu, Chao; Wang, Jianxin] Cent South Univ, Sch Comp Sci & Engn, Changsha, Peoples R China.

[Li, Wenjun] Changsha Univ Sci & Technol, Hunan Prov Key Lab Intelligent Proc Big Data Tran, Changsha, Peoples R China.

[Yang, Yongjie] Saarland Univ, Econ Theory, Saarbrucken, Germany.

通讯机构：

[Yang, Yongjie] C

[Yang, Yongjie] S

Cent South Univ, Sch Comp Sci & Engn, Changsha, Peoples R China.

Saarland Univ, Econ Theory, Saarbrucken, Germany.

语种：

英文

关键词：

CNF formula;3-SAT;Branching algorithm;Complexity;Parameterized complexity

期刊：

Journal of Combinatorial Optimization

ISSN：

1382-6905

年：

2021

卷：

期：

页码：

524-542

会议名称：

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

会议时间：

DEC 16-18, 2017

会议地点：

Shanghai, PEOPLES R CHINA

会议主办单位：

[Xu, Chao;Wang, Jianxin;Yang, Yongjie] Cent South Univ, Sch Comp Sci & Engn, Changsha, Peoples R China.^[Li, Wenjun] Changsha Univ Sci & Technol, Hunan Prov Key Lab Intelligent Proc Big Data Tran, Changsha, Peoples R China.^[Yang, Yongjie] Saarland Univ, Econ Theory, Saarbrucken, Germany.

会议赞助商：

Shanghai Jiao Tong Univ, Adv Network Lab, Nanjing Univ, GPS Lab, Shanghai Univ Finance & Econ, Res Inst Interdisciplinary Sci, Cardinal Operat Co

出版地：

VAN GODEWIJCKSTRAAT 30, 3311 GZ DORDRECHT, NETHERLANDS

出版者：

SPRINGER

DOI：

10.1007/s10878-019-00421-1

机构署名：

本校为其他机构

院系归属：

计算机与通信工程学院

摘要：

We study the (n,3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n, 3)$$\end{document}-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the (n,3)\documentclass[12pt]{minimal} \usepacka...

反馈

产权有误：本人成果被他人认领

数据有误：数据基本信息有误

归属有误：成果的院系归属、机构署名归属有误

其他原因：

验证码：

看不清楚，换一个

确定

取消

成果认领

标题：

用户	作者	通讯作者	--
	请选择	请选择	--

确定

取消

反馈

成果认领

提示

该栏目需要登录且有访问权限才可以访问