5 papers
Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases
Chandra Chekuri, Lars Rohwedder, Neta Singer +2
Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function over m…
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
Lars Rohwedder, Rico Zenklusen
Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an ac…
A -approximation algorithm for the general scheduling problem in quasipolynomial time
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
We study the general scheduling problem (GSP) which generalizes and unifies several well-studied preemptive single-machine scheduling problems, such as weighted flow time, weighted…
Non-Adaptive Evaluation of -of- Functions: Tight Gap and a Unit-Cost PTAS
Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior
We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of -of- functions: There are independent Boolean random variables $x_1,\dots,x_…
Multiplicative assignment with upgrades
Alexander Armbruster, Lars Rohwedder, Stefan Weltge +2
We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractio…