Publications related to Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

Partial Recovery Bounds for the Sparse Stochastic Block Model

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities

\frac{a}{n}

and

\frac{b}{n}

respectively. We consider the ...

Ieee2016

Exponentiality of the exchange algorithm for finding another room-partitioning

Laura Sanità

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange ...

Elsevier Science Bv2014

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

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Michel Bierlaire, Bilal Farooq, Dimitrios Efthymiou, Paul Richard Anderson

The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...

Natl Acad Sciences2014

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

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

Large simplices determined by finite point sets

János Pach, Filip Moric

Given a set P of n points in ℝd, let d1 > d2 >...denote all distinct inter-point distances generated by point pairs in P. It was shown by Schur, Martini, Perles, and Kupitz that there is at most oned-dimensional regular simplex of edge length d1 whos ...

Springer-Verlag2013

The flip-graph of the 4-dimensional cube is connected

Lionel Pournin

Flip-graph connectedness is established here for the vertex set of the 4-dimensional cube. It is found as a consequence, that this vertex set admits 92487256 triangulations, partitioned into 247451 symmetry classes. ...

Springer-Verlag2013

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...

2013

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Graph Chatbot

Chat with Graph Search

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Partial Recovery Bounds for the Sparse Stochastic Block Model

Exponentiality of the exchange algorithm for finding another room-partitioning

Node-weighted network design and maximum sub-determinants

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

On the Performance of Percolation Graph Matching

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Large simplices determined by finite point sets

The flip-graph of the 4-dimensional cube is connected

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

On the Performance of Percolation Graph Matching

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Exponentiality of the exchange algorithm for finding another room-partitioning

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Partial Recovery Bounds for the Sparse Stochastic Block Model

Large simplices determined by finite point sets

The flip-graph of the 4-dimensional cube is connected

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Node-weighted network design and maximum sub-determinants