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-approximat...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.展开更多
基金supported by NNSF of China(Grant Nos.10401038&10171108)Startup grant for doctoral research of Beijing University of Technology+1 种基金The second author's work was supported by NNSF of China(Grant Nos.10271002&70271014)The third author's work was supported by NSERC(Grant No.10004901)
文摘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.
