In this talk we address a dynamic variant of the classic NP-complete bin packing problem. In the bin packing problem we are presented with items of various sizes, s_1,s_2,...,s_n<=1, which we are required to pack into unit-sized bins, where the objective is to minimize the number of bins used. Bin packing can be used to model the problem of data backup, while attempting to minimize the number of disks used to backup the data. This problem is unfortunately known to be NP complete, and so it is unlikely that there is an efficient algorithm to compute an optimal solution to this problem.

For More Information, Contact:

We give an m{1+o(1)}\β{o(1)}-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix. Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk.

For More Information, Contact:

Consider the multi-level aggregation problem in a weighted rooted tree. In this problem, requests arrive over time at the nodes of the tree. where each request specifies a deadline. A request needs to be served by sending it to the root before its deadline at a cost equal to the weight of the path from its node to the root. However, requests from different nodes can also be aggregated and served together so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes containing the requests.

For More Information, Contact:

With the emergence of big-data technologies, computing systems are growing rapidly in size and becoming more and more complex, making it costly to conduct experiments and simulations.  Therefore, modeling computing systems and characterizing their performance analytically are more critical than ever in identifying bottlenecks, informing system design, and facilitating provisioning decision-making.  In this talk, I will illustrate how we use asymptotic analysis to characterize delay performance.  The primary focus is on the asymptotic regime where the number of servers in the system becomes

For More Information, Contact:

This thesis proposes using more sophisticated exploration techniques to bring theory closer to practice for reinforcement learning algorithms. One technique, directed exploration, involves explicitly performing exploration for specific goals, which can be used to accumulate useful information that can narrow down the possibility space of unknown parameters. When solving multiple tasks either concurrently or sequentially, algorithms can explore distinguishing state--action pairs to cluster similar tasks together and share samples to speed up learning.

For More Information, Contact:

For More Information, Contact:

For More Information, Contact:

Thursday, December 21, 2017 - by

The Association for Computing Machinery has selected Mor Harchol-Balter and Venkatesan Guruswami, both professors in the Computer Science Department, as ACM Fellows in recognition of their major contributions to computer science.

They are among 54 members of the 2017 class of ACM fellows, including MIT’s Shafi Goldwasser, a CMU alumna and Turing Award recipient. They join 33 current and former CMU faculty members previously named as fellows.

For More Information, Contact:

Sunday, December 17, 2017 - by

Libratus, an artificial intelligence that defeated four top professional poker players in No-Limit Texas Hold'em earlier this year, uses a three-pronged approach to master a game with more decision points than atoms in the universe, researchers at Carnegie Mellon University report.

For More Information, Contact:

The presence of aliasing makes modular verification of object-oriented code difficult. If multiple clients depend on the properties of an object, one client may break a property that others depend on.

For More Information, Contact:

Pages

Subscribe to Carnegie Mellon University - Computer Science Department RSS