61 citations · 242 across the 48 of their papers we have counts for
6 papers · 1 filter
Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics
Jialiang Li, Aneta Neumann, Frank Neumann +2
Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algor…
Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint
Anh Viet Do, Mingyu Guo, Aneta Neumann +1
Finding diverse solutions to optimization problems has been of practical interest for several decades, and recently enjoyed increasing attention in research. While submodular optim…
Limited Query Graph Connectivity Test
Mingyu Guo, Jialiang Li, Aneta Neumann +2
We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are…
Exact Counting and Sampling of Optima for the Knapsack Problem
Jakob Bossek, Aneta Neumann, Frank Neumann
Computing sets of high quality solutions has gained increasing interest in recent years. In this paper, we investigate how to obtain sets of optimal solutions for the classical kna…
Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights
Yue Xie, Aneta Neumann, Frank Neumann +1
Addressing a complex real-world optimization problem is a challenging task. The chance-constrained knapsack problem with correlated uniform weights plays an important role in the c…
Pareto Optimization for Subset Selection with Dynamic Cost Constraints
Vahid Roostapour, Aneta Neumann, Frank Neumann +1
We consider the subset selection problem for function with constraint bound that changes over time. Within the area of submodular optimization, various greedy approaches ar…