Hybrid practices are emerging that integrate creative materials like paint, clay, and cloth with intangible immaterials like computation, electricity, and heat. This work aims to expand the design potential of immaterial elements by transforming them into manipulatable, observable and intuitive materials. We explore one such immaterial, electric heat, and develop a maker-friendly fabrication pipeline and crafting support tool that allows users to experientially compose resistive heaters that generate heat spatially and temporally. These heaters are then used to couple heat and thermoreactive materials in a class of artifacts we term Thermoreactive Composites (TrCs). In a formal user study, we observe how designing fabrication workflows along dimensions of composability and perceivability better matches the working styles of material practitioners without domain knowledge of electronics. Through exemplar artifacts, we demonstrate the potential of heat as a creative material and discuss implications for immaterials used within creative practices.

Deep learning has emerged as a powerful tool for feature-driven labeling of datasets. However, for it to be effective, it requires a large and finely labeled training dataset. Precisely labeling a large training dataset is expensive, time-consuming, and error prone. In this article, we present a visually driven deep-learning approach that starts with a coarsely labeled training dataset and iteratively refines the labeling through intuitive interactions that leverage the latent structures of the dataset. Our approach can be used to (a) alleviate the burden of intensive manual labeling that captures the fine nuances in a high-dimensional dataset by simple visual interactions, (b) replace a complicated (and therefore difficult to design) labeling algorithm by a simpler (but coarse) labeling algorithm supplemented by user interaction to refine the labeling, or (c) use low-dimensional features (such as the RGB colors) for coarse labeling and turn to higher-dimensional latent structures that are progressively revealed by deep learning, for fine labeling. We validate our approach through use cases on three high-dimensional datasets and a user study.

We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with release time, deadline and required processing length. The jobs need to be scheduled so that at most g jobs can be running on a machine at any given time. The duration for which a machine is active (i.e., "on") is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4-approximation is known for this problem. We develop a new combinatorial algorithm that is a $3$-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, that is, where g is unbounded. For arbitrary g, this yields an algorithm that is 2$-approximate.

In this work, we introduce the Cov-MECF framework, a special case of minimum-edge cost flow in which the input graph is bipartite. We observe that several important covering (and multi-covering) problems are captured in this unifying model and introduce a new heuristic LPO for any problem in this framework. The essence of LPO harnesses as an oracle the fractional solution in deciding how to greedily modify the partial solution. We empirically establish that this heuristic returns solutions that are higher in quality than those of Wolsey's algorithm. We also apply the analogs of Leskovec et. al.'s [25] optimization to LPO and introduce a further freezing optimization to both algorithms. We observe that the former optimization generally benefits LPO more than Wolsey's algorithm, and that the additional freezing step often corrects suboptimalities while further reducing the number of subroutine calls. We tested these implementations on randomly generated testbeds, several instances from the Second DIMACS Implementation Challenge and a couple networks modeling real-world dynamics.

Broadcast Scheduling is a popular method for disseminating information in response to client requests. There are n pages of information, and clients request pages at different times. However, multiple clients can have their requests satisfied by a single broadcast of the requested page. In this article, we consider several related broadcast scheduling problems. One central problem we study simply asks to minimize the maximum response time (over all requests). Another related problem we consider is the version in which every request has a release time and a deadline, and the goal is to maximize the number of requests that meet their deadlines. While approximation algorithms for both these problems were proposed several years back, it was not known if they were NP-complete. One of our main results is that both these problems are NP-complete. In addition, we use the same unified approach to give a simple NP-completeness proof for minimizing the sum of response times. A very complicated proof was known for this version. Furthermore, we give a proof that FIFO is a 2-competitive online algorithm for minimizing the maximum response time (this result had been claimed earlier with no proof) and that there is no better deterministic online algorithm (this result was claimed earlier as well, but with an incorrect proof).