
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
In this paper, we focus on the less studied scenario of $alpha > 1$ with a posi tive startup cost $sigma > 0$. Now, the cost function $f(cdot)$ is neither sub additive nor superadditive. This is motivated by minimizing networkwide energy consumption when supporting a set of traffic demands. It is commonly accepted that, for some computing and communication devices, doubling processing speed mo re than doubles the energy consumption. Hence, in Economics parlance, such a cos t function reflects emph{diseconomies of scale}.
We begin by discussing why existing routing techniques such as randomized roundi ng and treemetric embedding fail to generalize directly. We then present our m ain contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitat ed mincost flow problem that we believe is interesting in its own right. Our ap proach for this problem builds upon the welllinked decomposition due to Chekuri KhannaShepherd~cite{ChekuriKS05}, the construction of expanders via matchings due to KhandekarRaoVazirani~cite{KhandekarRV06}, and edgedisjoint routing i n wellconnected graphs due to RaoZhou~cite{RaoZ06}. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature.