We present a new method for cell segmentation which combines a marked point process model with a combinatorics-based method of finding global optima. The method employs an energy term that assesses possible segmentations by their fidelity to both local image information and a simple model of cell interaction, and we use a randomized iterative reweighting technique for its minimization. Our approach was successfully applied to cell microscopy images of varying difficulty and experimentally compared with both a standard segmentation method as well as a method based on Multiple Birth and cut. The proposed method is found to improve upon previous approaches.