Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (32)

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Assoc Computing Machinery2023

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Orcun Karaca, Maryam Kamgarpour

We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...

IEEE2023

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

arXiv2023

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Maryam Kamgarpour, Tony Alan Wood

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

2023

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-constrained Cycles

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Cycles are one of the fundamental subgraph patterns and being able to enumerate them in graphs enables important applications in a wide variety of fields, including finance, biology, chemistry, and network science. However, to enable cycle enumeration in r ...

Assoc Computing Machinery2023

Time vs. Truth: Age-Distortion Tradeoffs and Strategies for Distributed Inference

Yunus Inan

In 1948, Claude Shannon laid the foundations of information theory, which grew out of a study to find the ultimate limits of source compression, and of reliable communication. Since then, information theory has proved itself not only as a quest to find the ...

EPFL2023

Robust Collaborative Learning with Linear Gradient Overhead

Rachid Guerraoui, Le Nguyen Hoang, John Stephan, Sadegh Farhadkhani, Nirupam Gupta, Rafaël Benjamin Pinot

Collaborative learning algorithms, such as distributed SGD (or D-SGD), are prone to faulty machines that may deviate from their prescribed algorithm because of software or hardware bugs, poisoned data or malicious behaviors. While many solutions have been ...

PLMR2023

Adaptive isogeometric methods with C-1 (truncated) hierarchical splines on planar multi-patch domains

Rafael Vazquez Hernandez

Isogeometric analysis is a powerful paradigm which exploits the high smoothness of splines for the numerical solution of high order partial differential equations. However, the tensor-product structure of standard multivariate B-spline models is not well s ...

WORLD SCIENTIFIC PUBL CO PTE LTD2023

Dynamical Low-Rank Approximation for Stochastic Differential Equations

Fabio Nobile, Yoshihito Kazashi, Fabio Zoccolan

In this paper, we set the mathematical foundations of the Dynamical Low-Rank Approximation (DLRA) method for stochastic differential equations (SDEs). DLRA aims at approximating the solution as a linear combination of a small number of basis vectors with r ...

American Mathematical Society (AMS)2024

Phenomenological theory of variational quantum ground-state preparation

Ivano Tavernelli, Giuseppe Carleo

The variational approach is a cornerstone of computational physics, considering both conventional and quantum computing computational platforms. The variational quantum eigensolver algorithm aims to prepare the ground state of a Hamiltonian exploiting para ...

Amer Physical Soc2023

On the fast assemblage of finite element matrices with application to nonlinear heat transfer problems

Yannis Dirk Voet

The finite element method is a well-established method for the numerical solution of partial differential equations (PDEs), both linear and nonlinear. However, the repeated re -assemblage of finite element matrices for nonlinear PDEs is frequently pointed ...

ELSEVIER SCIENCE INC2023

Learning Sparse Graphons And The Generalized Kesten-Stigum Threshold

Emmanuel Abbé

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succe ...

INST MATHEMATICAL STATISTICS-IMS2023

Page 2 sur 2