Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

Zi Xu (), Donglei Du () and Dachuan Xu ()
Additional contact information
Zi Xu: Shanghai University
Donglei Du: University of New Brunswick
Dachuan Xu: Beijing University of Technology

Journal of Combinatorial Optimization, 2014, vol. 27, issue 2, No 8, 315-327

Abstract: Abstract We consider the max-bisection problem and the disjoint 2-catalog segmentation problem, two well-known NP-hard combinatorial optimization problems. For the first problem, we apply the semidefinite programming (SDP) relaxation and the RPR2 technique of Feige and Langberg (J. Algorithms 60:1–23, 2006) to obtain a performance curve as a function of the ratio of the optimal SDP value over the total weight through finer analysis under the assumption of convexity of the RPR2 function. This ratio is shown to be in the range of [0.5,1]. The performance curve implies better approximation performance when this ratio is away from 0.92, corresponding to the lowest point on this curve with the currently best approximation ratio of 0.7031 due to Feige and Langberg (J. Algorithms 60:1–23, 2006). For the second problem, similar technique results in an approximation ratio of 0.7469, improving the previously best known result 0.7317 due to Wu et al. (J. Ind. Manag. Optim. 8:117–126, 2012).

Keywords: Max-bisection problem; 2-Catalog segmentation problem; Approximation algorithm; Semidefinite programming; RPR2 rounding (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9526-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:2:d:10.1007_s10878-012-9526-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9526-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().