A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

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.

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Chat with Graph Search

Band Gap Renormalization at Different Symmetry Points in Perovskites

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

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

Learning to Remove Cuts in Integer Linear Programming

Approximation Algorithms for Allocation and Network Design

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

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

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

Results on Sparse Integer Programming and Geometric Independent Sets

Streaming and Matching Problems with Submodular Functions

Quasi-symmetry-protected topology in a semi-metal

Mismatched Decoding Reliability Function at Zero Rate

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Modified snaking in plane Couette flow with wall-normal suction

Efficient implementation of atom-density representations

One-dimensional composite host-guest structure in BaVS3

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

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

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

Local invertibility and sensitivity of atomic structure-feature mappings