The widely studiedGeneralized Min-Sum-Set-Cover(GMSSC) problem serves as a formal model for the setting above. GMSSC is NP-hard and the standard application ofno-regretonline learning algorithms iscomputationally inefficient, because they operate in the space of rankings. In this work, we show how to achievelowregret for GMSSC inpolynomial-time.

Layer fusion techniques are critical to improving the inference efficiency of deep neural networks (DNN) for deployment. Fusion aims to lower inference costs by reducing data transactions between an accelerator's on-chip buffer and DRAM. This is accomplished by grouped execution of multiple operations like convolution and activations together into single execution units - fusion groups. However, on-chip buffer capacity limits fusion group size and optimizing fusion on whole DNNs requires partitioning into multiple fusion groups. Finding the optimal groups is a complex problem where the presence of invalid solutions hampers traditional search algorithms and demands robust approaches. In this paper we incorporate Explainable AI, specifically Graph Explanation Techniques (GET), into layer fusion. Given an invalid fusion group, we identify the operations most responsible for group invalidity, then use this knowledge to recursively split the original fusion group via a greedy tree-based algorithm to minimize DRAM access. We pair our scheme with common algorithms and optimize DNNs on two types of layer fusion: Line-Buffer Depth First (LBDF) and Branch Requirement Reduction (BRR). Experiments demonstrate the efficacy of our scheme on several popular and classical convolutional neural networks like ResNets and MobileNets. Our scheme achieves over 20% DRAM Access reduction on EfficientNet-B3.

The facility location problem (FLP) is a classical combinatorial In real cities, facility layout tends to deviate from residential demands optimization challenge aimed at strategically laying out facilities for corresponding services, leading to costly travel [12, 13]. to maximize their accessibility. In this paper, we propose a reinforcement Therefore, optimizing accessibility by strategically locating urban learning method tailored to solve large-scale urban facilities is crucial for creating more sustainable and inclusive cities. FLP, capable of producing near-optimal solutions at superfast inference In fact, facility location problem (FLP) is a classic combinatorial speed. We distill the essential swap operation from local optimization (CO) problem [2, 8], which is notoriously challenging search, and simulate it by intelligently selecting edges on a graph due to the NP-hardness inherent in selecting urban regions to of urban regions, guided by a knowledge-informed graph neural place facilities from candidate regions [5]. As both and are network, thus sidestepping the need for heavy computation typically large in urban contexts, designing a reliable algorithm that of local search. Extensive experiments on four US cities with different delivers satisfactory solutions within reasonable timeframes is difficult.

We study a fundamental model of online preference aggregation, where an algorithm maintains an ordered list of $n$ elements. An input is a stream of preferred sets $R_1, R_2, \dots, R_t, \dots$. Upon seeing $R_t$ and without knowledge of any future sets, an algorithm has to rerank elements (change the list ordering), so that at least one element of $R_t$ is found near the list front. The incurred cost is a sum of the list update costs (the number of swaps of neighboring list elements) and access costs (position of the first element of $R_t$ on the list). This scenario occurs naturally in applications such as ordering items in an online shop using aggregated preferences of shop customers. The theoretical underpinning of this problem is known as Min-Sum Set Cover. Unlike previous work (Fotakis et al., ICALP 2020, NIPS 2020) that mostly studied the performance of an online algorithm ALG against the static optimal solution (a single optimal list ordering), in this paper, we study an arguably harder variant where the benchmark is the provably stronger optimal dynamic solution OPT (that may also modify the list ordering). In terms of an online shop, this means that the aggregated preferences of its user base evolve with time. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is $O(r^2)$ and prove the existence of a deterministic $O(r^4)$-competitive algorithm. Here, $r$ is the maximum cardinality of sets $R_t$. This is the first algorithm whose ratio does not depend on $n$: the previously best algorithm for this problem was $O(r^{3/2} \cdot \sqrt{n})$-competitive and $\Omega(r)$ is a lower bound on the performance of any deterministic online algorithm.

We consider the non-metric data placement problem and develop distributed algorithms for computing or approximating its optimal integral solution. We first show that the non-metric data placement problem is inapproximable up to a logarithmic factor. We then provide a game-theoretic decomposition of the objective function and show that natural Glauber dynamics in which players update their resources with probability proportional to the utility they receive from caching those resources will converge to an optimal global solution for a sufficiently large noise parameter. In particular, we establish the polynomial mixing time of the Glauber dynamics for a certain range of noise parameters. Finally, we provide another auction-based distributed algorithm, which allows us to approximate the optimal global solution with a performance guarantee that depends on the ratio of the revenue vs. social welfare obtained from the underlying auction. Our results provide the first distributed computation algorithms for the non-metric data placement problem.

Data Engineers and data scientists often have to deal with an enormous amount of data. Dealing with such data is not a straightforward task. To process this data as efficiently as possible, we need to have a clear understanding of how the data is organized. So before moving on to the main topic, let us build a basic ground first. Memory in a computer system is organized in a hierarchy (as shown in the diagram below).