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

Related publications (28)

About
Privacy
Disclaimer

Graph Chatbot

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

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

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

Page 1 of 3