Carsten Moldenhauer

SODA Conference 2015 Conference Paper

On largest volume simplices and sub-determinants

• Marco Di Summa
• Friedrich Eisenbrand
• Yuri Faenza
• Carsten Moldenhauer

We show that the problem of finding the simplex of largest volume in the convex hull of n points in ℚ d can be approximated with a factor of O (log d ) d /2 in polynomial time. This improves upon the previously best known approximation guarantee of d ( d –1)/2 by Khachiyan. On the other hand, we show that there exists a constant c > 1 such that this problem cannot be approximated with a factor of c d, unless P = NP. Our hardness result holds even if n = O ( d ), in which case there exists a d -approximation algorithm that relies on recent sampling techniques, where is again a constant. We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a d × n matrix.

I&C Journal 2013 Journal Article

Primal-dual approximation algorithms for Node-Weighted Steiner Forest on planar graphs

• Carsten Moldenhauer

Node-Weighted Steiner Forest is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider the restriction to planar graphs where the problem remains NP-complete. Demaine et al. showed that the generic primal-dual algorithm of Goemans and Williamson is a 6-approximation on planar graphs. We present (1) two different analyses to prove an approximation factor of 3, (2) show that our analysis is best possible for the chosen proof strategy, and (3) generalize this result to feedback problems on planar graphs. We give a simple proof for the first result using contraction techniques and following a standard proof strategy for the generic primal-dual algorithm. Given this proof strategy our analysis is best possible which implies that proving a better upper bound for this algorithm, if possible, would require different proof methods. Then, we give a reduction on planar graphs of Feedback Vertex Set to Node-Weighted Steiner Tree, and Subset Feedback Vertex Set to Node-Weighted Steiner Forest. This generalizes our result to the feedback problems studied by Goemans and Williamson. For the opposite direction, we show how our constructions can be combined with the proof idea for the feedback problems to yield an alternative proof of the same approximation guarantee for Node-Weighted Steiner Forest.

SoCS Conference 2010 Conference Paper

Single-Frontier Bidirectional Search

• Carsten Moldenhauer
• Ariel Felner
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001

We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. We provide theoretical analysis that explains when SFBDS will work validated by experimental results.

AAAI Conference 2010 Conference Paper

Single-Frontier Bidirectional Search

• Ariel Felner
• Carsten Moldenhauer
• Nathan Sturtevant
• Jonathan Schaeffer

On the surface, bidirectional search (BDS) is an attractive idea with the potential for significant asymptotic reductions in search effort. However, the results in practice often fall far short of expectations. We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SF- BDS). Unlike traditional BDS which keeps two frontiers, SF- BDS uses a single frontier. Each node in the tree can be seen as an independent task of finding the shortest path between the current start and current goal. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. Theoretical results give insights as to when this approach will work and experimental data validates the algorithm for a broad range of domains.

IJCAI Conference 2009 Conference Paper

• Carsten Moldenhauer
• Nathan R. Sturtevant

Moving target search (MTS) or the game of cops and robbers has a broad field of application reaching from law enforcement to computer games. Within the recent years research has focused on computing move policies for one or multiple pursuers (cops). The present work motivates to extend this perspective to both sides, thus developing algorithms for the target (robber). We investigate the game with perfect information for both players and propose two new methods, named TrailMax and Dynamic Abstract Trailmax, to compute move policies for the target. Experiments are conducted by simulating games on 20 maps of the commercial computer game Baldur’s Gate and measuring survival time and computational complexity. We test seven algorithms: Cover, Dynamic Abstract Minimax, minimax, hill climbing with distance heuristic, a random beacon algorithm, TrailMax and DA- TrailMax. Analysis shows that our methods outperform all the other algorithms in quality, achieving up to 98% optimality, while meeting modern computer game computation time constraints.