Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We consider the following general network design problem. The input is an asymmetric metric (V, c), root [Formula: see text], monotone submodular function [Formula: see text], and budget B. The goal is to find an rrooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasipolynomial time [Formula: see text]approximation algorithm for this problem, in which [Formula: see text] is the number of vertices in an optimal solution. As a consequence, we obtain an [Formula: see text]approximation algorithm for directed (polymatroid) Steiner tree in quasipolynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved [Formula: see text]approximation algorithms for the singlesource buyatbulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and singlesource buyatbulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors).more » « less

We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, cardinalityconstrained, and knapsackconstrained versions of this problem, which are all known to be NPhard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and suitable linearprogram rounding algorithms. We obtain a randomized polynomial time approximation scheme for the unconstrained version and performance guarantees of 50% and [Formula: see text] for the cardinalityconstrained and knapsackconstrained versions, respectively. These bounds improve significantly over prior work. We also obtain a performance guarantee of 38.5% for the assortment problem under more general constraints, such as multidimensional knapsack (where products have multiple attributes and there is a knapsack constraint on each attribute) and partition constraints (where products are partitioned into groups and there is a limit on the number of products selected from each group). In addition, we implemented our algorithms and tested them on random instances available in prior literature. We compared our algorithms against an upper bound obtained using a linear program. Our average performance bounds for the unconstrained, cardinalityconstrained, knapsackconstrained, and partitionconstrained versions are over 99%, 99%, 96%, and 99%, respectively.more » « less

Meila, Marina ; Zhang, Tong (Ed.)

We consider the following general network design problem on directed graphs. The input is an asymmetric metric (V, c), root r in V, monotone submodular function f and budget B. The goal is to find an rrooted arborescence T of cost at most B that maximizes f(T). Our main result is a very simple quasipolynomial time approximation algorithm for this problem, where k ≤ V is the number of vertices in an optimal solution. To the best of our knowledge, this is the first nontrivial approximation ratio for this problem. As a consequence we obtain an O(log^2 k / loglog k) approximation algorithm for directed (polymatroid) Steiner tree in quasipolynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved approximation algorithms for the singlesource buyatbulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio, but improves significantly on the running time. For polymatroid Steiner tree and singlesource buyatbulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are best possible (up to constant factors).more » « less