Back to search

Institutes outside Greece

Optimization problems in network mechanism design

Abstract

dc:description

We study approximation algorithms and design truthful mechanisms for optimization problems in networks that have direct applications in smart cities and urban planning. We present new models and new techniques which could be of independent interest. More specifically, in Chapter 2 we introduce a new model for pollution control and propose two applications of this model. This is the first time this problem is studied from the computational perspective. The network is represented by a graph where nodes are the pollutants and edges between pollutants represent the effect of spread of pollution. The government sets bounds on the levels of emitted pollution in both local areas and the whole network. We mainly study the classes of planar graphs and trees which model air and water pollution and design truthful approximate mechanisms. In Chapter 3 we introduce a new mechanism design model for a new model for the budgeted maximum lifetime coverage (BMLC) in wireless sensor networks (wsns). BMLC generalizes the known maximum lifetime coverage problem to the case where sensors are owned by selfish agents, where each agent has a private cost per unit time of how much to be paid for deploying his sensor. We introduce a random instances model for BMLC and design a novel approximate mechanism by reducing BMLC to the fractional knapsack which is truthful under some technical assumptions. For a closely related minimum coverage problem in wsns on unit disk graphs, we generalize a recent PTAS for this problem to obtain a truthful PTAS for the problem where sensors' costs are agents' private data. In Chapter 4 we study approximation algorithms which are based on the primal dual method for network connectivity problems. We then prove that these algorithms are monotone and thus can lead to truthful mechanisms. Finally in Chapter 5 we study the problem of facility location on the real line under non utilitarian objective functions. We extend previous models and derive inapproximability bounds for deterministic and randomized truthful mechanisms. As a byproduct we show that the same approximation guarantees hold for the social utility objective.

Degree

thesis:*
Grantor dc:publisher
Institutes outside Greece
Year dc:date
2016

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Anastasiadis, Eleftherios
  • Αναστασιάδης, Ελευθέριος

Subjects

dc:subject × 10

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/57268

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Anastasiadis, Eleftherios; Αναστασιάδης, Ελευθέριος. Optimization problems in network mechanism design. Institutes outside Greece, 2016. http://hdl.handle.net/10442/hedi/57268