We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxϵR+nf(x) s.t. Ax ≥ 1, where f:R+n→ R+is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: maxyϵR+mΣj=1myj - g(ATy), where g:R+n→R+is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

We provide a framework for designing competitive online algorithms using regularization, a widely used technique in online learning, particularly in online convex optimization. An online algorithm that uses regularization serves requests by computing a solution, in each step, to an objective function involving a smooth convex regularization function. Applying the technique of regularization allows us to obtain new results in the domain of competitive analysis. We remark that competitive analysis and online learning are two widely studied frameworks for online decision-making settings. We show that even though there are significant differences in assumptions, goals, and techniques between the two fields, one can still benefit by introducing techniques from one field to the other. In our new framework we exhibit a general O(log m)-competitive deterministic algorithm for generating a fractional solution that satisfies a time-varying set of online covering and precedence constraints, where m is the number of variables. This framework allows to incorporate both service costs (over time) and setup costs into a host of applications. We then provide an O(log m log n)-competitive randomized algorithm for the online set cover problem with service cost, where m is the number of sets and n is the number of elements. This model allows for sets to be both added and deleted over time from a solution.

Decision makers often need to take into account multiple conflicting objectives when selecting a solution for their problem. This can result in a potentially large number of candidate solutions to be considered. Visualizing a Pareto Frontier, the optimal set of solutions to a multi-objective problem, is considered a difficult task when the problem at hand spans more than three objective functions. We introduce a novel visual-interactive approach to facilitate coping with multi-objective problems. We propose a characterization of the Pareto Frontier data and the tasks decision makers face as they reach their decisions. Following a comprehensive analysis of the design alternatives, we show how a semantically-enhanced Self-Organizing Map, can be utilized to meet the identified tasks. We argue that our newly proposed design provides both consistent orientation of the 2D mapping as well as an appropriate visual representation of individual solutions. We then demonstrate its applicability with two real-world multi-objective case studies. We conclude with a preliminary empirical evaluation and a qualitative usefulness assessment.

Publish/subscribe based communication systems have become very popular in recent years. Such systems are becoming larger and more complex, and thus require a smart management framework. An important challenge in this context is to efficiently disseminate the data flows sent from the publishers to the subscribers. To this aim, multicast dissemination is often used, requiring a smart mapping of data flows to multicast groups. Most existing publish/subscribe systems use static configuration and thus do not efficiently handle dynamic changes in the publish/subscribe system. In this work, we present a self-managed and self-optimized publish/subscribe system that efficiently adapts to changes in run time. A key element in the solution is a smart mapping algorithm that computes efficient routes for the data flows based on the current conditions in the system. The mapping algorithm takes into account various costs and constraints that are associated with the transition from one mapping to another during run time. The solution we present maintains the publish/subscribe system optimized while at the same time ensuring the stability of the system. We complement our work with a comprehensive simulation study in which we evaluate the suggested solution. The results clearly demonstrate the advantages of a dynamic self-optimized system over a static system.