Publications associées à On some coloring problems in grids

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Tony Alan Wood

We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Inhalation of Microplastics—A Toxicological Complexity

Florian Frédéric Vincent Breider, Myriam Borgatta

Humans are chronically exposed to airborne microplastics (MPs) by inhalation. Various types of polymer particles have been detected in lung samples, which could pose a threat to human health. Inhalation toxicological studies are crucial for assessing the e ...

2024

Graph generative deep learning models with an application to circuit topologies

Igor Krawczuk

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

EPFL2024

Differentially private multi-agent constraint optimization

Boi Faltings, Aleksei Triastcyn, Sujit Prakash Gujar, Sankarshan Damle

Distributed constraint optimization (DCOP) is a framework in which multiple agents with private constraints (or preferences) cooperate to achieve a common goal optimally. DCOPs are applicable in several multi-agent coordination/allocation problems, such as ...

Springer2024

A Comparative Analysis of Tools & Task Types for Measuring Computational Problem-Solving

Engin Walter Bumbacher, Jérôme Guillaume Brender, Richard Lee Davis

How to measure students' Computational Problem-Solving (CPS) competencies is an ongoing research topic. Prevalent approaches vary by measurement tools (e.g., interactive programming, multiple-choice tests, or programming-independent tests) and task types ( ...

Association for Computing Machinery2024

On-Chip Fully Reconfigurable Artificial Neural Network in 16 nm FinFET for Positron Emission Tomography

Claudio Bruschini, Edoardo Charbon, Andrada Alexandra Muntean, Emanuele Ripiccini

Smarty is a fully-reconfigurable on-chip feed-forward artificial neural network (ANN) with ten integrated time-to-digital converters (TDCs) designed in a 16 nm FinFET CMOS technology node. The integration of TDCs together with an ANN aims to reduce system ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Hybrid ground-state quantum algorithms based on neural Schrödinger forging

Giuseppe Carleo, Sofia Vallecorsa

Entanglement forging based variational algorithms leverage the bipartition of quantum systems for addressing ground-state problems. The primary limitation of these approaches lies in the exponential summation required over the numerous potential basis stat ...

Amer Physical Soc2024

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Rom Pinchasi

Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...

Electronic Journal Of Combinatorics2024

Identification of typical district configurations: A two-step global sensitivity analysis framework

François Maréchal, Jonas Schnidrig, Cédric Terrier

The recent geopolitical conflicts in Europe have underscored the vulnerability of the current energy system to the volatility of energy carrier prices. In the prospect of defining robust energy systems ensuring sustainable energy supply in the future, the ...

Pergamon-Elsevier Science Ltd2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

Efficient Continual Finite-Sum Minimization

Volkan Cevher, Leello Tadesse Dadi, Efstratios Panteleimon Skoulakis

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

2024

Reactive collision-free motion generation in joint space via dynamical systems and sampling-based MPC

Aude Billard, Nadia Barbara Figueroa Fernandez, Mikhail Koptev

Dynamical system (DS) based motion planning offers collision-free motion, with closed-loop reactivity thanks to their analytical expression. It ensures that obstacles are not penetrated by reshaping a nominal DS through matrix modulation, which is construc ...

Sage Publications Ltd2024

Functional-Basis Analysis of Non-Stationary Signals in Modern Power Grids: Theory and Implementation in Embedded Systems

Alexandra Cameron Karpilow

Situational awareness strategies are essential for the reliable and secure operation of the electric power grid which represents critical infrastructure in modern society. With the rise of converter-interfaced renewable generation and the consequent shift ...

EPFL2024

Energy Management of Price-Maker Community Energy Storage by Stochastic Dynamic Programming

Xue Zhang, Tianshu Yang

In this paper, we propose an analytical stochastic dynamic programming (SDP) algorithm to address the optimal management problem of price-maker community energy storage. As a price-maker, energy storage smooths price differences, thus decreasing energy arb ...

China Electric Power Research Inst2024

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Why computational complexity may set impenetrable barriers for epistemic reductionism

Michael Herzog, Adrien Christophe Doerig, Christian Sachse

According to physicalism, everything is physical or metaphysically connected to the physical. If physicalism were true, it seems that we should - in principle - be able to reduce the descriptions and explanations of special sciences to physical ones, for e ...

Springer2023

Smart acoustic lining for UHBR technologies engine: from the design of an electroacoustic metasurface to experimental characterization under flow

Hervé Lissek, Maxime Volery

The SALUTE project aims at evaluating performance of electroacoustic metasurface, employing a surface array of controlled electroacoustic actuators, for smart acoustic lining under grazing turbulent flow to be used in UHBR Technologies Engines. Theoretical ...

Society of Photo-Optical Instrumentation Engineers (SPIE)2023

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Thanh Trung Huynh

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

ELSEVIER SCIENCE INC2023