In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we show how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, we succeed in improving the complexity of rectangular matrix multiplication. Let $\alpha$ denote the maximum value such that the product of an $n\times n^\alpha$ matrix by an $n^\alpha\times n$ matrix can be computed with $O(n^{2+\epsilon})$ arithmetic operations for any $\epsilon>0$. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound $\alpha>0.31389$, which improves the previous lower bound $\alpha>0.30298$ obtained five years ago by Le Gall (FOCS'12) from the analysis of the second power of the Coppersmith-Winograd tensor. More generally, we give faster algorithms computing the product of an $n\times n^k$ matrix by an $n^k\times n$ matrix for any value $k\neq 1$. (In the case $k=1$, we recover the bounds recently obtained for square matrix multiplication). These improvements immediately lead to improvements in the complexity of a multitude of fundamental problems for which the bottleneck is rectangular matrix multiplication, such as computing the all-pair shortest paths in directed graphs with bounded weights.

Aug 21 2017

cs.DS arXiv:1708.05611v1

In this paper, we introduce the online service with delay problem. In this problem, there are $n$ points in a metric space that issue service requests over time, and a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, that has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm. The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We hope this technique will be useful for related problems such as reordering buffer management, online TSP, vehicle routing, etc. We also generalize our results to $k > 1$ servers.

We consider the problem of constructing a bipartite graph whose degrees lie in prescribed intervals. Necessary and sufficient conditions for the existence of such graphs are well-known. However, existing realization algorithms suffer from large running times. In this paper, we present a realization algorithm that constructs an appropriate bipartite graph G=(U,V,E) in O(|U| + |V| + |E|) time, which is asymptotically optimal. In addition, we show that our algorithm produces edge-minimal bipartite graphs and that it can easily be modified to construct edge-maximal graphs.

We revisit the problem of assortment optimization under the multinomial logit choice model with general constraints and propose new efficient optimization algorithms. Our algorithms do not make any assumptions on the structure of the feasible sets and in turn do not require a compact representation of constraints describing them. For the case of cardinality constraints, we specialize our algorithms and achieve time complexity sub-quadratic in the number of products in the assortment (existing methods are quadratic or worse). Empirical validations using the billion prices dataset and several retail transaction datasets show that our algorithms are competitive even when the number of items is 10^5 and beyond (100x larger instances than previously studied), supporting their practicality in data driven revenue management applications.