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

Approximating Vector Scheduling

Event Date: Mar 21, 2018 in AGCO, Seminars

Abstract: In this talk we will consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in [0,1]^d, and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is n^{f(epsilon,d)}, where f(epsilon,d) = (1/epsilon)^{Õ(d)}, where Õ suppresses polylogarithmic terms in d. In...

Read More

Structural-based Approach to Complexity of Optimization Algorithms

Event Date: Mar 28, 2018 in AGCO, Seminars

Abstract: The past few decades have witnessed tremendous progress in the field of Mathematical Optimization which led to a large proliferation of new optimization methods to many scientific fields. Among these is the field of machine learning whose applicability heavily relies on solvers which are capable of efficiently solving challenging large-scale optimization problems. Notwithstanding, we still lack an adequate complexity theory which satisfactorily quantifies the computational resources required for solving optimization problems of this nature. Motivated by the limitations of current...

Read More