Publications related to An Efficient Streaming Algorithm for the Submodular Cover Problem

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

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

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

EPFL2023

Tight 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

Approximate 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 SCIENCE2022

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

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 Informatik2021

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

2021

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

2021

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

2020

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

An Efficient Streaming Algorithm for the Submodular Cover Problem

Graph Chatbot

Chat with Graph Search

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

Approximation Algorithms for Allocation and Network Design

Results on Sparse Integer Programming and Geometric Independent Sets

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

Approximate CVPp in time 2(0.802n)

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms

New Results in Integer and Lattice Programming

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

Approximation Algorithms for Allocation and Network Design

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Results on Sparse Integer Programming and Geometric Independent Sets

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

New Results in Integer and Lattice Programming

Approximate CVPp in time 2(0.802n)

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

Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid