Publication

Constrained Binary Identification Problem

Related publications (76)

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.

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

Generalized Turan Problems For Even Cycles

Abhishek Methuku

Given a graph H and a set of graphs F, let ex(n, H, F) denote the maximum possible number of copies of H in an T-free graph on n vertices. We investigate the function ex(n, H, F), when H and members of F are cycles. Let C-k denote the cycle of length k and ...

2019

Graph Learning with Partial Observations: Role of Degree Concentration

Ali H. Sayed, Augusto José Rabelo Almeida Santos

In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections ...

IEEE2019

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

When Stuck, Flip a Coin

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

A graph learning approach for light field image compression

Touradj Ebrahimi, Pascal Frossard, Irene Viola, Hermina Petric Maretic

In recent years, light field imaging has attracted the attention of the academic and industrial communities thanks to its enhanced rendering capabilities that allow to visualise contents in a more immersive and interactive way. However, those enhanced capa ...

Spie-Int Soc Optical Engineering2018

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Nisheeth Vishnoi, Javad Ebrahimi Boroojeni, Damian Mateusz Straszak

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...

Ieee2017

Lower Bounds on Active Learning for Graphical Model Selection

Volkan Cevher, Jonathan Mark Scarlett

We consider the problem of estimating the underlying graph associated with a Markov random field, with the added twist that the decoding algorithm can iteratively choose which subsets of nodes to sample based on the previous samples, resulting in an active ...

2017

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by c ...

Association for Computing Machinery2017