Publications related to Improving SAM Requires Rethinking its Optimization Formulation

Predicting in Uncertain Environments: Methods for Robust Machine Learning

One of the main goal of Artificial Intelligence is to develop models capable of providing valuable predictions in real-world environments. In particular, Machine Learning (ML) seeks to design such models by learning from examples coming from this same envi ...

EPFL2022

Optimization and equilibrium problems with discrete choice models

Stefano Bortolomiol

Many transportation markets are characterized by oligopolistic competition. In these markets customers, suppliers and regulators make decisions that are influenced by the preferences and the decisions of all other agents. In particular, capturing and under ...

EPFL2022

The completeness of the generalized eigenfunctions and an upper bound for the counting function of the transmission eigenvalue problem for Maxwell equations

Hoài-Minh Nguyên, Jean Louis-Alexandre Fornerod

Cakoni and Nguyen recently proposed very general conditions on the coefficients of Maxwell equations for which they established the discreten ess of the set of eigenvalues of the transmission problem and studied their locations. In this paper, we establish ...

2021

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

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

Remote Source Coding Under Gaussian Noise: Dueling Roles of Power and Entropy Power

Michael Christoph Gastpar

The distributed remote source coding (the so-called CEO) problem is studied in the case where the underlying source, not necessarily Gaussian, has finite differential entropy and the observation noise is Gaussian. The main result is a new lower bound for t ...

2019

Fundamental Limits for Implanted Antennas: Maximum Power Density Reaching Free Space

Anja Skrivervik, Zvonimir Sipus

Medical implants with communication capability are becoming increasingly popular with today’s trends to continuously monitor patient’s condition. This is a major challenge for antenna designers since the implants are inherently small and placed in a commun ...

2019

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2018

A feasible-side globally convergent modifier-adaptation scheme

Dominique Bonvin, Alejandro Gabriel Marchetti, Timm Faulwasser

In the context of static real-time optimization (RTO) of uncertain plants, the standard modifier-adaptation scheme consists in adding first-order correction terms to the cost and constraint functions of a model based optimization problem. If the algorithm ...

Elsevier Sci Ltd2017

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

Nonequilibrium localization and the interplay between disorder and interactions

Eduardo Carlo Mascarenhas Moraes

We study the nonequilibrium interplay between disorder and interactions in a closed quantum system. We base our analysis on the notion of dynamical state-space localization, calculated via the Loschmidt echo. Although real-space and state-space localizatio ...

Iop Publishing Ltd2016

Bisector Energy and Few Distinct Distances

Frank de Zeeuw

We define the bisector energy E(P) of a set P in R-2 to be the number of quadruples (a, b, c, d) is an element of P-4 such that a, b determine the same perpendicular bisector as c, d. Equivalently, E(P) is the number of isosceles trapezoids determined by P ...

Springer2016

Accelerated ADMM based on Accelerated Douglas-Rachford Splitting

Colin Neil Jones, Ivan Pejcic

Alternating direction method of multipliers (ADMM) is a form of augmented Lagrangian optimisation algorithm that found its place in many new applications in recent years. This paper explores a possibility for an upgrade of the ADMM by extrapolation-based a ...

Ieee2016

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

On the DCJ Median Problem

Bernard Moret, Mingfu Shao

As many whole genomes are sequenced, comparative genomics is moving from pairwise comparisons to multiway comparisons framed within a phylogenetic tree. A central problem in this process is the inference of data for internal nodes of the tree from data giv ...

Springer-Verlag Berlin2014

On Sub-determinants and the Diameter of Polyhedra

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Nicolas Bonifas, Marco Di Summa

We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show ...

Springer2014

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

Vectors in a box

Doemoetoer Palvoelgyi

For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a part ...

Springer2012

Expected loss bounds for authentication in constrained channels

Serge Vaudenay, Christos Dimitrakakis, Aikaterini Mitrokotsa

We derive bounds on the expected loss for authenti-cation protocols in channels which are constrained due to noisyconditions and communication costs. This is motivated by anumber of authentication protocols, where at least some partof the authentication is ...

Ieee2012

A heuristic for nonlinear global optimization

Nicolas Zufferey, Michel Bierlaire, Michaël Clément Louis Ghislain Thémans

We propose a new heuristic for nonlinear global optimization combining a variable neighborhood search framework with a modified trust-region algorithm as local search. The proposed method presents the capability to prematurely interrupt the local search if ...

2010

Approximating the Gaussian Multiple Description Rate Region Under Symmetric Distortion

Suhas Diggavi, Soheil Mohajerzefreh

We consider multiple description (MD) coding for the Gaussian source with K descriptions under the symmetric mean-squared error (MSE) distortion constraints, and provide an approximate characterization of the rate region. We show that the rate region can b ...

2009