Two Combinatorial Optimization Problems At The Interface Of Computer Science And Operations Research