Source author record

Riley Murray

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.AG math.OC

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Sublinear Circuits and the Constrained Signomial Nonnegativity Problem

Conditional Sums-of-AM/GM-Exponentials (conditional SAGE) is a decomposition method to prove nonnegativity of a signomial or polynomial over some subset $X$ of real space. In this article, we undertake the first structural analysis of conditional SAGE signomials for convex sets $X$ . We introduce the $X$ -circuits of a finite subset $\mathcal{A} \subset \mathbb{R}^n$ , which generalize the simplicial circuits of the affine-linear matroid induced by $\mathcal{A}$ to a constrained setting. The $X$ -circuits serve as the main tool in our analysis and exhibit particularly rich combinatorial properties for polyhedral $X$ , in which case the set of $X$ -circuits is comprised of one-dimensional cones of suitable polyhedral fans. The framework of $X$ -circuits transparently reveals when an $X$ -nonnegative conditional AM/GM-exponential can in fact be further decomposed as a sum of simpler $X$ -nonnegative signomials. We develop a duality theory for $X$ -circuits with connections to geometry of sets that are convex according to the geometric mean. This theory provides an optimal power cone reconstruction of conditional SAGE signomials when $X$ is polyhedral. In conjunction with a notion of reduced $X$ -circuits, the duality theory facilitates a characterization of the extreme rays of conditional SAGE cones. Since signomials under logarithmic variable substitutions give polynomials, our results also have implications for nonnegative polynomials and polynomial optimization.

preprint2016arXiv

Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms [Full Version]

The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of N jobs on M distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into M "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.