Rounding-based moves for semi-metric labeling
Semi-metric labeling is a special case of energy minimization for pairwise Markov random fields. The energy function consists of arbitrary unary potentials, and pairwise potentials that are proportional to a given semi-metric distance function over the label set. Popular methods for solving semi-met...
| Autors principals: | , |
|---|---|
| Format: | Journal article |
| Publicat: |
MIT Press
2016
|
| _version_ | 1826259092036911104 |
|---|---|
| author | Kumar, M Dokania, P |
| author_facet | Kumar, M Dokania, P |
| author_sort | Kumar, M |
| collection | OXFORD |
| description | Semi-metric labeling is a special case of energy minimization for pairwise Markov random fields. The energy function consists of arbitrary unary potentials, and pairwise potentials that are proportional to a given semi-metric distance function over the label set. Popular methods for solving semi-metric labeling include (i) move-making algorithms, which iteratively solve a minimum st-cut problem; and (ii) the linear programming (LP) relaxation based approach. In order to convert the fractional solution of the LP relaxation to an integer solution, several randomized rounding procedures have been developed in the literature. We consider a large class of parallel rounding procedures, and design move-making algorithms that closely mimic them. We prove that the multiplicative bound of a move-making algorithm exactly matches the approximation factor of the corresponding rounding procedure for any arbitrary distance function. Our analysis includes all known results for move-making algorithms as special cases. |
| first_indexed | 2024-03-06T18:44:24Z |
| format | Journal article |
| id | oxford-uuid:0e030714-1c3b-4672-9460-21591ad281ca |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:44:24Z |
| publishDate | 2016 |
| publisher | MIT Press |
| record_format | dspace |
| spelling | oxford-uuid:0e030714-1c3b-4672-9460-21591ad281ca2022-03-26T09:43:33ZRounding-based moves for semi-metric labelingJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0e030714-1c3b-4672-9460-21591ad281caSymplectic Elements at OxfordMIT Press2016Kumar, MDokania, PSemi-metric labeling is a special case of energy minimization for pairwise Markov random fields. The energy function consists of arbitrary unary potentials, and pairwise potentials that are proportional to a given semi-metric distance function over the label set. Popular methods for solving semi-metric labeling include (i) move-making algorithms, which iteratively solve a minimum st-cut problem; and (ii) the linear programming (LP) relaxation based approach. In order to convert the fractional solution of the LP relaxation to an integer solution, several randomized rounding procedures have been developed in the literature. We consider a large class of parallel rounding procedures, and design move-making algorithms that closely mimic them. We prove that the multiplicative bound of a move-making algorithm exactly matches the approximation factor of the corresponding rounding procedure for any arbitrary distance function. Our analysis includes all known results for move-making algorithms as special cases. |
| spellingShingle | Kumar, M Dokania, P Rounding-based moves for semi-metric labeling |
| title | Rounding-based moves for semi-metric labeling |
| title_full | Rounding-based moves for semi-metric labeling |
| title_fullStr | Rounding-based moves for semi-metric labeling |
| title_full_unstemmed | Rounding-based moves for semi-metric labeling |
| title_short | Rounding-based moves for semi-metric labeling |
| title_sort | rounding based moves for semi metric labeling |
| work_keys_str_mv | AT kumarm roundingbasedmovesforsemimetriclabeling AT dokaniap roundingbasedmovesforsemimetriclabeling |