%0 Conference Paper %B 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) %D 2011 %T Entropy rate superpixel segmentation %A Ming-Yu Liu %A Tuzel, O. %A Ramalingam, S. %A Chellapa, Rama %K balancing function %K Berkeley segmentation benchmark %K Complexity theory %K Entropy %K entropy rate %K graph construction %K graph theory %K graph topology %K greedy algorithm %K Greedy algorithms %K homogeneous clusters %K Image edge detection %K Image segmentation %K matrix algebra %K matroid constraint %K measurement %K pattern clustering %K Random variables %K standard evaluation metrics %K superpixel segmentation %K vector spaces %X We propose a new objective function for superpixel segmentation. This objective function consists of two components: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function encourages clusters with similar sizes. We present a novel graph construction for images and show that this construction induces a matroid - a combinatorial structure that generalizes the concept of linear independence in vector spaces. The segmentation is then given by the graph topology that maximizes the objective function under the matroid constraint. By exploiting submodular and mono-tonic properties of the objective function, we develop an efficient greedy algorithm. Furthermore, we prove an approximation bound of ½ for the optimality of the solution. Extensive experiments on the Berkeley segmentation benchmark show that the proposed algorithm outperforms the state of the art in all the standard evaluation metrics. %B 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) %I IEEE %P 2097 - 2104 %8 2011/06/20/25 %@ 978-1-4577-0394-2 %G eng %R 10.1109/CVPR.2011.5995323 %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 IEEE 25th International Conference on Data Engineering, 2009. ICDE '09 %D 2009 %T Ef?cient Query Evaluation over Temporally Correlated Probabilistic Streams %A Kanagal,B. %A Deshpande, Amol %K Birds %K Computerized monitoring %K correlated probabilistic streams %K correlation structure %K Data engineering %K data mining %K Databases %K Event detection %K Graphical models %K inference mechanisms %K Markov processes %K polynomial time %K probabilistic database %K probabilistic graphical model %K probabilistic query evaluation %K query evaluation %K query planning algorithm %K query plans %K Query processing %K Random variables %K stream processing operator %K Streaming media %X In this paper, we address the problem of efficient query evaluation over highly correlated probabilistic streams. We observe that although probabilistic streams tend to be strongly correlated in space and time, the correlations are usually quite structured (i.e., the same set of dependencies and independences repeat across time) and Markovian (i.e., the state at time "t+1" is independent of the states at previous times given the state at time "t"). We exploit this observation to compactly encode probabilistic streams by decoupling the correlation structure (the set of dependencies) from the actual probability values. We develop novel stream processing operators that can efficiently and incrementally process new data items; our operators are based on the previously proposed framework of viewing probabilistic query evaluation as inference over probabilistic graphical models (PGMs) [P. Sen and A. Deshpande, 2007]. We develop a query planning algorithm that constructs efficient query plans that are executable in polynomial-time whenever possible, and we characterize queries for which such plans are not possible. Finally we conduct an extensive experimental evaluation that illustrates the advantages of exploiting the structured nature of correlations in probabilistic streams. %B IEEE 25th International Conference on Data Engineering, 2009. ICDE '09 %I IEEE %P 1315 - 1318 %8 2009/04/29/March %@ 978-1-4244-3422-0 %G eng %R 10.1109/ICDE.2009.229 %0 Conference Paper %B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings %D 2002 %T Dependent rounding in bipartite graphs %A Gandhi,R. %A Khuller, Samir %A Parthasarathy,S. %A Srinivasan, Aravind %K Application software %K Approximation algorithms %K bipartite graph %K bipartite graphs %K broadcast channels %K broadcast scheduling %K Broadcasting %K capacitated vertex cover %K Character generation %K computational complexity %K Computer science %K Delay %K edge-sets %K Educational institutions %K fair scheduling %K fractional vectors %K graph theory %K per-user fairness properties %K pipage rounding technique %K Processor scheduling %K Random variables %K random-graph models %K randomized rounding approach %K rounding method %K scheduling %K Scheduling algorithm %K telecommunication computing %K unrelated parallel machines %X We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties. %B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings %I IEEE %P 323 - 332 %8 2002/// %@ 0-7695-1822-2 %G eng %R 10.1109/SFCS.2002.1181955