Publication

Message-Passing Algorithms for Quadratic Minimization

Related publications (42)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Ya-Ping Hsieh, Ashkan Norouzi Fard, Abbas Bazzi, Marwa El Halabi

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream wi ...

2016

A block algorithm for computing antitriangular factorizations of symmetric matrices

Daniel Kressner, Zvonimir Bujanovic

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditio ...

Springer2016

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...

Springer-Verlag Berlin2014

Message-Passing Algorithms: Reparameterizations and Splittings

Nicholas Ruozzi

The max-product algorithm, a local message-passing scheme that attempts to compute the most probable assignment (MAP) of a given probability distribution, has been successfully employed as a method of approximate inference for applications arising in codin ...

Ieee-Inst Electrical Electronics Engineers Inc2013

On the Performance of Percolation Graph Matching

Matthias Grossglauser, Lyudmila Yartseva

Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...

ACM2013

Structural Analysis of Network Traffic Matrix via Relaxed Principal Component Pursuit

Xiaowen Dong, Zhe Wang, Ke Xu

The network traffic matrix is widely used in network operation and management. It is of crucial importance to analyze the composition and the structure of the network traffic matrix, for which some mathematical approaches such as Principal Component Analys ...

2012

The Truncated Tracial Moment Problem

Sabine Burgdorf

We present tracial analogs of the classical results of Curto and Fialkow on moment matrices. A sequence of real numbers indexed by words in noncommuting variables with values invariant under cyclic permutations of the indexes, is called a tracial sequence. ...

Theta Foundation2012

Information Processing and Structure of Dynamical Networks

Ali Ajdari Rad

Networks are everywhere and we are confronted with many networks in our daily life. Networks such as Internet, World Wide Web, social, biological and economical networks have been subject to extensive studies in the last decade. The volume of publications ...

EPFL2011

Content Preference Estimation In Online Social Networks: Message Passing Versus Sparse Reconstruction On Graphs

We design two different strategies for computing the unknown content preferences in an online social network based on a small set of nodes in the corresponding social graph for which this information is available ahead of time. The techniques take advantag ...

2011

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

. Then, we draw a connection to Goem ...

EPFL2014