Nguyễn Kim Thắng
Assistant Professor
IBISC,
University Evry Val d'Essonne.
Email: thang (at) ibisc (dot) fr
Sabbatical: I am on sabbatical for the 20172018 academic year at ENS Ulm, in
Algorithms group.
Research interests: Design and Analysis of Algorithms, Algorithmic Game Theory.
ANR Project: Online Algorithms beyond Traditional Approaches
Publications:

Approximating kForest with Resource Augmentation: A PrimalDual Approach
Eric Angel, Nguyen Kim Thang, Shikha Singh.
Conference on Combinatorial Optimization and Applications, 2017

Tropical Path in VertexColored Graphs.
Johanne Cohen, Giuseppe F. Italiano, Yannis Manoussakis,
Nguyen Kim Thang, Pham Hong Phong.
Conference on Combinatorial Optimization and Applications, 2017

Online Nonpreemptive Scheduling in a Resource Augmentation Model based on Duality
[Paper]
Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, Denis Trystram
European Symposium on Algorithms (ESA), 2016

Online Algorithms for MultiLevel Aggregation
[Paper]
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr,
Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý
European Symposium on Algorithms (ESA), 2016

Lagrangian Duality based Algorithms in Online EnergyEfficient Scheduling
[Paper]
Nguyen Kim Thang
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2016

The LocalGlobal Conjecture for Scheduling with NonLinear Cost
[Paper]
Nikhil Bansal, Christoph Dürr, Nguyen Kim Thang, Oscar C. Vasquez
Journal of Scheduling

Primaldual and dualfitting analysis of online scheduling algorithms for generalized flowtime problems
[Paper]
Spyros Angelopoulos, Giorgio Lucarelli, Nguyen Kim Thang
European Symposium on Algorithms (ESA), 2015.

Nonpreemptive Throughput Maximization for SpeedScaling with PowerDown
[Paper]
Eric Angel, Evripidis Bampis, Vincent Chau, Nguyen Kim Thang
Conference on Parallel and Distributed Computing (Europar), 2015.

Throughput Maximization in Multiprocessor SpeedScaling
[Paper]
Eric Angel, Evripidis Bampis, Vincent Chau, Nguyen Kim Thang
Symposium on Algorithms and Computation (ISAAC), 2014.

Lagrangian Duality in Online Scheduling with
Resource Augmentation and Speed Scaling
[Paper]
[Abstract]
[Slides]
[BibTex]
Nguyen Kim Thang
European Symposium on Algorithms (ESA), 2013.

Improved Local Search for Universal Facility Location
[Paper]
[Abstract]
[Slides]
[BibTex]
Eric Angel, Nguyen Kim Thang, Damien Regnault
Journal of Combinatorial Optimization 29(1): 237246 (2015)
Conference on Computing and Combinatorics (COCOON), 2013.

Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games
[Paper]
[Abstract]
[Slides]
[BibTex]
Johanne Cohen, Christoph Dürr, Nguyen Kim Thang
Workshop on Internet and Network Economics (WINE), 2012.

Congestion Games with Capacitated Resources
[Paper]
[Abstract]
[Slides]
[BibTex]
Laurent Gourves, Jerome Monnot, Stefano Moretti, Nguyen Kim Thang
Symposium of Algorithmic Game Theory (SAGT), 2012.

Strategyproof Mechanisms for Facility Location Games with Many Facilities
[Paper]
[Abstract]
[Slides]
[BibTex]
Bruno Escoffier, Laurent Gourves, Nguyen Kim Thang, Fanny Pascual, Olivier Spanjaard
International Conference on Algorithmic Decision Theory (ADT), 2011.
This paper is devoted to the location of public facilities in a metric space. Selfish agents are located in this metric space, and their aim to minimize their own cost, which is the distance from their location to the nearest facility. A central authority has to locate the facilities in the space, but she is ignorant of the true locations of the agents. The agents will therefore report their locations, but they may lie if they have an incentive to do it. We consider two social costs in this paper: the sum of the distances of the agents to their nearest facility, or the maximal distance of an agent to her nearest facility. We are interested in designing strategyproof mechanisms that have a small approximation ratio for the considered social cost. A mechanism is strategyproof if no agent has an incentive to report false information. This setting has been previously studied for extreme cases where one and two facilities are to be opened. In this paper, we consider the other extreme case: given n agents, we wish to design strategyproof mechanisms to locate n1 facilities. We study this problem in the general metric and in the tree metric spaces. We provide lower and upper bounds on the approximation ratio of deterministic and randomized strategyproof mechanisms. Our work could be considered as one step toward
the general case.

Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs
[Paper]
[Abstract]
[Slides]
[BibTex]
Nguyen Kim Thang
International Computer Science Symposium in Russia (CSR), 2011.
Motivated by issues raised from data broadcast and networks using ATM and TCP/IP, we consider
an online scheduling problem on a single machine. In the problem,
each job i is revealed at release time r_{i},
has processing time p_{i}, deadline d_{i} and
weight w_{i}. Preemption is allowed and there are two
models of preemption: preemption with restart and preemption with resume.
The goal is to maximize the throughput  the total weight of all jobs completed on time. In the paper, we consider the problem
where all processing time of jobs are equal and present improved algorithms
which achieve 4.24competitive in both models
of preemption.
@inproceedings{Nguyen:ATM,
author = {Nguyen Kim Thang},
title = {Improved Online Scheduling in Maximizing Throughput of Equal
Length Jobs},
booktitle = {The 6th International Computer Science Symposium in Russia (CSR)},
year = {2011},
pages = {42944}
}

On (Group) StrategyProof Mechanism without Payment for Facility Location Games
[Paper]
[Abstract]
[Slides]
[BibTex]
Nguyen Kim Thang
Workshop on Internet and Network Economics (WINE), 2010.
We characterize the performance of strategyproof and groupstrategyproof social
choice rules, for placing a facility on the nodes of a metric network inhabited by N autonomous
selfinterested agents. Every agent owns a set of locations
and caters to minimization of its cost which is the total distance from the facility to its locations.
Agents may misreport their locations, so as to manipulate the outcome. A central authority
has a set of allowable locations where the facility could be opened. The authority
must devise a mechanism that, given the agents’ reports,
places the facility in an allowable location that
minimizes the utilitarian social cost  the sum of agents’ costs.
A mechanism is strategyproof (SP) if no agent may misreport its
locations and be better off; it is groupstrategyproof (GSP) if no coalition of agents benefits by
jointly misreporting their locations.
The requirement for (G)SP
in this setting makes optimum placement of the facility impossible and, therefore, we consider
approximation (G)SP mechanisms.
For SP mechanisms, we give a simple 3approximation randomized mechanism
and also provide asymptotic lower bounds for different variants.
For GSP mechanisms, a (2N+1)approximation deterministic GSP mechanism
is devised. Although the mechanism is simple,
we showed that it is asymptotically optimal up to a constant. Our
Ω(N^{1  ε})
lower bound that randomization cannot improve over the approximation factor achieved
by the deterministic mechanism, when GSP is required.
@inproceedings{Nguyen:(G)SP,
author = {Nguyen Kim Thang},
title = {On (Group) StrategyProof Mechanism without Payment for Facility Location Games},
booktitle = {The 6th workshop on Internet and Network Economics (WINE)},
year = {2010},
pages = {531538}
}

Tile Packing Tomography is NPhard
[Paper]
[Abstract]
[Slides]
[BibTex]
Marek Chrobak, Christoph Dürr, Flavio Guinez, Antoni Lozano, Nguyen Kim Thang
Algorithmica 64(2): 267278, 2012
Preliminary version appeared in International Computing and Combinatorics Conference (COCOON), 2010.
Discrete tomography deals with reconstructing finite spatial objects from lower
dimensional projections and has applications for example in timetable design.
In this paper we consider the problem of reconstructing a tile packing from
its row and column projections. It consists of disjoint copies of a fixed tile,
all contained in some rectangular grid. The projections tell how many cells are
covered by a tile in each row and column. How difficult is it to construct a
tile packing satisfying given projections? It was known to be solvable by a
greedy algorithm for bars (tiles of width or height 1), and NPhardness results
were known for some specific tiles. This paper shows that the problem is
NPhard whenever the tile is not a bar.
@inproceedings{ChrobakDurrGuinez:TilingTomography,
author = {Marek Chrobak, Christoph Durr, Flavio Guinez, Antoni Lozano, Nguyen Kim Thang},
title = {Tile Packing Tomography is NPhard},
booktitle = {The 16th International Computing and Combinatorics Conference},
year = {2010},
pages = {254263}
}

Online Scheduling of Bounded Length Jobs to Maximize Throughput
[Paper]
[Abstract]
[Slides]
[BibTex]
Christoph Dürr, Lukasz Jez, Nguyen Kim Thang
Journal of Scheduling 15(5): 653664, 2012
Preliminary version appeared in Workshop on Approximation and Online Algorithms (WAOA), 2009.
We consider an online scheduling problem, motivated by the issues
present at the joints of networks using ATM and TCP/IP. Namely,
IP packets have to broken down to small ATM cells and sent out
before their deadlines, but cells corresponding to different packets
can be interwoven.
More formally, we consider the online scheduling problem with
preemptions, where each job j is revealed at release time r_{j},
has processing time p_{j}, deadline d_{j}
and weight w_{j}.
A preempted job can be resumed at any time.
The goal is to maximize the total weight of all jobs completed on time.
Our main results are as follows: we prove that if all jobs have processing
time exactly k, the deterministic competitive ratio is between
2.598 and 5, and when the processing times are at most k,
the deterministic competitive ratio is Θ(k/logk).
@inproceedings{DurrJezNguyen:OnlineScheduling,
title = {Online Scheduling of Bounded Length Jobs to Maximize Throughput},
author = {Christoph Durr, Lukasz Jez, Nguyen Kim Thang},
year = {2009},
booktitle = {The 7th Workshop on Approximation and Online Algorithms (WAOA)},
pages = {116127}
}

Nonclairvoyant Scheduling Games
[Paper]
[Abstract]
[Slides]
[BibTex]
Johanne Cohen, Christoph Dürr, Nguyen Kim Thang
Theory of Computing Systems 49(1): 323, 2011
Preliminary version appeared in Symposium of Algorithm Game Theory (SAGT), 2009.
In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy – the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled.
Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness.
In this paper we study these socalled nonclairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using timemultiplexing, assigning each job an equal fraction of CPU time. For these models we study two important questions, the existence of Nash equilibria and the price of anarchy. We show under some restrictions that the game under RANDOM policy is a potential game for two unrelated machines but it is not for three or more; for uniform machines, we prove that the game under this policy always possesses a Nash equilibrium by using a novel potential function with respect to a refinement of bestresponse dynamic. Moreover, we show that the game under the EQUI policy is a potential game.
Next, we analyze the inefficiency of EQUI policy. Interestingly, the (strong) price of anarchy of EQUI, a nonclairvoyant policy, is asymptotically the same as that of the best strongly local policy – policies in which a machine may look at the processing time of jobs assigned to it. The result also indicates that knowledge of jobs’ characteristics is not necessarily needed.
@inproceedings{CohenDurrNguyen:SchedulingGames,
author = {Johanne Cohen, Christoph Durr and Nguyen Kim Thang},
title = {Nonclairvoyant Scheduling Games},
booktitle = {The 2nd International Symposium on Algorithmic Game Theory},
year = {2009},
pages = {135146}
}

NPhardness of pure Nash equilibrium in Scheduling and Connection Games
[Paper]
[Abstract]
[Slides]
[BibTex]
Nguyen Kim Thang
Theoretical Computer Science
Preliminary version appeared in Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2009.
We prove NPhardness of pure Nash equilibrium
for some problems of scheduling games and connection games.
The technique is standard: first, we construct a gadget without
the desired property and then embed it to a larger game which encodes a
NPhard problem in order to prove the complexity
of the desired property in a game. This technique is very efficient in proving
NPhardness for deciding the existence of Nash equilibria.
In the paper, we illustrate the efficiency of the technique in proving the
NPhardness of deciding the existence of pure
Nash equilibria of Matrix Scheduling Games and Weighted Connection Games.
Moreover, using the technique, we can settle the complexity not only of the
existence of equilibrium but also of the existence of good costsharing protocol.
@inproceedings{Nguyen:NPhard,
author = {Nguyen Kim Thang},
title = {NPhardness of Pure Nash Equilibrium in Scheduling and Connection
Games},
booktitle = {The 35th Conference on Current Trends in Theory and Practice of Computer Science},
year = {2009},
pages = {413424}
}

Nash Equilibria in Voronoi Games on Graphs
[Paper]
[Abstract]
[Slides]
[BibTex]
Christoph Dürr, Nguyen Kim Thang
European Symposium on Algorithms (ESA), 2007.
In this paper we study a game where every player is to choose a
vertex (facility) in a given undirected graph. All vertices
(customers) are then assigned to closest facilities and a player’s
payoff is the number of customers assigned to it. We show that
deciding the existence of a Nash equilibrium for a given graph is
NPhard. We also introduce a new measure,
the social cost discrepancy, defined as the ratio of the
costs between the worst and the best Nash equilibria. We show that
the social cost discrepancy in our game is Ω(√n/k)
and O(√kn), where n is the number of vertices and k
the number of players.
@inproceedings{DurrNguyen:VoronoiGames,
author = {Christoph Durr and Nguyen Kim Thang},
title = {Nash Equilibria in Voronoi Games on Graphs},
booktitle = {The 15th Annual European Symposium on Algorithms},
year = {2007},
pages = {1728}
}
Stage: Lagrangian Duality in Online Algorithms
Teaching:
Thesis:
Pure Equilibria: Existence and Inefficiency & Online Auction, Ecole Polytechnique, 2009 (description, talk)