BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this note, we observe that X∈(GC) if X admits Chebyshev center for any finite set in it. This answers the problem raised by Veselý, addressed in [{\em Generalized centers of finite sets in Banach spaces}, Acta Math. Univ. Comenian. (N.S.) {\bf 66}(1) (1997), 83--115]. We extend our observation towards the fact that the property (GC) is not a 3-space property.
In this paper, we initiate the study of fair clustering that ensures distributional similarity among similar individuals. In response to improving fairness in machine learning, recent papers have investigated fairness in clustering algorithms and have focused on the paradigm of statistical parity/group fairness. These efforts attempt to minimize bias against some protected groups in the population. However, to the best of our knowledge, the alternative viewpoint of individual fairness, introduced by Dwork et al. (ITCS 2012) in the context of classification, has not been considered for clustering so far. Similar to Dwork et al., we adopt the individual fairness notion which mandates that similar individuals should be treated similarly for clustering problems. We use the notion of f-divergence as a measure of statistical similarity that significantly generalizes the ones used by Dwork et al. We introduce a framework for assigning individuals, embedded in a metric space, to probability distributions over a bounded number of cluster centers. The objective is to ensure (a) low cost of clustering in expectation and (b) individuals that are close to each other in a given fairness space are mapped to statistically similar distributions. We provide an algorithm for clustering with p-norm objective (k-center, k-means are special cases) and individual fairness constraints with provable approximation guarantee. We extend this framework to include both group fairness and individual fairness inside the protected groups. Finally, we observe conditions under which individual fairness implies group fairness. We present extensive experimental evidence that justifies the effectiveness of our approach.
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1+ε)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity-c mimicking networks with O(kc4) edges exist and can be found in time m(clogn)O(c). We also give a separate algorithm that constructs such graphs with k⋅O(c)2c edges in time mcO(c)logO(1)n. These results lead to the first data structures for answering fully dynamic offline c-edge-connectivity queries for c≥4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
Given a graph G=(V,E), capacities w(e) on edges, and a subset of terminals T⊆V:∣T∣=k, a mimicking network for (G,T) is a graph (H,w′) that contains copies of T and preserves the value of minimum cuts separating any subset A,B⊆T of terminals. Mimicking networks of size 22k are known to exist and can be constructed algorithmically, while the best known lower bound is 2Ω(k); therefore, an exponential size is required if one aims at preserving cuts exactly. In this paper, we study mimicking networks that preserve connectivity of the graph exactly up to the value of c, where c is a parameter. This notion of mimicking network is sufficient for some applications, as we will elaborate. We first show that a mimicking of size 3c⋅k exists, that is, we can preserve cuts with small capacity using a network of size linear in k. Next, we show an algorithm that finds such a mimicking network in time 2O(c2)poly(m).
Online algorithms are usually analyzed using the notion of competitive ratio which compares the solution obtained by the algorithm to that obtained by an online adversary for the worst possible input sequence. Often this measure turns out to be too pessimistic, and one popular approach especially for scheduling problems has been that of "resource augmentation" which was first proposed by Kalyanasundaram and Pruhs. Although resource augmentation has been very successful in dealing with a variety of objective functions, there are problems for which even a (arbitrary) constant speedup cannot lead to a constant competitive algorithm. In this paper we propose a "rejection model" which requires no resource augmentation but which permits the online algorithm to not serve an epsilon-fraction of the requests. The problems considered in this paper are in the restricted assignment setting where each job can be assigned only to a subset of machines. For the load balancing problem where the objective is to minimize the maximum load on any machine, we give $O(\log^2 1/\eps)$-competitive algorithm which rejects at most an $\eps$-fraction of the jobs. For the problem of minimizing the maximum weighted flow-time, we give an $O(1/\eps^4)$-competitive algorithm which can reject at most an $\eps$-fraction of the jobs by weight. We also extend this result to a more general setting where the weights of a job for measuring its weighted flow-time and its contribution towards total allowed rejection weight are different. This is useful, for instance, when we consider the objective of minimizing the maximum stretch. We obtain an $O(1/\eps^6)$-competitive algorithm in this case. Our algorithms are immediate dispatch, though they may not be immediate reject. All these problems have very strong lower bounds in the speed augmentation model.
We describe a primal-dual framework for the design and analysis of online convex optimization algorithms for {\em drifting regret}. Existing literature shows (nearly) optimal drifting regret bounds only for the ℓ2 and the ℓ1-norms. Our work provides a connection between these algorithms and the Online Mirror Descent ($\omd$) updates; one key insight that results from our work is that in order for these algorithms to succeed, it suffices to have the gradient of the regularizer to be bounded (in an appropriate norm). For situations (like for the ℓ1 norm) where the vanilla regularizer does not have this property, we have to {\em shift} the regularizer to ensure this. Thus, this helps explain the various updates presented in \cite{bansal10, buchbinder12}. We also consider the online variant of the problem with 1-lookahead, and with movement costs in the ℓ2-norm. Our primal dual approach yields nearly optimal competitive ratios for this problem.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.