We introduce the Itinerant List-Update Problem (ILU), which is a relaxation of the classic List-Update Problem (LU) in which the pointer no longer has to return to a home location after each request. The motivation to introduce ILU arises from the application of track management in Domain Wall Memory. We first show an Omega(log n) lower bound on the competitive ratio for any randomized online algorithm for ILU. This shows that online ILU is harder than online LU, for which O(1)-competitive algorithms, like Move-To-Front, are known. We then show that ILU is essentially equivalent to a variation of the Minimum Linear Arrangement Problem (MLA), which we call the Dynamic Minimum Linear Arrangement (DMLA) problem. We then give an offline polynomial-time algorithm for DMLA and show that it has an polylogarithmic approximation guarantee.
This is joint work with Neil Olver, Kirk Pruhs, René Sitters, and Leen Stougie.
Differential Evolution (DE) emerged as a simple yet very competitive evolutionary algorithm for optimization over continuous parameter spaces. For more than two decades, DE and its variants (the "DE family" to be precise) have been exhibiting brilliant performance over numerical benchmarks as well as several real world optimization problems. Unlike the traditional evolution strategies or real-coded genetic algorithms, DE does not sample the perturbation step-size for its population members from a parameterized probability distribution. Instead, it uses a kind of self-referential mutation where the scaled vector difference(s) of the current population members are used to perturb others. This talk will discuss the basic working principle of DE and will highlight some of the recent DE variants that are extensively in use for single-objective, multi-modal and non-convex optimization problems. It will also highlight some future research issues including the theoretical studies that need to be undertaken to fully understand DE.
Multi-component problems play a crucial role in real-world applications, especially in the area of supply chain management. Recently, the traveling thief problem (TTP) has been introduced to study multi-component problems in a systematic way and many heuristic search algorithms have been proposed for the TTP. Although a lot of algorithmic advances have been made on this problem, determining an optimal solution, even for small instances, is very challenging. In this talk, we will present exact and hybrid approaches for this problem. We start by investigating the already NP-hard Packing While Traveling (PWT) problem which results from TTP when the TSP tour is fixed. We present an exact dynamic programming approach for PWT and give a fully polynomial time approximation scheme (FPTAS) for PWT over its baseline travel cost. Afterwards, we extend the approach to give a dynamic programming (DP) approach for TTP and report on some experimental results. Furthermore, we will show how the DP for PWT can be incorporated into an evolutionary multi-objective algorithm to tackle a multi-objective formulation of TTP. Joint work with Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu, Markus Wagner
Evolutionary algorithms have recently been used to create a wide range of artistic work. In this paper, we propose a new approach for the composition of new images from existing ones, that retain some salient features of the original images. We introduce evolutionary algorithms that create new images based on a fitness function that incorporates feature covariance matrices associated with different parts of the images. This approach is very flexible in that it can work with a wide range of features and enables targeting specific regions in the images. For the creation of the new images, we propose a population-based evolutionary algorithm with mutation and crossover operators based on random walks. Our experimental results reveal a spectrum of aesthetically pleasing images that can be obtained with the aid of our evolutionary process.
We give a summary of the iterative method from the book "Iterative methods in combinatorial optimization" by Lap Chi Lau, R.Ravi and Mohit Singh.
We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type Bd. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Paris Sud), Syed Meesum (IMSc Chennai), and Shmuel Onn (Technion).
Hash functions have become ubiquitous tools in modern data analysis, e.g., the construction of small randomized sketches of large data streams. We like to think of abstract hash functions, assigning independent uniformly random hash values to keys, but in practice, we have to choose a hash function that only has an element of randomness, e.g., 2-independence. While this works for sufficiently random input, the real world has structured data where such simple hash functions fail, calling for the need of more powerful hash functions. In this talk, we focus hashing for set similarity, which is an integral component in the analysis of Big Data. The basic idea is to use the same hash function to do coordinated sampling from different sets. Depending on the context, we want subsets sampled without replacement, or fixed-length vectors of samples that may be with replacement. The latter is used as input to support vector machines (SVMs) and locality sensitive hashing (LSH). The most efficient constructions require very powerful hash functions that are also needed for efficient size estimation. We discuss the interplay between the hash functions and the algorithms using them. Finally, we present experiments on both real and synthetic data where standard 2-independent hashing yield systematically poor similarity estimates, while the right theoretical choice is sharply concentrated, and faster than standard cryptographic hash functions with no proven guarantees.
We will present algorithms for the evacuation problem by a pair of distinct-speed robots on an infinite line. In this problem, two mobile robots with different maximal speeds are initially placed at the same point on an infinite line. The robots need to find a stationary target (i.e., the exit), which is placed at an unknown location on the line. The search is completed when both robots arrive at the exit and the goal is to conclude evacuation in as little time as possible. The robot that discovers the exit first may communicate it to the other robot. We consider two models of communication between the robots, namely wireless communication and face-to-face communication. We present an optimal algorithm for any combination of robot speeds in the case of face-to-face communication. In the case of wireless communication, our algorithm is optimal if the slow robot is at most 6 times slower than the fast robot.
I will present different projects I am currently working on and questions I am interested in. I have presented simple stochastic games at seminar S a few month ago, therefore I will focus on periodic scheduling and enumeration algorithms.
In a so-called mixed-shop scheduling problem, the operations of some jobs
have to be processed in a fixed order (as in the job-shop problem); the
other ones can be processed in an arbitrary order (as in the open-shop
problem). In this paper we present a new exact polynomial-time algorithm
for the mixed-shop problems with preemptions and at most two unit
operations per job.
Joint work with Aldar Dugarzhapov.
We consider a novel single-machine scheduling problem where the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job $j$ takes one unit of time and may reduce its processing time from the given upper limit $\bar{p}_j$ (which is the time taken to execute the job if it is not tested) to any value between $0$ and $\bar{p}_j$. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.
Joint work with Thomas Erlebach, Nicole Megow, and Julie Meißner.
An algorithm is a set of instructions to process the input for a given problem. In the classical setting, algorithms have access to the entire input and the algorithm is a function applied to this input. The result of the function being the output. In contrast, in the online setting, the input is revealed sequentially, piece by piece; these pieces are called requests. Moreover, after receiving each request, the algorithm must take an action before the next request is revealed. That is, the algorithm must make irrevocable decisions based on the input revealed so far without any knowledge of the future input. Since the future is unknown, these decisions could prove very costly. Online problems have many real-world applications such as paging, routing and scheduling. In this talk, I'll review the topic of online computation, some classic online problems, and some techniques used to analyze online algorithms that have been developed over the last 30 years. Then, I'll show how our new techniques (the bijective ratio and approximate stochastic dominance) fit into this rich domain and apply them to classic problems with a particular focus on the greedy algorithm for the k-server problem, an algorithm that performs well in practice (on certain metric spaces) when the classic analysis tools claim it should not.
We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) k-median and k-means in edge-weighted planar graphs; (3) k-means in Euclidean space of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the p-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding $1/\epsilon^{O(1)}$ centers.
Joint work with Philip N. Klein, and Claire Mathieu.
Dantzig–Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method was not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. We demonstrate that for generic MIPs strong dual bounds can be obtained from the automatically reformulated model using column generation. In the second part of the talk we apply a recursive Automatic Dantzig–Wolfe reformulation to the Temporal Knapsack Problem (TKP) which is a generalization of the standard Knapsack Problem where a time horizon is considered, and each item consumes the knapsack capacity during a limited time interval only. We then show that this new method allows us to solve TKP instances to proven optimality through computation of extremely strong dual bounds.
In this talk we are going to talk about the dynamic control of resource-sharing systems that arise in various domains: e.g. inventory management, communication networks. We aim at efficiently allocating the available resources among competing projects according to a certain performance criteria. In particular, we will focus on Restless Bandit (RB) type of allocation problems. These type of problems have a stochastic nature and may be very complex to solve. We will go through different possible techniques to solve RB problems using scaling and relaxation techniques. The latter allow us to obtain simple and ready to implement suboptimal policies. We will discuss on the asymptotic optimality of these policies in interesting regimes such as Heavy-traffic and Light-traffic regimes and also the Many-Users regime. We will provide several application examples for which near-optimal heuristics have been obtained.
The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the few problems in NP ∩ coNP which are not known to be in P. However, there are some cases where these games can be easily solved, as for instance when the underlying graph is acyclic. I will present three classes of games that can be thought as ”almost” acyclic, by restricting parameters such as the number of cycles or the size of the minimal feedback vertex set. For these classes, we provide several polynomial algorithms or fixed-parameter algorithms.
We address the problem of coordinating the planning decisions for a single product in a supply chain composed of one supplier and one retailer. We assume that the retailer has private information about his cost structure and that he has the market power, he can impose his optimal replenishment plan. In the case where the actors of the supply chain act individually, the supplier's cost can be large since he has to satisfy the retailer's optimal replenishment plan. However, in order to decrease the supplier's cost, side payment can be allowed between the actors. We propose to design contracts between the actors under the asymmetric information assumption in order to decrease the supplier's cost.
We propose several special cases of the MUCP in order to discuss the complexity issues of the problem. We will present two open questions that still annoy us.
We will discuss the complexity of one of the most basic problems in pattern matching, that of approximating the Hamming distance. Given a pattern P of length n the task is to output an approximation of the Hamming distance (that is, the number of mismatches) between P and every n-length substring of a longer text. We provide the first efficient one-way randomised communication protocols as well as a new, fast and space efficient streaming algorithm for this problem.
In data centers, many tasks (services, virtual machines or computational jobs) share a single physical machine. Machines are used more efficiently, but tasks' performance deteriorates, as colocated tasks compete for shared resources. As tasks are heterogeneous (CPU-, memory-, network- or disk-intensive), the resulting performance dependencies are complex.
We explore a new resource management model for such colocation. Our model uses two parameters of a task - its size and its type - to characterize how a task influences the performance of the other tasks allocated on the same machine. The performance of a task is a function of the loads of all tasks assigned to the machine. The load of each type is counted separately.
We consider minimization of the total cost (utilitarian fairness). We show that for a linear cost function the problem is strongly NP-hard, but polynomially-solvable in some particular cases.
We propose an algorithm polynomial in the number of tasks (but exponential in the number of types and machines); and another algorithm polynomial in the number of tasks and machines (but exponential in the number of types and admissible sizes of tasks). We also propose a polynomial approximation algorithm, and, in a case of a single type, a polynomial exact algorithm.
For convex costs, we prove that, even for a single type, the problem becomes NP-hard; we propose an approximation algorithm.
Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online strategy based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and an absolute competitive ratio at most 22.641. We also show that no deterministic strategy can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is n-omega(1), where n is the number of vertices in the graph.