Arrow Research search

Author name cluster

Samir Khuller

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers
2 author rows

Possible papers

37

AAMAS Conference 2024 Conference Paper

Fair Allocation of Conflicting Courses under Additive Utilities

  • Arpita Biswas
  • Yiduo Ke
  • Samir Khuller
  • Quanquan C. Liu

We investigate the problem of fair allocation of indivisible items when certain item pairs conflict, where conflicts are represented by an interval graph. In this setting, no two conflicting items may be allocated to the same agent. Our problem has practical applications specifically for course allocation where students are agents and course seats are items; courses may have conflicting schedules. We devise algorithms for finding fair, specifically envy-freeness up to one item (EF1), allocations of courses to students in the most general setting: when students have non-uniform, non-identical, additive utility functions. In this extended abstract, we provide one of the algorithms that finds a EF1 solution under identical utilities, implying that, for any course, all students have the same utility.

PDF

ICML Conference 2022 Conference Paper

Individual Preference Stability for Clustering

  • Saba Ahmadi
  • Pranjal Awasthi
  • Samir Khuller
  • Matthäus Kleindessner
  • Jamie Morgenstern
  • Pattara Sukprasert
  • Ali Vakilian

In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. Our notion can be motivated from several perspectives, including game theory and algorithmic fairness. We study several questions related to our proposed notion. We first show that deciding whether a given data set allows for an IP-stable clustering in general is NP-hard. As a result, we explore the design of efficient algorithms for finding IP-stable clusterings in some restricted metric spaces. We present a polytime algorithm to find a clustering satisfying exact IP-stability on the real line, and an efficient algorithm to find an IP-stable 2-clustering for a tree metric. We also consider relaxing the stability constraint, i. e. , every data point should not be too far from its own cluster compared to any other cluster. For this case, we provide polytime algorithms with different guarantees. We evaluate some of our algorithms and several standard clustering approaches on real data sets.

Details

ICML Conference 2020 Conference Paper

A Pairwise Fair and Community-preserving Approach to k-Center Clustering

  • Brian Brubach
  • Darshan Chakrabarti
  • John Dickerson 0001
  • Samir Khuller
  • Aravind Srinivasan
  • Leonidas Tsepenekas

Clustering is a foundational problem in machine learning with numerous applications. As machine learning increases in ubiquity as a backend for automated systems, concerns about fairness arise. Much of the current literature on fairness deals with discrimination against protected classes in supervised learning (group fairness). We define a different notion of fair clustering wherein the probability that two points (or a community of points) become separated is bounded by an increasing function of their pairwise distance (or community diameter). We capture the situation where data points represent people who gain some benefit from being clustered together. Unfairness arises when certain points are deterministically separated, either arbitrarily or by someone who intends to harm them as in the case of gerrymandering election districts. In response, we formally define two new types of fairness in the clustering setting, pairwise fairness and community preservation. To explore the practicality of our fairness goals, we devise an approach for extending existing $k$-center algorithms to satisfy these fairness constraints. Analysis of this approach proves that reasonable approximations can be achieved while maintaining fairness. In experiments, we compare the effectiveness of our approach to classical $k$-center algorithms/heuristics and explore the tradeoff between optimal clustering and fairness.

Details

IJCAI Conference 2020 Conference Paper

An Algorithm for Multi-Attribute Diverse Matching

  • Saba Ahmadi
  • Faez Ahmed
  • John P. Dickerson
  • Mark Fuge
  • Samir Khuller

Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e. g. , linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e. g. , country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application. The source code is made available at https: //github. com/faezahmed/diverse_matching.

PDF Details DOI

TCS Journal 2019 Journal Article

Select and permute: An improved online framework for scheduling to minimize weighted completion time

  • Samir Khuller
  • Jingling Li
  • Pascal Sturmfels
  • Kevin Sun
  • Prayaag Venkat

In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et al. (1997) [11] and Garg et al. (2007) [9], who show how to convert an offline approximation to an online scheme. Our framework uses two offline approximation algorithms—one for the simpler problem of scheduling without release times, and another for the minimum unscheduled weight problem—to create an online algorithm with provably good competitive ratios. We illustrate multiple applications of this method that yield improved competitive ratios. Our framework gives algorithms with the best or only-known competitive ratios for the concurrent open shop, coflow, and concurrent cluster models. We also introduce a randomized variant of our framework based on the ideas of Chakrabarti et al. (1996) [3] and use it to achieve improved competitive ratios for these same problems.

Details DOI

SODA Conference 2014 Conference Paper

Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

  • Samir Khuller
  • Manish Purohit
  • Kanthi K. Sarpatwar

We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem (P cds ), we are given an undirected graph G = ( V, E ) and an integer n′, and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n′ vertices. We obtain the first polynomial time algorithm with an O (lnΔ) approximation factor for this problem, thereby significantly extending the results of Guha and Khuller (Algorithmica, Vol. 20(4), Pages 374–387, 1998) for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem (B cds ), there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a “special” submodular function. This generalization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies a O (ln q ) approximation (where q denotes the quota) and an O (1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function.

Details

FOCS Conference 2012 Conference Paper

LP Rounding for k-Centers with Non-uniform Hard Capacities

  • Marek Cygan
  • MohammadTaghi Hajiaghayi
  • Samir Khuller

In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, so that we respect the capacity constraints on centers. The objective is to minimize the maximum distance a node has to travel to get to its assigned center. This problem is NP-hard, even when centers have no capacity restrictions and optimal factor 2 approximation algorithms are known. With capacities, when all centers have identical capacities, a 6 approximation is known with no better lower bounds than for the infinite capacity version. While many generalizations and variations of this problem have been studied extensively, no progress was made on the capacitated version for a general capacity function. We develop the first constant factor approximation algorithm for this problem. Our algorithm uses an LP rounding approach to solve this problem, and works for the case of non-uniform hard capacities, when multiple copies of a node may not be chosen and can be extended to the case when there is a hard bound on the number of copies of a node that may be selected. Finally, for non-uniform soft capacities we present a much simpler 11-approximation algorithm, which we find as one more evidence that hard capacities are much harder to deal with.

Details

SODA Conference 2010 Conference Paper

Energy Efficient Scheduling via Partial Shutdown

  • Samir Khuller
  • Jian Li 0015
  • Barna Saha

Motivated by issues of saving energy in data centers we define a collection of new problems referred to as “machine activation” problems. The central framework we introduce considers a collection of m machines (unrelated or related) with each machine i having an activation cost of a i. There is also a collection of n jobs that need to be performed, and p i, j is the processing time of job j on machine i. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of A – we would like to select a subset S of the machines to activate with total cost a ( S ) ≤ A and find a schedule for the n jobs on the machines in S minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine i has activation cost a i and speed s i, and the processing time of job j on machine i is, where p j is the processing requirement of job j. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan T and activation cost A then we can obtain a schedule with makespan (2 + ε) T and activation cost, for any ε > 0. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. In addition, we present a greedy algorithm which only works for the basic version and yields a makespan of 2 T and an activation cost A (1 + ln n ). For the uniformly related parallel machine scheduling problem, we develop a polynomial time approximation scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most A and the makespan is at most (1 + ε) T for any ε > 0. For the special case of m identical speed machines, the machine activation problem is trivial, since the cheapest subset of k machines is always the best choice if the optimal solution activates k machines. In addition, we consider the case when some jobs can be dropped (and are treated as outliers).

Details

FOCS Conference 2002 Conference Paper

Dependent Rounding in Bipartite Graphs

  • Rajiv Gandhi
  • Samir Khuller
  • Srinivasan Parthasarathy 0002
  • Aravind Srinivasan

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.

Details

TCS Journal 2000 Journal Article

Fault tolerant K-center problems

  • Samir Khuller
  • Robert Pless
  • Yoram J. Sussmann

The basic K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve an approximation factor of 2 have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of α (α⩽K) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least α centers close to it. In the second version, each vertex that does not have a center placed on it is required to have at least α centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for any α. For the first version we give an algorithm that achieves an approximation factor of 3 for any α, and achieves an approximation factor of 2 for α<4. For the second version, we provide algorithms with approximation factors of 2 for any α. The best possible approximation factor for even the basic K-center problem is 2, assuming P≠NP. In addition, we give a polynomial time approximation algorithm for a generalization of the K-supplier problem where a subset of at most K supplier nodes must be selected as centers so that every demand node has at least α centers close to it. For this version our approximation factor is 3. The best possible approximation factor for even the basic K-supplier problem is 3, assuming P≠NP.

Details DOI

I&C Journal 1999 Journal Article

Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets

  • Sudipto Guha
  • Samir Khuller

In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy approximation algorithm based on “spider decompositions” was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2ln k, wherekis the number of terminals. However, the best known lower bound on the approximation ratio is (1−o(1))ln k, assuming thatNP⊈DTIME[n O(loglog n)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of ln k. For the weighted case we develop a new decomposition theorem and generalize the notion of “spiders” to “branch-spiders” that are used to design a new algorithm with a worst case approximation factor of 1. 5ln k. We then generalize the method to yield an approximation factor of (1. 35+ε)ln k, for any constantε>0. These algorithms, although polynomial, are not very practical due to their high running time, since we need to repeatedly find many minimum weight matchings in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1. 6103ln k. The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by 0–1 proper functions as well. These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was 3ln nby Guha and Khuller. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor of (1. 35+ε)ln nfor any fixedε>0.

Details DOI

FOCS Conference 1995 Conference Paper

The Loading Time Scheduling Problem (Extended Abstract)

  • Randeep Bhatia
  • Samir Khuller
  • Joseph Naor

In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the shortest common supersequence problem. We use the same algorithmic technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines, and for the weighted shortest common supersequence problem.

Details

TCS Journal 1994 Journal Article

On-line algorithms for weighted bipartite matching and stable marriages

  • Samir Khuller
  • Stephen G. Mitchell
  • Vijay V. Vazirani

We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This algorithm is optimal - there is no on-line deterministic algorithm that achieves a competitive ratio better than (2n−1) in all metric spaces. We also study the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple “first come, first served” deterministic algorithm yields on the average O(n log n) unstable pairs, but in the worst case no deterministic or randomized on-line algorithm can do better than ω(n 2) unstable pairs. This appears to be the first on-line problem for which provably one cannot do better with randomization; for most on-line problems studied in the past, randomization has helped in improving the performance.

Details DOI

STOC Conference 1992 Conference Paper

Biconnectivity Approximations and Graph Carvings

  • Samir Khuller
  • Uzi Vishkin

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP -hard. We consider the problem of finding an approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity our algorithm guarantees a solution that is no more than 5/3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP -hard as well. We also consider the case where the graph has edge weights. We show that an approximation factor of 2 is possible in polynomial time for finding a k -edge connected spanning subgraph. This improves an approximation factor of 3 for k =2 due to [FJ81], and extends it for any k (with an increased running time though).

Details

FOCS Conference 1992 Conference Paper

Efficient Minimum Cost Matching Using Quadrangle Inequality

  • Alok Aggarwal
  • Amotz Bar-Noy
  • Samir Khuller
  • Dina Kravets
  • Baruch Schieber

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red * Blue), where mod Red mod = n, mod Blue mod = m, n >

Details

TCS Journal 1991 Journal Article

Planar graph coloring is not self-reducible, assuming P ≠ NP

  • Samir Khuller
  • Vijay V. Vazirani

We show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of our result is that the schema of Jerrum et al. (1986) cannot be used for approximately counting the number of four colorings of a planar graph. These results extend to planar graph k-coloring, for k⩾4.

Details DOI

I&C Journal 1990 Journal Article

Extending planar graph algorithms to K3,3-free graphs

  • Samir Khuller

For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this paper we extend these algorithms to K 3, 3-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are: graph coloring, depth first search, and maximal independent sets. As a corollary we show that K 3, 3-free graphs are five colorable (this bound is tight).

Details DOI

FOCS Conference 1989 Conference Paper

Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary)

  • Samir Khuller
  • Baruch Schieber

An efficient parallel algorithm for testing whether a graph G is K-vertex connected, for any fixed k, is presented. The algorithm runs in O(log n) time and uses nC(n, m) processors on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM), where n and m are the number of vertices and edges of G and C(n, m) is the number of processors required to compute the connected components of G in logarithmic time. An optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing k-vertex connectivity, for any k>4. To develop the algorithm, an efficient parallel algorithm is designed for the following disjoint s-t paths problem: Given a graph G and two specified vertices s and t, find k-vertex disjoint paths between s and t, if they exist. If no such paths exist, find a set of at most k-1 vertices whose removal disconnects s and t. The parallel algorithm for this problem runs in O(log n) time using C(n, m) processors. It is shown how to modify the algorithm to find k-edge disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph G is k-edge connected, for any fixed k. The algorithm runs in O(log n) time and uses nC (n, n) processors on a CRCW PRAM. Again, an optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing k-edge connectivity. >

Details

FOCS Conference 1989 Conference Paper

Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph

  • Samir Khuller
  • Stephen G. Mitchell
  • Vijay V. Vazirani

Given a graph G and two pairs of vertices s/sub 1/, t/sub 1/ and s/sub 2/, t/sub 2/, the two disjoint paths problem asks for vertex-disjoint paths connecting s/sub i/ with t/sub i/, i=1, 2. A fast parallel (NC) algorithm is given for this problem, which has applications in certain routing situations. If G is nonplanar, an algorithm that finds a Kuratowski homeomorph in G (i. e. a subgraph homeomorphic to K/sub 3. 3/ or K/sub 5/) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm provides a certificate of nonplanarity in the negative case. Both algorithms are processor efficient; in each case, the processor-time product is within a polylogarithmic factor of the best known sequential algorithm. >

Details
v2026.09.13