Brian Tagiku
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Coupled and k-Sided Placements: Generalizing Generalized Assignment
Madhukar Korupolu
Rajmohan Rajaraman
Integer Programming and Combinatorial Optimization (IPCO) (2014)
Preview abstract
In modern datacenters and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem (GAP), which concerns the placement of jobs into single nodes providing one kind of service. We also study a further generalization, the k-Sided Placement problem, in which we place jobs into k-tuples of nodes, each node in a tuple offering one of k services.
For both the coupled and k-sided placement problems, we consider minimization and maximization versions. In the minimization versions (MinCP and MinkSP), the goal is to achieve minimum placement cost, while incurring a minimum blowup in the capacity of the individual nodes. Our first main result is an algorithm for MinkSP that achieves optimal cost while increasing capacities by at most a factor of k + 1, also yielding the first constant-factor approximation for MinCP. In the maximization versions (MaxCP and MaxkSP), the goal is to maximize the total weight of the jobs that are placed under hard capacity constraints. MaxkSP can be expressed as a k-column sparse integer program, and can be approximated to within a factor of O(k) factor using randomized rounding of a linear program relaxation. We consider alternative combinatorial algorithms that are much more efficient in practice. Our second main result is a local search based approximation algorithm that yields a 15-approximation and O(k^3)-approximation for MaxCP and MaxkSP respectively. Finally, we consider an online version of MaxkSP and present algorithms that achieve logarithmic competitive ratio under certain necessary technical assumptions.
View details
The survivability of design-specific spare placement in FPGA architectures with high defect rates
Amit Agarwal
Jason Cong
ACM Transactions on Design Automation of Electronic Systems, vol. 18 (2013)
Online Multidimensional Load Balancing
Streaming k-means on Well-Clusterable Data
Vladimir Braverman
Rafail Ostrovsky
Alan Roytman
Michael Shindler
SODA (2011), pp. 26-40
Energy-efficient mobile data transport via online multi-network packet scheduling
Minimizing Average Shortest Path Distances via Shortcut Edge Addition
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
