We show that there is a largely unexplored class of functions (positive polyma-troids) that can define proper discrete metrics over pairs of binary vectors andthat are fairly tractable to optimize over. By exploiting submodularity, we areable to give hardness results and approximation algorithms for optimizing oversuch metrics. Additionally, we demonstrate empirically the effectiveness of thesemetrics and associated algorithms on both a metric minimization task (a form ofclustering) and also a metric maximization task (generating diversek-best lists).