About a problem on real time scheduling and control

Event Date: Jun 20, 2018 in AGCO, Seminars

Abstract: Certain control computations require to be co-scheduled, each of which is allowed to be skipped occasionally. This may be modeled as periodic tasks with the correctness requirement that for each one, the fraction of jobs that complete execution should be at least some specified value between zero and one. I will show you two different real time scheduling models to formalize the problem, and derive approximation algorithms. Time permitting, I would also like to discuss about the model and solution strategies, and what other variants can be consider in order to capture different...

Read More

Negative Prices in Stackelberg Network Pricing Games.

Event Date: Jun 06, 2018 in AGCO, Seminars

Abstract: A Stackelberg network pricing game is a two-stage game, in which, in the first stage, a leader sets prices/tolls for a subset of edges so as to maximize profit (all other edges have a fixed cost), and, in the second stage, one or multiple followers choose a shortest path from their source to sink. Labbé et al. (1998) showed that finding optimal prices with lower bounds is NP-hard and gave an example in which profit is maximized by using negative prices. We explore this last phenomena and study the following two questions already posted in an open problem session of the AGCO...

Read More

On the equitable Hamiltonian Cycle problem

Event Date: May 16, 2018 in AGCO, Seminars

Abstract: Kinable, Smeulders, Delcour, and Spieksma (2017) introduced the Equitable TSP (E-TSP). In the E-TSP, we are given an even number of cities and distances between each pair of these. Instead of finding a tour of minimum length, Kinable et al. (uniquely) decomposed the tour in two perfect matchings, one with “even” edges and one with “odd” edges and the goal is to minimize the difference between the costs of the two perfect matchings. Kinable et al. show that the E-TSP is strongly NP-hard by reduction from Hamiltonian Cycle. The reduction resembles the reduction to show that TSP is...

Read More

Markets and Fair Division of Goods

Event Date: Jan 05, 2018 in AGCO, Seminars

Abstract: Items have to be distributed to agents in a fair manner. The agents have valuations for the goods and the value of a set of goods is simply the sum of the valuations. Nash introduced axioms for fairness and showed that for divisible goods maximizing the product of the agent’s valuations leads to a fair division. The allocation maximizing the product is the same as the allocation in a Fisher market in which all agents have the same budget. For indivisible goods the problem is harder. Cole/Gkatzelis gave an approximation algorithm based on rounding the allocation in a Fisher market...

Read More

Robust Submodular Maximization: Offline and Online algorithms

Event Date: Jan 03, 2018 in AGCO, Seminars

Abstract: In this work, we consider the robust submodular maximization problem subject to a matroid constraint in the offline and online setting. In the offline version, we are given a collection of k monotone submodular functions and matroid on a ground set of size n. The goal is to select one independent set that maximizes the minimum of the submodular functions. Given the complexity of the problem, we design a bi-criteria approximation algorithm that returns a set that is the union of a logarithmic number of independent sets. In the online version of the problem, we receive a new...

Read More

Markov Decision Processes with long duration

Event Date: Mar 14, 2018 in AGCO, Seminars

Abstract: In a Markov Decision Process (MDP), at each stage, knowing the current state, the decision-maker chooses an action, and receives a reward depending on the current state of the world. Then a new state is randomly drawn from a distribution depending on the action and on the past state. Many optimal payoffs concepts have been introduced to analyze the strategic aspects of MDPs with long duration: asymptotic value, uniform value, liminf average payoff criterion… We provide sufficient conditions under which these concepts coincide, and discuss some open problems. (Joint work with Xavier...

Read More