Polynomial time algorithms for ratio regions and a variant of normalized cut

Area of Science:

• Computer Science
• Image Processing
• Discrete Mathematics

Background:

• Partitioning, clustering, and grouping problems aim to group similar objects while ensuring distinctness and adequate size of groups.
• Ratio optimization problems, such as normalized cut and ratio regions, combine these objectives.

Purpose of the Study:

• To develop the first polynomial-time algorithms for optimally solving the ratio region problem and a variant of the normalized cut problem.
• To provide efficient, combinatorial alternatives to existing nonlinear, continuous, and computationally expensive spectral techniques in image segmentation.

Main Methods:

• The algorithms utilize a minimum s,t-cut procedure on a related graph of polynomial size as a subroutine.
• The approach is combinatorial, contrasting with traditional spectral methods in image segmentation.

Main Results:

• The study presents optimal polynomial-time solutions for the ratio region problem and a variant of the normalized cut problem.
• The algorithms are efficient and combinatorial, outperforming continuous spectral techniques in terms of computation and applicability to discrete problems.

Conclusions:

• The developed algorithms offer efficient and optimal solutions for critical ratio optimization problems in areas like image segmentation and data clustering.
• The combinatorial approach provides a more feasible and computationally advantageous method compared to existing spectral techniques.