Publication
When Stuck, Flip a Coin
Related publications (332)
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 Ltd2024COMMUNICATION LOWER BOUNDS AND OPTIMAL ALGORITHMS FOR MULTIPLE TENSOR-TIMES-MATRIX COMPUTATION
Multiple tensor-times-matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine ...
Philadelphia2024Results on Sparse Integer Programming and Geometric Independent Sets
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 p ...
EPFL2023Fast 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 ...
arXiv2023Fast 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 ...
New York2023Automated planning for the construction of laterally resistant masonry walls using irregular stones
Katrin Beyer, Bryan German Pantoja Rosero, Qianqing Wang, Ketson Roberto Maximiano Dos Santos
The construction industry's carbon footprint may be reduced by switching to the usage of natural stones as building materials. Construction of dry-joint stone masonry structures is difficult because of the irregular shapes and the nonuniform sizes of the s ...
2023Learning Sparse Graphons And The Generalized Kesten-Stigum Threshold
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-IMS2023How to Find Molecules with Long-lasting Charge Migration?
Jiri Vanicek, Alan Scheidegger, Nikolay Golubev
Under certain conditions, the ionization of a molecule may create a superposition of electronic states, leading to ultrafast electron dynamics. If controlled, this motion could be used in attochemistry applications, but it has been shown that the decoheren ...
SWISS CHEMICAL SOC2023Unambiguous DNFs and Alon-Saks-Seymour
Mika Tapani Göös, Siddhartha Jain
We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...
IEEE COMPUTER SOC2022Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Adam Teodor Polak, Alexandra Anna Lassota
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...
Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022