Data Structures and Algorithms (cs.DS)

  • PDF
    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.
  • PDF
    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.
  • PDF
    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.
  • PDF
    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.

Recent comments

Māris Ozols Feb 21 2017 15:35 UTC

I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

...(continued)
Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

Māris Ozols Oct 21 2016 21:06 UTC

Very nice! Now we finally know how to fairly cut a cake in a finite number of steps! What is more, the number of steps is expected to go down from the whopping $n^{n^{n^{n^{n^n}}}}$ to just barely $n^{n^n}$. I can't wait to get my slice!

https://www.quantamagazine.org/20161006-new-algorithm-solve

...(continued)
Ashley Apr 21 2015 18:42 UTC

Thanks for the further comments and spotting the new typos. To reply straight away to the other points:

First, the resulting states might as well stay in the same bin (even though, as you rightly note, the bins no longer correspond to the same bit-strings as before). All that matters is that the

...(continued)
Perplexed Platypus Apr 21 2015 14:55 UTC

Thanks for updating the paper so promptly. The updated version addresses all my concerns so far. However I noticed a few extra (minor) things while reading through it.

On page 15, last step of 2(b): if $|\psi_r\rangle$ and $|\psi_t\rangle$ were in the same bin but the combination operation failed

...(continued)
Ashley Apr 20 2015 16:27 UTC

Thank you for these very detailed and helpful comments. I have uploaded a new version of the paper to the arXiv to address them, which should appear tomorrow. I will reply to the comments in more detail (and justify the cases where I didn't modify the paper as suggested) when I receive them through

...(continued)
Perplexed Platypus Apr 13 2015 22:37 UTC

**Summary and recommendation**

This paper considers a $d$-dimensional version of the problem of finding a given pattern within a text, for random patterns and text. The text is assumed to be picked uniformly at random and has size $n^d$ while the pattern has size $m^d$ and is either uniformly ran

...(continued)
Ashley Apr 12 2015 13:01 UTC

Thanks for the clarification. In fact it seems that I do have this option switched on, with the correct author identifier, so I'm not sure why I didn't get an email about these comments.

Perplexed Platypus Apr 10 2015 13:18 UTC

Hi Ashley,

Thanks for your reply, it was very helpful! I thought about e-mailing you but I wanted to preserve my confidentiality as a reviewer. Also, I wanted to see if it is feasible to use SciRate as a platform for interacting with authors during the review process.

I encourage you (and **ot

...(continued)
Ashley Apr 09 2015 20:03 UTC

Hi,

Thank you for your very detailed comments / questions about the technical points in this paper. I did happen to check Scirate today but in general (as I suspect with many other people) I don't check it regularly, so for reliable replies it's better just to email me. To reply to your questions i

...(continued)