Publication

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Related publications (67)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic

In this paper, we consider the problem of sequentially optimizing a black-box function

f

based on noisy samples and bandit feedback. We assume that

f

is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yield ...

2017

Network Flow Integer Programming to Track Elliptical Cells in Time-Lapse Sequences

Pascal Fua, Engin Türetken, Xinchao Wang, Carlos Joaquin Becker

We propose a novel approach to automatically tracking elliptical cell populations in time-lapse image sequences. Given an initial segmentation, we account for partial occlusions and overlaps by generating an over-complete set of competing detection hypothe ...

2017

Small subset sums

Gergely Ambrus

Let parallel to.parallel to be a norm in R-d whose unit ball is B. Assume that V subset of B is a finite set of cardinality n, with Sigma(v is an element of V) v = 0. We show that for every integer k with 0

Elsevier Science Inc2016

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings

Andrew Joseph Reynolds

We prove that the quantifier-free fragment of the theory of character strings with regular language membership constraints and linear integer constraints over string lengths is decidable. We do that by describing a sound, complete and terminating tableaux ...

Springer-Verlag Berlin2015

Renormalized solutions to the continuity equation with an integrable damping term

Maria Colombo

We consider the continuity equation with a nonsmooth vector field and a damping term. In their fundamental paper, DiPerna and Lions (Invent Math 98:511-547, 1989) proved that, when the damping term is bounded in space and time, the equation is well posed i ...

2015

Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex

Jan Kyncl

We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant such that whenever are n-element subsets of , we can find a point and subsets for every , each of size at least , suc ...

Springer2015

, , ,

We propose a novel approach to automatically detecting and tracking cell populations in time-lapse images. Unlike earlier ones that rely on linking a predetermined and potentially under-complete set of detections, we generate an overcomplete set of competi ...

2015

Upper bounds for Euclidean minima of abelian number fields

Eva Bayer Fluckiger, Piotr Aleksander Maciak

Le but de cet article est de donner des bornes supérieures pour les minima euclidiens de corps abéliens, en particulier dans le cas des corps abéliens de conducteurs des puissances de nombres premiers. ...

2015

A sieve algorithm based on overlattices

Anja Annemone Becker

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...

Cambridge Univ Press2014

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic

In this paper, we consider the problem of sequentially optimizing a black-box function

f

based on noisy samples and bandit feedback. We assume that

f

is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yield ...

2017