This thesis investigates foundational algorithmic challenges that arise when embedding fairness, diversity, explainability, and robustness into computational decision-making. As machine learning systems, resource allocation mechanisms, and data analysis pipelines increasingly influence critical decisions, it is essential that these systems uphold not only efficiency and accuracy but also ethical and structural guarantees. However, enforcing these principles introduces complex trade-offs and computational difficulties.

We address five core problems that capture different facets of algorithmic decision-making under structural and informational constraints: (1) determinant maximization under matroid constraints, modeling the selection of diverse and representative subsets; (2) approximation of the weighted Nash Social Welfare objective, a fairness-centric formulation in indivisible resource allocation; (3) constrained subspace approximation, which enforces group-level representation in data summarization; (4) explainable clustering, which trades off interpretability and clustering quality using decision trees with axis-aligned threshold cuts; and (5) combinatorial optimization using comparison oracles, which enables robust decision-making in uncertain or preference-driven environments.

Each of these problems introduces structural constraints that challenge conventional algorithmic techniques. We develop new frameworks that combine combinatorial methods, convex and non-convex relaxations, convex geometry, and probabilistic methods. The resulting algorithms offer improved approximation guarantees, shed light on key trade-offs between fairness, interpretability, and performance, and support the development of more equitable, interpretable, diverse, and reliable algorithmic systems. These contributions have broad implications in machine learning, economics, data summarization, and human-in-the-loop decision-making.

294 pages

Thesis Committee:
David Woodruff (Co-Chair)
Anupam Gupta (Co-Chair)
Prasad Tetali Mohit Singh (Georgia Institute of Technology)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Creative Commons: CC-BY (Attribution)

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu