Training of discrete latent variable models remains challenging because passing gradient information through discrete units is difficult. We propose a new class of smoothing transformations based on a mixture of two overlapping distributions, and show that the proposed transformation can be used for training binary latent models with either directed or undirected priors. We derive a new variational bound to efficiently train with Boltzmann machine priors. Using this bound, we develop DVAE++, a generative model with a global discrete prior and a hierarchy of convolutional continuous variables. Experiments on several benchmarks show that overlapping transformations outperform other recent continuous relaxations of discrete latent variables including Gumbel-Softmax (Maddison et al., 2016; Jang et al., 2016), and discrete variational autoencoders (Rolfe 2016).

Abstract We consider the wavelength assignment problem in WDM optical networks with multiple parallel fibers: Given a setPof paths, assign a color to each path such that the number of paths with the same color containing any link is at most the number of fibers in the link. Assuming the number of fibers in each link is fixed, we study two optimization problems. One is to minimize the number of colors for coloringP. The other is to color as many paths ofPas possible with a given number of colors. We show that both the minimization and the maximization problems are NP‐hard in star networks with a uniform odd number of fibers. We give polynomial time optimal algorithms for the minimization and maximization problems in star networks with an even number of fibers and in the generalized star networks with a uniform even number of fibers. We also give a 1.58‐approximation algorithm for the maximization problem in the generalized star networks with an arbitrary number of fibers. The algorithms for the maximization problem in the generalized stars are based on our newly developed algorithm, which optimally solves the call control problem in the generalized star networks. The call control algorithm is of independent interest. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We propose efficient implementations of Seymour and Thomas algorithm which, given a planar graph and an integer β, decides whether the graph has the branchwidth at least β. The computational results of our implementations show that the branchwidth of a planar graph can be computed in a practical time and memory space for some instances of size about one hundred thousand edges. Previous studies report that a straightforward implementation of the algorithm is memory consuming, which could be a bottleneck for solving instances with more than a few thousands edges. Our results suggest that with efficient implementations, the memory space required by the algorithm may not be a bottleneck in practice. Applying our implementations, an optimal branch decomposition of a planar graph of practical size can be computed in a reasonable time. Branch-decomposition based algorithms have been explored as an approach for solving many NP-hard problems on graphs. The results of this paper suggest that the approach could be practical.

We consider the wavelength assignment problem in WDM optical networks with multiple parallel fibers: Given a set P of paths, assign a color to each path such that the number of paths with the same color on any link is at most the number of fibers in the link. Assuming the number of fibers in each link is fixed, we study two optimization problems. One is to minimize the number of colors for coloring P. The other is to color as many paths of P as possible with a given number of colors. The main results of the paper are: (1) Both the minimization and maximization problems are NP-hard in stars (thus in spiders) with uniform odd number of fibers. (2) The minimization problem is polynomial time solvable in stars with even number of fibers and in spiders with uniform even number of fibers. The result for spiders implies a (1 + 1/K - 1)-approximation algorithm for the minimization problem in spiders with uniform odd number k of fibers. (3) For the maximization problem, we show that it is polynomial time solvable for spiders with uniform even number of fibers and give a 1.58-approximation algorithm for spiders with arbitrary number of fibers. The algorithms for the maximization problem in spiders are based on our newly developed algorithm which optimally solves the call control problem in spiders. Call control is a well studied problem in communication networks. It is known solvable for stars but is NP-hard and MAX SNP-hard even for depth-3 trees. As the spider is a boundary topology between the star and the tree, the call control algorithm has its independent interests.