On Approximate MMS Allocations on Restricted Graph Classes

• URL: http://arxiv.org/abs/2508.06343v2
• Date: Thu, 14 Aug 2025 19:01:13 GMT
• Title: On Approximate MMS Allocations on Restricted Graph Classes
• Abstract summary: We study the problem of fair division of a set of indivisible goods with connectivity constraints.<n>It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist.<n>We show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.
• Score: 0.31457219084519
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.

Related papers

• Correlation Clustering with Random Partial Information [4.706621352211144]
  Correlation clustering is a fundamental unsupervised learning problem.<n>We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$.<n>We prove approximation guarantees that are substantially better than the bounds achievable for general graphs.
  arXiv  Detail & Related papers  (2026-08-17T09:22:22Z)
• Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions [0.0]
  Local complement is a graph operation which replaces the neighborhood of a chosen edge-complement with its edge-complement.<n> determining the size of the resulting equivalence classes is a challenging problem in general.<n>We extend these results by deriving explicit formulas for several broad families of distance-hereditary graphs.
  arXiv  Detail & Related papers  (2026-02-27T09:07:41Z)
• Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs [13.60873698530933]
  A graph that encodes its commutatitivity structure, i.e., by its frustration graph, provides a natural interface between graph theory and quantum information.<n>We call this class $hbar$-perfect, as it extends the class of perfect and $h$-perfect graphs.<n>We find efficient schemes for entanglement detection, a connection to the complexity of shadow tomography, tight uncertainty relations and a construction for computing good lower on ground state energies.
  arXiv  Detail & Related papers  (2025-11-17T16:05:28Z)
• Multi-View Graph Learning with Graph-Tuple [13.991938982402807]
  We introduce a multi-view graph-tuple framework for efficient Graph Neural Networks (GNNs)<n>Instead of a single graph, our graph-tuple framework partitions the graph into disjoint subgraphs, capturing primary local interactions and weaker, long-range connections.<n>We instantiate our framework on two scientific domains: molecular property prediction from feature-scarce Coulomb matrices and cosmological parameter inference from geometric point clouds.
  arXiv  Detail & Related papers  (2025-10-11T20:57:03Z)
• $σ$-Maximal Ancestral Graphs [1.6574413179773764]
  We introduce and study a class of graphical objects that we coin ''$sigma$-Maximal Ancestral Graphs'' (''$sigma$-MAGs'')<n>These graphical objects encode information about ancestral relations and d-separations of Directed Acyclic Graphs (DAGs)<n>We show how these graphs provide an abstract representation of Directed Graphs with latent (selection) variables, analogous to how MAGs represent DAGs.
  arXiv  Detail & Related papers  (2025-06-30T10:08:21Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  Learning correspondences aims to find correct correspondences from the initial correspondence set with an uneven correspondence distribution and a low inlier rate. Recent advances usually use graph neural networks (GNNs) to build a single type of graph or stack local graphs into the global one to complete the task. We propose MGNet to effectively combine multiple complementary graphs.
  arXiv  Detail & Related papers  (2024-01-10T07:58:44Z)
• M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering [57.947071423091415]
  We introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence. We develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-10-27T19:40:34Z)
• Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
  We take a perspective of taking limits of operators derived from graphs, such as the aggregation operation that makes up GNNs. Our results hold for dense and sparse graphs, and various notions of graph limits.
  arXiv  Detail & Related papers  (2023-06-07T15:04:58Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  We study the so-called emph$k$-core estimator, which outputs a correspondence that induces a large, common subgraph of both graphs. We specialize our general framework to derive new results on exact and partial recovery in correlated block models, correlated Chung-Lu geometric graphs, and correlated random graphs.
  arXiv  Detail & Related papers  (2023-02-10T18:21:35Z)
• Variational Graph Generator for Multi-View Graph Clustering [51.89092260088973]
  We propose Variational Graph Generator for Multi-View Graph Clustering (VGMGC)<n>This generator infers a reliable variational consensus graph based on a priori assumption over multiple graphs.<n>It embeds the inferred view-common graph and view-specific graphs together with features.
  arXiv  Detail & Related papers  (2022-10-13T13:19:51Z)
• Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
  We study the node classification problem in the hierarchical graph where a 'node' is a graph instance. We propose the Hierarchical Graph Mutual Information (HGMI) and present a way to compute HGMI with theoretical guarantee. We demonstrate the effectiveness of this hierarchical graph modeling and the proposed SEAL-CI method on text and social network data.
  arXiv  Detail & Related papers  (2022-06-11T04:05:29Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  We introduce a novel graph convolutional network (GCN) that explicitly disentangles intertwined relations encoded in a graph. FactorGCN takes a simple graph as input, and disentangles it into several factorized graphs. We evaluate the proposed FactorGCN both qualitatively and quantitatively on the synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-12T03:01:40Z)
• Few-Shot Learning on Graphs via Super-Classes based on Graph Spectral Measures [14.932318540666545]
  We study the problem of few shot graph classification in graph neural networks (GNNs) to recognize unseen classes, given limited labeled graph examples. We propose an approach where a probability measure is assigned to each graph based on the spectrum of the graphs normalized Laplacian.
  arXiv  Detail & Related papers  (2020-02-27T17:11:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.