About: Fair Packing of Independent Sets

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Fair Packing of Independent Sets Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Fair Packing of Independent Sets
Creator	Chiarelli, Nina Krnc, Matjaž Milanič, Martin Pferschy, Ulrich Pivač, Nevena Schauer, Joachim
Source	PMC
abstract	In this work we add a graph theoretical perspective to a classical problem of fairly allocating indivisible items to several agents. Agents have different profit valuations of items and we allow an incompatibility relation between pairs of items described in terms of a conflict graph. Hence, every feasible allocation of items to the agents corresponds to a partial coloring, that is, a collection of pairwise disjoint independent sets. The sum of profits of vertices/items assigned to one color/agent should be optimized in a maxi-min sense. We derive complexity and algorithmic results for this problem, which is a generalization of the classical Partition and Independent Set problems. In particular, we show that the problem is strongly NP-complete in the classes of bipartite graphs and their line graphs, and solvable in pseudo-polynomial time in the classes of cocomparability graphs and biconvex bipartite graphs.
has issue date	2020-04-30(xsd:dateTime)
bibo:doi	10.1007/978-3-030-48966-3_12
has license	no-cc
sha1sum (hex)	a0b527c1fa15a06f1a5a47c42993469ae313aae6
schema:url	https://doi.org/10.1007/978-3-030-48966-3_12
resource representing a document's title	Fair Packing of Independent Sets
has PubMed Central identifier	PMC7254894
schema:publication	Combinatorial Algorithms
resource representing a document's body	covid:a0b527c1fa15a06f1a5a47c42993469ae313aae6#body_text
is schema:about of	named entity 'graphs' named entity 'vertices' named entity 'agents' named entity 'valuations' named entity 'BIPARTITE' named entity 'COMPLEXITY' named entity 'Independent Set' named entity 'graphs' named entity 'indivisible' named entity 'graph theoretical' named entity 'optimized' named entity 'complexity' named entity 'collection' named entity 'conflict graph' named entity 'Independent Set' named entity 'independent sets' named entity 'line graphs' named entity 'generalization' named entity 'k-coloring' named entity 'partition' named entity 'Algorithm' named entity 'NP-hard to approximate' named entity 'combinatorial optimization' named entity 'algorithm' named entity 'vertex' named entity 'strongly NP-hard' named entity 'algorithm' named entity 'vertices' named entity 'k-coloring' named entity 'pseudo-polynomial time' named entity '1/2' named entity 'graph theoretical' named entity 'vertex' named entity 'subset' named entity 'conflict graph' named entity 'Lemma 2' named entity 'Comparability graphs' named entity 'algorithm' named entity 'strongly NP-hard' named entity 'forbidden induced subgraph' named entity 'line graph' named entity 'Santa Claus' named entity 'k-coloring' named entity 'Clique problem' named entity 'combinatorial optimization' named entity 'inapproximability' named entity 'disjoint' named entity 'bipartite graphs' named entity 'vertices' named entity 'running time' named entity 'algorithm' named entity 'lower bound' named entity 'comparability graph' named entity 'weakly NP-hard' named entity 'integer' named entity 'conflict graph' named entity 'strongly polynomial time' named entity 'transitive orientation' named entity 'NP-complete' named entity 'k-dimensional' named entity 'pseudopolynomial' named entity 'bipartite' named entity 'vertex' named entity 'bipartite' named entity 'perfect matching' named entity 'weakly NP-hard' named entity 'vertices' named entity 'class G1' named entity 'special case' named entity 'running time' named entity 'bipartite graph' named entity 'utility function' named entity 'subset' named entity 'independent set problem' named entity 'vertices' named entity 'pseudo-polynomial time' named entity 'NP-complete' named entity 'vertices'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software