Jump to Content

Brian Tagiku

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    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
    Alan Roytman
    APPROX-RANDOM (2013), pp. 287-302
    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
    Aaron Cote
    Green Computing Conference (2010), pp. 175-187
    Minimizing Average Shortest Path Distances via Shortcut Edge Addition
    APPROX-RANDOM (2009), pp. 272-285
    Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
    Douglas E. Carroll
    APPROX-RANDOM (2009), pp. 29-41