.png){kind=icon}
.png){kind=icon}
Return
An approximation algorithm for high-dimensional table compression on balanced K-partite graph
.png){kind=icon}
OA
AI
DOI：10.1016/j.compeleceng.2023.109048.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper considers the high-dimensional table compression problem on balanced k-partite graph. The objective is to choose half of the vertices from each of the k-partite to maximize the total weight of edges connecting the chosen vertices. Our main contribution is a 0.8785-approximation algorithm for the high-dimensional table compression problem by introducing the a-independent solutions through Lasserre semidefinite programming. This new algorithm improved two previous low-dimensional results, namely the 0.8731-approximation algorithm of Wu et al. for the one-dimensional case and the 0.6708-approximation of Xu and Du for the two-dimensional case.
Keywords:
Semidefinite programming
Lasserre hierarchy
Approximation algorithm
High-dimensional table compression
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.9
Papers:
6.7K
Citations:
1.3W
View more organizations