MPI-INF Logo
Campus Event Calendar
  • Home
  • Campus Event Calendar

Event Entry

What and Who

Graph coalition partitions that are optimal under social welfare

Liana Khazaliya
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Thursday, 25 February 2021
13:00
30 Minutes
Virtual talk
Virtual talk
Saarbrücken

Abstract

We consider a problem of the coalition game, where the utility of each member of the coalition depends in some terms on his closeness to the rest of the coalition members. We are interested in obtaining the partition for which the maximum of a target value (i.e. social welfare) is reached. Upper and lower bounds on social welfare value, optimal partitions for several cases and a polynomial algorithm for finding the optimal partition for the tree case, as well as the NP-hardness of the problem for 4-regular graphs have been recently shown.


In the seminar, we discuss the problem in the context of parameterized complexity. Namely, we suggest an algorithm parameterized by tree-width for optimal partitioning with a restriction on the size of the coalition. Then we will explain an exact exponential algorithm and several general graph-theoretical results for the considered problem.

------------------------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Contact

Sándor Kisfaludi-Bak
--email hidden
passcode not visible
logged in users only
Login for more details

Tags, Category, Keywords and additional notes

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak, 02/19/2021 10:13
Sándor Kisfaludi-Bak, 02/15/2021 09:52
Sándor Kisfaludi-Bak, 02/13/2021 13:58 -- Created document.