Approximation of dense-n/2-subgraph and table compression problems
文献类型：期刊论文
| 作者 | Xu, DC; Han, JY; Du, DL |
| 刊名 | SCIENCE IN CHINA SERIES A-MATHEMATICS
 |
| 出版日期 | 2005-09-01 |
| 卷号 | 48期号:9页码:1223-1233 |
| 关键词 | dense-n/2-subgraph problem (DSP) table compression problem (TCP) SDP approximation ratio |
| ISSN号 | 1006-9283 |
| DOI | 10.1360/04ys0167 |
| 英文摘要 | We develop improved approximation algorithms for two NP-hard problems: the dense-n/2-subgraph and table compression. Based on SDP relaxation and advanced rounding techniques, we first propose 0.5982 and 0.5970-approximation algorithms respectively for the dense-n/2-subgraph problem (DSP) and the table compression problem (TCP). Then we improve these bounds to 0.6243 and 0.6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP relaxation. The results for TCP beat the 0.5 bound of a simple greedy algorithm on this problem, and hence answer an open question of Anderson in an affirmative way. |
| WOS研究方向 | Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000233073200006 |
| 出版者 | SCIENCE PRESS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/1881]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Xu, DC |
| 作者单位 | 1.Beijing Univ Technol, Coll Appl Sci, Beijing 100022, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Acad Math & Syst Sci, Beijing 100080, Peoples R China 3.Univ New Brunswick, Fac Adm, Fredericton, NB E3B 5A3, Canada |
| 推荐引用方式 GB/T 7714 | Xu, DC,Han, JY,Du, DL. Approximation of dense-n/2-subgraph and table compression problems[J]. SCIENCE IN CHINA SERIES A-MATHEMATICS,2005,48(9):1223-1233. |
| APA | Xu, DC,Han, JY,&Du, DL.(2005).Approximation of dense-n/2-subgraph and table compression problems.SCIENCE IN CHINA SERIES A-MATHEMATICS,48(9),1223-1233. |
| MLA | Xu, DC,et al."Approximation of dense-n/2-subgraph and table compression problems".SCIENCE IN CHINA SERIES A-MATHEMATICS 48.9(2005):1223-1233. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。