|
|||||
|
|
| Approximation of dense-n/2-subgraph and table compression problems | |
| 作者姓名： | XU Dachuan~ HAN Jiye~ & DU Dongle~ . College of Applied Sciences Beijing University of Technology Beijing China . Institute of Applied Mathematics Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing China . Faculty of Administration University of New Brunswick P.O.Box Fredericton NB EB A Canada |
| 作者单位： | XU Dachuan~1 HAN Jiye~2 & DU Dongle~3 1. College of Applied Sciences，Beijing University of Technology，Beijing 100022，China; 2. Institute of Applied Mathematics，Academy of Mathematics and Systems Science，Chinese Academy of Sciences，Beijing 100080，China; 3. Faculty of Administration，University of New Brunswick，P.O.Box 4400，Fredericton，NB E3B 5A3，Canada |
| 基金项目： | The first author's work was supported by NNSF of China，北京工业大学校科研和教改项目，国家自然科学基金，The third author's work was supported by NSERC |
| 摘 要： | 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 respec- tively 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. |
Approximation of dense-n/2-subgraph and table compression problems |
|
| XU Dachuan HAN Jiye & DU Dongle . College of Applied Sciences,Beijing University of Technology,Beijing ,China, . Institute of Applied Mathematics,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing ,China, . Faculty of Administration,University of New Brunswick,P.O.Box ,Fredericton,NB EB A,Canada.Approximation of dense-n/2-subgraph and table compression problems[J].Science in China(Mathematics),2005,48(9). | |
| Authors: | XU Dachuan HAN Jiye DU Donglei |
| Institution: | 1. College of Applied Sciences, Beijing University of Technology, Beijing 100022, China 2. Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China 3. Faculty of Administration, University of New Brunswick,P.O. Box 4400, Fredericton, NB E3B 5A3, Canada |
| Abstract: | 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 respec- tively 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. |
| Keywords: | dense-n/2-subgraph problem(DSP) table compression problem(TCP) SDP approximation ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |