The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always ...exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a (1- ε)-approximation for two agents, and a (8/9 - ε) -approximation for three agents. Apart from the extension to matroids, the (8/9 - ε) -approximation for three agents improves on a (7-8 - ε) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed.
Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for desirability of a committee, ...Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider five prominent extensions (responsive, downward lexicographic, upward lexicographic, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. For each of the preference extensions, we give a complete characterization of the complexity of testing Pareto optimality when preferences are dichotomous or linear. We also consider strategic issues: for four of the set extensions, we present a linear-time, Pareto optimal and strategyproof algorithm that even works for weak preferences.
•Extending a partial solution of an optimization problem occurs as a subproblem in many areas.•We propose a general framework for dealing with these extension problems.•We present several problems ...from different areas which can be expressed in this framework.•We show NP-hardness results and parameterized complexity results for the presented problems.
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G=(V,E), one usually arrives at the problem to decide for a vertex set U⊆V (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover S⊆V such that no proper subset of S is a vertex cover) with U⊆S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework.
In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP-complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP-completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework.
•We focus on Upper EDS, the problem of finding a minimal edge dominating set of maximum size in a given graph G = (V,E).•We show that Upper EDS is not approximable within a ratio of nϵ−12, for any ...ϵ∈(0,12), unless P = NP, where n = |V|.•For graphs of minimum degree at least 2, we show that Upper EDS is approximable within a ratio of 1/n.•We show that Upper EDS is APX-complete in bipartite graphs of maximum degree 4.
We study the problem of finding a minimal edge dominating set of maximum size in a given graph G=(V,E), called Upper EDS. We show that this problem is not approximable within a ratio of nε−12, for any ε∈(0,12), assuming P≠NP, where n=|V|. On the other hand, for graphs of minimum degree at least 2, we give an approximation algorithm with ratio 1n, matching this lower bound. We further show that Upper EDS is APX-complete in bipartite graphs of maximum degree 4, and NP-hard in planar bipartite graphs of maximum degree 4.
Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. While finding an arbitrary Pareto optimal allocation is generally easy, checking ...whether a particular allocation is Pareto optimal can be much more difficult. This problem is equivalent to checking that the allocated objects cannot be reallocated in such a way that at least one agent prefers her new allocation to her old one, and no agent prefers her old allocation to her new one. We consider the problem for two related types of preference relations over sets of objects. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over individual objects, and that their underlying preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.
Project games Bilò, Vittorio; Gourvès, Laurent; Monnot, Jérôme
Theoretical computer science,
01/2023, Volume:
940, Issue:
Part A
Journal Article
Peer reviewed
Open access
We consider a strategic game, called project game, where each agent has to choose a project among her own list of available projects. The model includes positive weights expressing the capacity of a ...given agent to contribute to a given project. The realization of a project produces some reward that has to be allocated to the agents. The reward of a realized project is fully allocated to its contributors according to a simple proportional rule. Existence and computational complexity of pure Nash equilibria is addressed and their efficiency is investigated according to both the utilitarian and the egalitarian social function.
We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems and generalizations thereof. Given a graph ...G=(V,E) and an edge set U⊆E, it is asked whether there exists an inclusion-wise minimal (or maximal, respectively) feasible solution E′ which satisfies a given property, for instance, being an edge dominating set (or a matching, respectively) and containing the forced edge set U (or avoiding any edges from the forbidden edge set E∖U, respectively). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation and inapproximability results.
•For given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions?•We determine the computational complexity of this and related problems for different values ...of d.•For d=3, the problem is related to Moore graphs and solvable in polynomial time.•For all d>4, the problem is NP-complete.•The NP-completeness results are proved for various values of the diameter of the input graph.
We study the following problem: for given integers d,k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d.
•Definition and study of the extension variants of the connected vertex cover problem (Ext-CVC), and of the Non-Separating Independent Set problem (Ext-NSIS).•Solvability and hardness results for ...Ext-CVC, notably in bipartite graphs of maximum degree 3 and in weakly triangulated graphs, applying also to Ext-NSIS.•Formulation of the concept of Price of Extension (PoE) as the approximation ratio for the problem Max Ext-CVC (resp., Min Ext-NSIS).•Lower bounds for PoE of Max Ext-CVC in general and bipartite graphs; proof that it is equal to 1 in chordal graphs, carrying over to Min Ext-NSIS.
We consider extension variants of Vertex Cover and Independent Set, following a line of research initiated in 10. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G=(V,E) and a vertex set U⊆V, does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S, such that U⊆S (respectively, U⊇S). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC, that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE), a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs.