Jack Zhang

Approximate solution of infinite-horizon risk-sensitive Markov decision processes

Categories Dynamic Programming, Other Topics Tags , ,

Infinite-horizon risk-sensitive Markov decision processes (MDPs) under the discounted cost criterion are challenging to solve because the optimal policy may be nonstationary. Existing methods  typically reformulate the problem as a continuous-state risk-neutral MDP and rely on state discretization or value-function approximation, often without explicit stopping conditions or error bounds. In this paper, we present approximate … Read more

Partitioning a graph into low-diameter clusters

Categories Branch and Cut Algorithms, Combinatorial Optimization, Network Optimization Tags , , , ,

This paper studies the problems of partitioning the vertices of a graph G = (V,E) into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at … Read more

Linear-size formulations for connected planar graph partitioning and political districting

Categories Combinatorial Optimization, Integer Programming, Network Optimization

Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more