Publications related to Complete (complexity)

Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Tensor-Based Numerical Method For Stochastic Homogenization

This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity ...

SIAM PUBLICATIONS2022

cRacklet: a spectral boundary integral method library for interfacial rupture simulation

Jean-François Molinari, Thibault Didier Roch, Fabian Barras

The study of dynamically propagating rupture along interfaces is of prime importance in various fields and system sizes, including tribology (nm to m), engineering (mm to m) and geophysics (m to km) (Armstrong-Hélouvry et al., 1994; Ben-Zion, 2008; Vanossi ...

2022

Adversarial training with informed data selection

Pascal Frossard, Javier Alejandro Maroto Morales, Marcele Oliveira Kuhfuss de Mendonça

With the increasing amount of available data and advances in computing capabilities, deep neural networks (DNNs) have been successfully employed to solve challenging tasks in various areas, including healthcare, climate, and finance. Nevertheless, state-of ...

IEEE2022

A method for faster application of process integration techniques in retrofit situations

Tuong-Van Nguyen

Numerous process integration techniques were proved to be highly effective for identifying and estimating potential energy savings in the industry. However, they require high time and effort to collect and analyse process data. As a result, they do not con ...

ELSEVIER SCI LTD2021

Minimum-Error Classes for Matching Parts

Thomas Alois Weber

This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...

2021

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Fast Block Sequential Decoding of Polar Codes

Kirill Ivanov

A reduced complexity sequential decoding algorithm for polar (sub) codes is described. The proposed approach relies on a decomposition of the polar (sub) code being decoded into a number of outer codes, and on-demand construction of codewords of these code ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Tropical Ehrhart Theory and Tropical Volume

Matthias Schymura, Georg Peter Loho

We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposit ...

2019

Improved decoding of second-order Reed-Muller codes

Rüdiger Urbanke, Kirill Ivanov

In this paper, we consider low-complexity decoding of second-order Reed-Muller codes. A class of polynomial-time algorithms, based on the projections onto first-order codes, is studied. An old representative of this class, originally developed for binary s ...

IEEE2019

Level crossings induced by a longitudinal coupling in the transverse field Ising chain

Frédéric Mila, Grégoire Vionnet

We study the effect of antiferromagnetic longitudinal coupling on the one-dimensional transverse field Ising model with nearest-neighbor couplings. In the topological phase where, in the thermodynamic limit, the ground state is twofold degenerate, we show ...

2017

The isostatic 3-body problem: a complete solution

Simon Nessim Henein, Florent Cosandier, Ilan Vardi, François Barrot, Johannes Richard Cornelis Geerit Kruis

Kinematic couplings are used when two rigid bodies need to be repeatedly and accurately positioned with respect to each other. They allow for sub-micron positioning repeatability by suppressing play and reducing strains in the bodies. Typical applications ...

2017

LPN in Cryptography : an Algorithmic Study

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

Electronic solutions for power system emulation

Guillaume Olivier Lanz

Nowadays electric power systems are subject to continuous changes and the needs in the power generation and delivery service are constantly increasing, with a higher complexity of a progressively more distributed network. Because the impact of a failure ca ...

EPFL2017

Progressive Geometric Algorithms

Timur Bagautdinov

Progressive algorithms are algorithms that, on the way to computing a complete solution to the problem at hand, output intermediate solutions that approximate the complete solution increasingly well. We present a framework for analyzing such algorithms, an ...

Carleton Univ, Dept Mathematics & Statistics2015

An optimization framework for the development of efficient one-way car-sharing systems

Nikolaos Geroliminis, Burak Boyaci, Konstantinos Zografos

Electric vehicle-sharing systems have been introduced to a number of cities as a means of increasing mobility, reducing congestion, and pollution. Electric vehicle-sharing systems can offer one or two-way services. One-way systems provide more flexibility ...

Elsevier2015

Learning decision rules for energy efficient building control

Colin Neil Jones

While rule based control (RBC) is current practice in most building automation systems that issue discrete control signals, recent simulation studies suggest that advanced, optimization based control methods such as hybrid model predictive control (HMPC) c ...

Elsevier2014

Learning Discriminative Features and Structured Models for Segmentation in Microscopy and Natural Images

Aurélien Lucchi

Segmenting images is a significant challenge that has drawn a lot of attention from different fields of artificial intelligence and has many practical applications. One such challenge addressed in this thesis is the segmentation of electron microscope (EM) ...

EPFL2013

Metropolis-Hastings sampling of paths

Michel Bierlaire, Gunnar Flötteröd

We consider the previously unsolved problem of sampling paths according to a given distribution from a general network. The problem is difficult because of the combinatorial number of alternatives, which prohibits a complete enumeration of all paths and he ...

2013

A reduced basis hybrid method for the coupling of parametrized domains represented by fluidic networks

Alfio Quarteroni, Gianluigi Rozza, Laura Iapichino

In this paper we propose a reduced basis hybrid method (RBHM) for the approximation of partial differential equations in domains represented by complex networks where topological features are recurrent. The RBHM is applied to Stokes equations in domains wh ...

Elsevier2012