Chen, Shahar ;
Di Castro, Dotan ;
Karnin, Zohar ;
LewinEytan, Liane ;
Naor, Joseph (Seffi) ;
Schwartz, Roy
Correlated Rounding of Multiple Uniform Matroids and MultiLabel Classification
Abstract
We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multilabel classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multilabel classification problem, the metric multilabeling problem, which captures the above applications. We present a (true) O(log{k})approximation for the general case of metric multilabeling and a tight 2approximation for the special case where there is no limit on the number of labels that can be assigned to an object.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2017:7461,
author = {Shahar Chen and Dotan Di Castro and Zohar Karnin and Liane LewinEytan and Joseph (Seffi) Naor and Roy Schwartz},
title = {{Correlated Rounding of Multiple Uniform Matroids and MultiLabel Classification}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {34:134:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7461},
URN = {urn:nbn:de:0030drops74612},
doi = {10.4230/LIPIcs.ICALP.2017.34},
annote = {Keywords: approximation algorithms, randomized rounding, dependent rounding, metric labeling, classification}
}
2017
Keywords: 

approximation algorithms, randomized rounding, dependent rounding, metric labeling, classification 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 