TY - GEN
T1 - New results for network pollution games
AU - Anastasiadis, Eleftherios
AU - Deng, Xiaotie
AU - Krysta, Piotr
AU - Li, Minming
AU - Qiao, Han
AU - Zhang, Jinshan
PY - 2016
Y1 - 2016
N2 - We study a newly introduced network model of the pollution control and design approximation algorithms and truthful mechanisms with objective to maximize the social welfare. On a high level, we are given a graph whose nodes represent the agents (sources of pollution), and edges between agents represent the effect of pollution spread. The government is responsible to maximize the social welfare while setting bounds on the levels of emitted pollution both locally and globally. We obtain a truthful in expectation FPTAS when the network is a tree (modelling water pollution) and a deterministic truthful 3-approximation mechanism. On planar networks (modelling air pollution) the previous result was a huge constant approximation algorithm. We design a PTAS with a small violation of local pollution constraints. We also design approximation algorithms for general networks with bounded degree. Our approximations are near best possible under appropriate complexity assumptions.
AB - We study a newly introduced network model of the pollution control and design approximation algorithms and truthful mechanisms with objective to maximize the social welfare. On a high level, we are given a graph whose nodes represent the agents (sources of pollution), and edges between agents represent the effect of pollution spread. The government is responsible to maximize the social welfare while setting bounds on the levels of emitted pollution both locally and globally. We obtain a truthful in expectation FPTAS when the network is a tree (modelling water pollution) and a deterministic truthful 3-approximation mechanism. On planar networks (modelling air pollution) the previous result was a huge constant approximation algorithm. We design a PTAS with a small violation of local pollution constraints. We also design approximation algorithms for general networks with bounded degree. Our approximations are near best possible under appropriate complexity assumptions.
KW - Algorithmic mechanism design
KW - Approximation algorithms
KW - Planar and tree networks
UR - http://www.scopus.com/inward/record.url?scp=84979207743&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84979207743&origin=recordpage
U2 - 10.1007/978-3-319-42634-1_4
DO - 10.1007/978-3-319-42634-1_4
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783319426334
VL - 9797
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 39
EP - 51
BT - Computing and Combinatorics
A2 - Dinh, Thang N.
A2 - Thai, My T.
PB - Springer Verlag
T2 - 22nd International Conference on Computing and Combinatorics, COCOON 2016
Y2 - 2 August 2016 through 4 August 2016
ER -
