Publication
An Efficient Streaming Algorithm for the Submodular Cover Problem
Related publications (53)
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 Ltd2024Approximation Algorithms for Allocation and Network Design
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 ...
EPFL2023Results 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 ...
EPFL2023Tight 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 Informatik2022Approximate CVPp in time 2(0.802n)
Friedrich Eisenbrand, Moritz Andreas Venzin
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2022Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021Online Contention Resolution Schemes With Applications To Bayesian Selection Problems
Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen
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 ...
2021Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
Maryam Kamgarpour, Orcun Karaca
This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and ...
2021Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms
Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca
Actuator placement is an active field of research which has received significant attention for its applications in complex dynamical networks. In this paper, we study the problem of finding a set of actuator placements minimizing the metric that measures t ...
2020New Results in Integer and Lattice Programming
An integer program (IP) is a problem of the form , where , , , and is a separable convex objective function.
The problem o ...
EPFL2020