---
title: "Max Is More than Min: Solving Maximization Problems with Heuristic Search"
authors:
  - "Roni Stern"
  - "Scott Kiesel"
  - "Rami Puzis"
  - "Ariel Felner"
  - "Wheeler Ruml"
doi: ""
url: "https://ijcai.org/proceedings/2015/615"
pdf: "https://ijcai.org/proceedings/2015/0615.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "4324-4329"
track: "Best Papers from Sister Conferences Track"
keywords:
---

# Max Is More than Min: Solving Maximization Problems with Heuristic Search

Roni Stern, Scott Kiesel, Rami Puzis, Ariel Felner, Wheeler Ruml

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 4324-4329.

## Abstract

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra's algorithm, weighted A*, and depth-first search.