Publications related to Iterated local search

A note on the integrality gap of the configuration LP for restricted Santa Claus

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...

ELSEVIER2020

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Ali Boujemaoui

Decreasing defects, waste time, meeting customer demand and being adaptable are the goals of a Zero Defect Manufacturing (ZDM) strategy. Scheduling is an important tool to perform that. It should take in account buffer size allocation. In this study, a met ...

SPRINGER INTERNATIONAL PUBLISHING AG2020

Combinatorial optimization of Dedicated Bus Lane layout in urban networks with dynamic congestion

Nikolaos Geroliminis, Dimitrios Tsitsokas, Anastasios Kouvelas

Transit priority based in exclusive right-of-way is a low-cost way of improving transit service by minimizing delays caused by interaction with other vehicles. This effect can increase the share of public transit against private cars in the mode preference ...

2020

A new wake model and comparison of eight algorithms for layout optimization of wind farms in complex terrain

Fernando Porté Agel, Roberto Brogna

Layout optimization of wind farms constitutes an important and challenging task in complex terrain. This is especially due to the complex interactions of the boundary layer flows in complex terrain and wind turbine wakes, which renders wake modelling in co ...

ELSEVIER SCI LTD2020

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Volkan Cevher, Ali Kavis, Shaul Nadav Hallak

This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm’s convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with prob ...

2020

Square Attack: a query-efficient black-box adversarial attack via random search

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko, Francesco Croce

We propose the Square Attack, a new score-based black-box

l_2

and

l_\infty

adversarial attack that does not rely on local gradient information and thus is not affected by gradient masking. The Square Attack is based on a randomized search scheme where ...

2020

An Improved Analysis of Local Search for Max-Sum Diversification

Friedrich Eisenbrand, Rico Zenklusen, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

Trajectory and Foothold Optimization using Low-Dimensional Models for Rough Terrain Locomotion

Sylvain Calinon, Jonas Buchli

We present a trajectory optimization framework for legged locomotion on rough terrain. We jointly optimize the center of mass motion and the foothold locations, while considering terrain conditions. We use a terrain costmap to quantify the desirability of ...

IEEE2017

LP-Based Algorithms For Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic me ...

Society for Industrial and Applied Mathematics2017

A Bi-Criteria Approximation Algorithm for k-Means

Justin Dean Ward

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set ...

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2016

Iterated local search

Graph Chatbot

Chat with Graph Search

A note on the integrality gap of the configuration LP for restricted Santa Claus

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Combinatorial optimization of Dedicated Bus Lane layout in urban networks with dynamic congestion

A new wake model and comparison of eight algorithms for layout optimization of wind farms in complex terrain

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Square Attack: a query-efficient black-box adversarial attack via random search

An Improved Analysis of Local Search for Max-Sum Diversification

Trajectory and Foothold Optimization using Low-Dimensional Models for Rough Terrain Locomotion

LP-Based Algorithms For Capacitated Facility Location

A Bi-Criteria Approximation Algorithm for k-Means

An Improved Analysis of Local Search for Max-Sum Diversification

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Square Attack: a query-efficient black-box adversarial attack via random search

A note on the integrality gap of the configuration LP for restricted Santa Claus

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Combinatorial optimization of Dedicated Bus Lane layout in urban networks with dynamic congestion

A new wake model and comparison of eight algorithms for layout optimization of wind farms in complex terrain

Trajectory and Foothold Optimization using Low-Dimensional Models for Rough Terrain Locomotion

A Bi-Criteria Approximation Algorithm for k-Means

LP-Based Algorithms For Capacitated Facility Location