Publication

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Related publications (37)

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.

Minimum d-blockers and d-transversals in graphs

Dominique de Werra

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...

2011

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

Sparse Image Restoration Using Iterated Linear Expansion of Thresholds

Thierry Blu, Hanjie Pan

We focus on image restoration that consists in regularizing a quadratic data-fidelity term with the standard l1 sparse-enforcing norm. We propose a novel algorithmic approach to solve this optimization problem. Our idea amounts to approximating the result ...

2011

Hypergraphic LP Relaxations for Steiner Trees

David Pritchard

We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this ...

Springer2010

Blockers and transversals

Dominique de Werra, Bernard Ries, Rico Zenklusen

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

2009

A Magnetic Procedure for the Stability Number

Dominique de Werra

A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new verte ...

2009

Parity-regular Steinhaus graphs

Maxime Augier

Steinhaus graphs on n vertices are certain simple graphs in bijective correspondence with binary {0,1}-sequences of length n-1. A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic ...

American Mathematical Society2008

Robust Routing for Dynamic Wireless Networks Based on Stable Embeddings

Matthias Grossglauser, Suhas Diggavi, Dominique Florian Tschopp, Jörg Widmer

Routing packets is a central function of multi-hop wireless networks. Traditionally, there have been two paradigms for routing, either based on the geographical coordinates of the nodes (geographic routing), or based on the connectivity graph (topology-bas ...

2007

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

A heuristic for nonlinear global optimization relevant to discrete choice models estimation

Michel Bierlaire, Michaël Clément Louis Ghislain Thémans, Nicolas Zufferey

In most applications related to transportation, it is of major importance to be able to identify the global optimum of the associated optimization problem. The work we present in this paper is motivated by the optimization problems arising in the maximum l ...

2007