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-approxi...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.展开更多
文摘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.
