de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Statistical estimation for optimization problems on graphs

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons75754

Langovoy,  M.
Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons76142

Sra,  S.
Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Langovoy, M., & Sra, S. (2011). Statistical estimation for optimization problems on graphs. In NIPS Workshop on Discrete Optimization in Machine Learning (DISCML) 2011: Uncertainty, Generalization and Feedback (pp. 1-6).


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0010-4BF2-F
Zusammenfassung
Large graphs abound in machine learning, data mining, and several related areas. A useful step towards analyzing such graphs is that of obtaining certain summary statistics — e.g., or the expected length of a shortest path between two nodes, or the expected weight of a minimum spanning tree of the graph, etc. These statistics provide insight into the structure of a graph, and they can help predict global properties of a graph. Motivated thus, we propose to study statistical properties of structured subgraphs (of a given graph), in particular, to estimate the expected objective function value of a combinatorial optimization problem over these subgraphs. The general task is very difficult, if not unsolvable; so for concreteness we describe a more specific statistical estimation problem based on spanning trees. We hope that our position paper encourages others to also study other types of graphical structures for which one can prove nontrivial statistical estimates.