Publications associées à A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Publications associées (30)

Band Gap Renormalization at Different Symmetry Points in Perovskites

Using ultrafast broad-band transient absorption (TA) spectroscopy of photoexcited MAPbBr3 thin films with probe continua in the visible and the mid- to deep-ultraviolet (UV) ranges, we capture the ultrafast renormalization at the fundamental gap at the R s ...

Amer Chemical Soc2024

'Fraternal-twin' ferroelectricity: competing polar states in hydrogen-doped samarium nickelate from first principles

Michele Kotiuga

In ferroelectric switching, an applied electric field switches the system between two polar symmetry-equivalent states. In this work, we use first-principles calculations to explore the polar states of hydrogen-doped samarium nickelate (SNO) at a concentra ...

Iop Publishing Ltd2024

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

Learning to Remove Cuts in Integer Linear Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

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

Critical line of the triangular Ising antiferromagnet in a field from a C3-symmetric corner transfer matrix algorithm

Afonso Dos Santos Rufino, Frédéric Mila, Jeanne Colbois, Samuel Louis Nyckees

The corner transfer matrix renormalization group (CTMRG) algorithm has been extensively used to investigate both classical and quantum two-dimensional (2D) lattice models. The convergence of the algorithm can strongly vary from model to model depending on ...

Amer Physical Soc2023

Exact quantum conformal symmetry, its spontaneous breakdown, and gravitational Weyl anomaly

Mikhail Chapochnikov, Anna Tokareva

The classical Lagrangian of the Standard Model enjoys the symmetry of the full conformal group if the mass of the Higgs boson is put to zero. This is a hint that conformal symmetry may play a fundamental role in the ultimate theory describing nature. The o ...

American Physical Society2023

Dynamic nuclear polarisation of 1H in Gd-doped In(OH)3

David Lyndon Emsley, Michael Allan Hope, Amrit Venkatesh, Yuxuan Zhang

Dynamic nuclear polarisation (DNP) of solids doped with high-spin metal ions, such as Gd3+, is a useful strategy to enhance the nuclear magnetic resonance (NMR) sensitivity for these samples. Spin diffusion can relay polarisation throughout a sample, which ...

Academic Press Inc - Elsevier Science2023

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

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Quasi-symmetry-protected topology in a semi-metal

Philip Johannes Walter Moll, Matthias Carsten Putzke, Yi-Chiang Sun, Chunyu Guo, Xiangwei Huang, Jonas De Jesus Diaz Gomez

The concept of quasi-symmetry-a perturbatively small deviation from exact symmetry-is introduced and leads to topological materials with strong resilience to perturbations. ...

NATURE PORTFOLIO2022

Mismatched Decoding Reliability Function at Zero Rate

Marco Bondaschi

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlos that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurg ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

Modified snaking in plane Couette flow with wall-normal suction

Tobias Schneider, Sajjad Azimi

A specific family of spanwise-localised invariant solutions of plane Couette flow exhibits homoclinic snaking, a process by which spatially localised invariant solutions of a nonlinear partial differential equation smoothly grow additional structure at the ...

Cambridge University Press2021

Efficient implementation of atom-density representations

Michele Ceriotti, Till Junge, Félix Benedito Clément Musil, Michael John Willatt, Guillaume André Jean Fraux, Max David Veit, Alexander Jan Goscinski

Physically motivated and mathematically robust atom-centered representations of molecular structures are key to the success of modern atomistic machine learning. They lie at the foundation of a wide range of methods to predict the properties of both materi ...

2021

One-dimensional composite host-guest structure in BaVS3

László Forró, Helmuth Berger, Gervais Chapuis, Philip Pattison, Alla Arakcheeva, Neven Barisic

A detailed synchrotron X-ray diffraction (XRD) study performed with a single crystal of BaVS3 (barium vanadium trisulfide) in the temperature range between 10 and 295 K is reported. Aside from the known tetragonal–orthorhombic (240 K) and orthorhombic–mono ...

2021

On the non-existence of stepped-pressure equilibria far from symmetry

Joaquim Loizu Cisquella

The Stepped Pressure Equilibrium Code (SPEC) (Hudson et al 2012 Phys. Plasmas 19 112502) has been successful in the construction of equilibria in 3D configurations that contain a mixture of flux surfaces, islands and chaotic magnetic field lines. In this m ...

2021

Gapped Goldstones at the cut-off scale: a non-relativistic EFT

Riccardo Rattazzi, Alexander Monin, Angelo Esposito, Gabriel Francisco Cuomo

At finite density, the spontaneous breakdown of an internal non-Abelian symmetry dictates, along with gapless modes, modes whose gap is fixed by the algebra and proportional to the chemical potential: the gapped Goldstones. Generically the gap of these sta ...

Springer Nature2021

Broken-Symmetry Ground States of the Heisenberg Model on the Pyrochlore Lattice

Giuseppe Carleo

The spin-1/2 Heisenberg model on the pyrochlore lattice is an iconic frustrated three-dimensional spin system with a rich phase diagram. Besides hosting several ordered phases, the model is debated to possess a spin-liquid ground state when only nearest-ne ...

American Physical Society2021

Local invertibility and sensitivity of atomic structure-feature mappings

Michele Ceriotti, Sergey Pozdnyakov

Background: The increasingly common applications of machine-learning schemes to atomic-scale simulations have triggered efforts to better understand the mathematical properties of the mapping between the Cartesian coordinates of the atoms and the variety o ...

2021