Théorème de Hall

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Dynamic Balanced Graph Partitioning

Georg Stefan Schmid, Andreas Loukas

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to servi ...

SIAM Publications2020

Stable Fractional Matchings

Aris Filos Ratsikas

We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). After observing that, in this cardinal setting, stable fractional matchings c ...

ASSOC COMPUTING MACHINERY2019

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

SPRINGER HEIDELBERG2018

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

Graph-based compression of dynamic 3D point cloud sequences

Pascal Frossard, Ntorina Thanou

This paper addresses the problem of compression of 3D point cloud sequences that are characterized by moving 3D positions and color attributes. As temporally successive point cloud frames are similar, motion estimation is key to effective compression of th ...

Institute of Electrical and Electronics Engineers2016

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 ...

National Academy of Sciences2014

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

Théorème de Hall

Graph Chatbot

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Dynamic Balanced Graph Partitioning

Stable Fractional Matchings

New Graph Algorithms via Polyhedral Techniques

The Sketching Complexity of Graph and Hypergraph Counting

Finding Perfect Matchings in Bipartite Hypergraphs

Partial Recovery Bounds for the Sparse Stochastic Block Model

Graph-based compression of dynamic 3D point cloud sequences

Exponentiality of the exchange algorithm for finding another room-partitioning

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

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Dynamic Balanced Graph Partitioning

Stable Fractional Matchings

New Graph Algorithms via Polyhedral Techniques

The Sketching Complexity of Graph and Hypergraph Counting

Finding Perfect Matchings in Bipartite Hypergraphs

Partial Recovery Bounds for the Sparse Stochastic Block Model

Graph-based compression of dynamic 3D point cloud sequences

Exponentiality of the exchange algorithm for finding another room-partitioning

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