Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size

• URL: http://arxiv.org/abs/2505.22384v1
• Date: Wed, 28 May 2025 14:11:14 GMT
• Title: Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
• Authors: Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos,
• Abstract summary: We study a version of this problem where each team must additionally be of bounded size.<n>Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded emphtreewidth) for small'' teams.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied \textsc{Coalition Formation} problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded \emph{treewidth}) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded \emph{vertex cover number}).

Related papers

• Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures [0.0]
  We study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework.<n>Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network.
  arXiv  Detail & Related papers  (2024-12-11T17:17:31Z)
• Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
  We present a framework for designing efficient algorithms for unsupervised learning problems. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise.
  arXiv  Detail & Related papers  (2023-11-13T12:26:25Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-09T02:33:36Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  Dynamic programming (DP) is an algorithmic design paradigm for the efficient, exact solution of intractable, problems. This paper presents a rigorous algebraic formalism for systematically deriving DP algorithms, based on semiring.
  arXiv  Detail & Related papers  (2021-07-05T00:51:02Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

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.