%0 Conference Paper %B 2011 Proceedings IEEE INFOCOM %D 2011 %T Approximation algorithms for throughput maximization in wireless networks with delay constraints %A Guanhong Pei %A Anil Kumar,V. S %A Parthasarathy,S. %A Srinivasan, Aravind %K Approximation algorithms %K Approximation methods %K approximation theory %K Delay %K delay constraints %K delays %K general interference model %K Interference %K multihop wireless networks %K optimisation %K Optimized production technology %K radio networks %K radiofrequency interference %K target delay bound %K Throughput %K throughput maximization %K Wireless networks %X We study the problem of throughput maximization in multi-hop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O (logΔm/log log Δm) of the maximum, so that the per-session (end-to-end) delay is O ((logΔm/log log Δm Δ(c))2), where Δm = maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge. %B 2011 Proceedings IEEE INFOCOM %I IEEE %P 1116 - 1124 %8 2011/04/10/15 %@ 978-1-4244-9919-9 %G eng %R 10.1109/INFCOM.2011.5934887 %0 Conference Paper %B 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS) %D 2011 %T Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems %A Li,Jian %A Deshpande, Amol %K Approximation algorithms %K Approximation methods %K combinatorial problems %K Fourier series %K knapsack problems %K optimisation %K OPTIMIZATION %K polynomial approximation %K polynomial time approximation algorithm %K Polynomials %K Random variables %K stochastic combinatorial optimization %K stochastic knapsack %K stochastic shortest path %K stochastic spanning tree %K vectors %X We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error ϵ for any ϵ >; 0, if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above) and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems. %B 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS) %I IEEE %P 797 - 806 %8 2011/10/22/25 %@ 978-1-4577-1843-4 %G eng %R 10.1109/FOCS.2011.33 %0 Conference Paper %B 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) %D 2010 %T New Constructive Aspects of the Lovasz Local Lemma %A Haeupler,B. %A Saha,B. %A Srinivasan, Aravind %K acyclic edge coloring %K Algorithm design and analysis %K Approximation algorithms %K Approximation methods %K computational complexity %K Computer science %K constant factor approximation algorithm %K graph colouring %K Linearity %K Lovasz Local Lemma %K MAX k-SAT %K Monte Carlo Algorithm %K Monte Carlo methods %K Moser-Tardos algorithm %K nonrepetitive graph coloring %K output distribution %K polynomial sized core subset %K Polynomials %K Probabilistc Method %K probabilistic analysis %K probabilistic logic %K probability %K Ramsey type graph %K Sampling methods %K Santa Claus Problem %X The Lov'{a}sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of ``bad'' events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emph{conditional LLL-distribution} – the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized ``core'' subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this. %B 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) %I IEEE %P 397 - 406 %8 2010/10/23/26 %@ 978-1-4244-8525-3 %G eng %R 10.1109/FOCS.2010.45