Zobrazeno 1 - 10
of 34
pro vyhledávání: '"Post, Ian"'
We consider the rooted prize-collecting walks (PCW) problem, wherein we seek a collection $C$ of rooted walks having minimum prize-collecting cost, which is the (total cost of walks in $C$) + (total node-reward of nodes not visited by any walk in $C$
Externí odkaz:
http://arxiv.org/abs/2111.07414
Publikováno v:
SIAM J. Comput. 47(4): 1667-1704 (2018)
Graphs with bounded highway dimension were introduced by Abraham et al. [SODA 2010] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion
Externí odkaz:
http://arxiv.org/abs/1502.04588
Autor:
Post, Ian, Swamy, Chaitanya
We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of $k$ vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the tot
Externí odkaz:
http://arxiv.org/abs/1411.4573
We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n
Externí odkaz:
http://arxiv.org/abs/1208.5083
We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless $NP = RP$. Since the Greedy algorithm is known to be 1/2-competitive for mono
Externí odkaz:
http://arxiv.org/abs/1204.1025
In this paper we give a construction of cut sparsifiers of Benczur and Karger in the {\em dynamic} streaming setting in a single pass over the data stream. Previous constructions either required multiple passes or were unable to handle edge deletions
Externí odkaz:
http://arxiv.org/abs/1203.4900
Infrastructure-as-a-Service (IaaS) providers need to offer richer services to be competitive while optimizing their resource usage to keep costs down. Richer service offerings include new resource request models involving bandwidth guarantees between
Externí odkaz:
http://arxiv.org/abs/1202.3683
Credit networks represent a way of modeling trust between entities in a network. Nodes in the network print their own currency and trust each other for a certain amount of each other's currency. This allows the network to serve as a decentralized pay
Externí odkaz:
http://arxiv.org/abs/1007.0515
Autor:
Goel, Ashish, Post, Ian
We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing
Externí odkaz:
http://arxiv.org/abs/1004.2291
Autor:
Goel, Ashish, Post, Ian
We consider the single-source (or single-sink) buy-at-bulk problem with an unknown concave cost function. We want to route a set of demands along a graph to or from a designated root node, and the cost of routing x units of flow along an edge is prop
Externí odkaz:
http://arxiv.org/abs/0908.3740