Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski's famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.
Every ten years, when states are forced to redraw their congressional districts, the process is intensely partisan, and the outcome is rarely fair and democratic. In the last few decades, the growing capabilities of computers have offered the promise of objective, computerized redistricting. Unfortunately, the redistricting problem can be shown to be NP-Complete, but there are a number of approximation algorithms and heuristics that are effective. We specifically define the redistricting problem and analyze two new algorithms. By comparing our new algorithms based on compactness and population deviation to existing algorithms and the actual districts, we demonstrate the tradeoffs of different algorithm components. We extend an approximation algorithm for the capacitated k-center problem by Khuller and Sussmann to this redistricting problem and show that these modifications maintain their original 5-approximation bounds under some conditions. We also introduce a divide and conquer heuristic that produces redistricting plans with the optimal population deviation in most U.S. states. In experiments, we show that our divide and conquer heuristic produces the best population deviation but a worse compactness score than an existing simulated annealing approach by Olson. While the modified capacitated k-center approach offers guarantees under certain conditions, it tends to only produce valid plans in small states.