Search Results

Documents authored by Khuller, Samir

Document
DOI: 10.4230/LIPIcs.ESA.2024.37
Online Flexible Busy Time Scheduling on Heterogeneous Machines

Authors: Gruia Călinescu, Sami Davies, Samir Khuller, and Shirley Zhang

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job’s arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied, relatively little is known when machines are heterogeneous (i.e., have different costs and capacities), despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and provide a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio 8(2p-1)/p < 16 when all jobs have uniform length p.
Cite as

Gruia Călinescu, Sami Davies, Samir Khuller, and Shirley Zhang. Online Flexible Busy Time Scheduling on Heterogeneous Machines. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{calinescu_et_al:LIPIcs.ESA.2024.37,
  author =	{C\u{a}linescu, Gruia and Davies, Sami and Khuller, Samir and Zhang, Shirley},
  title =	{{Online Flexible Busy Time Scheduling on Heterogeneous Machines}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.37},
  URN =		{urn:nbn:de:0030-drops-211083},
  doi =		{10.4230/LIPIcs.ESA.2024.37},
  annote =	{Keywords: Online algorithms, Scheduling, Competitive analysis}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.28
Scalable Auction Algorithms for Bipartite Maximum Matching Problems

Authors: Quanquan C. Liu, Yiduo Ke, and Samir Khuller

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
Bipartite maximum matching and its variants are well-studied problems under various models of computation with the vast majority of approaches centering around various methods to find and eliminate augmenting paths. Beginning with the seminal papers of Demange, Gale and Sotomayor [DGS86] and Bertsekas [Ber81], bipartite maximum matching problems have also been studied in the context of auction algorithms. These algorithms model the maximum matching problem as an auction where one side of the bipartite graph consists of bidders and the other side consists of items; as such, these algorithms offer a very different approach to solving this problem that do not use classical methods. Dobzinski, Nisan and Oren [DNO14] demonstrated the utility of such algorithms in distributed, interactive settings by providing a simple and elegant O(log n/ε²) round maximum cardinality bipartite matching (MCM) algorithm that has small round and communication complexity and gives a (1-ε)-approximation for any (not necessarily constant) ε > 0. They leave as an open problem whether an auction algorithm, with similar guarantees, can be found for the maximum weighted bipartite matching (MWM) problem. Very recently, Assadi, Liu, and Tarjan [ALT21] extended the utility of auction algorithms for MCM into the semi-streaming and massively parallel computation (MPC) models, by cleverly using maximal matching as a subroutine, to give a new auction algorithm that uses O(1/ε²) rounds and achieves the state-of-the-art bipartite MCM results in the streaming and MPC settings. In this paper, we give new auction algorithms for maximum weighted bipartite matching (MWM) and maximum cardinality bipartite b-matching (MCbM). Our algorithms run in O(log n/ε⁸) and O(log n/ε²) rounds, respectively, in the distributed setting. We show that our MWM algorithm can be implemented in the distributed, interactive setting using O(log² n) and O(log n) bit messages, respectively, directly answering the open question posed by Demange, Gale and Sotomayor [DNO14]. Furthermore, we implement our algorithms in a variety of other models including the the semi-streaming model, the shared-memory work-depth model, and the massively parallel computation model. Our semi-streaming MWM algorithm uses O(1/ε⁸) passes in O(n log n ⋅ log(1/ε)) space and our MCbM algorithm runs in O(1/ε²) passes using O((∑_{i ∈ L} b_i + |R|) log(1/ε)) space (where parameters b_i represent the degree constraints on the b-matching and L and R represent the left and right side of the bipartite graph, respectively). Both of these algorithms improves exponentially the dependence on ε in the space complexity in the semi-streaming model against the best-known algorithms for these problems, in addition to improvements in round complexity for MCbM. Finally, our algorithms eliminate the large polylogarithmic dependence on n in depth and number of rounds in the work-depth and massively parallel computation models, respectively, improving on previous results which have large polylogarithmic dependence on n (and exponential dependence on ε in the MPC model).
Cite as

Quanquan C. Liu, Yiduo Ke, and Samir Khuller. Scalable Auction Algorithms for Bipartite Maximum Matching Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.APPROX/RANDOM.2023.28,
  author =	{Liu, Quanquan C. and Ke, Yiduo and Khuller, Samir},
  title =	{{Scalable Auction Algorithms for Bipartite Maximum Matching Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{28:1--28:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.28},
  URN =		{urn:nbn:de:0030-drops-188537},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.28},
  annote =	{Keywords: auction algorithms, maximum weight bipartite matching, maximum b-matching, distributed blackboard model, parallel work-depth model, streaming model, massively parallel computation model}
}
Document
DOI: 10.4230/LIPIcs.FORC.2023.8
An Algorithmic Approach to Address Course Enrollment Challenges

Authors: Arpita Biswas, Yiduo Ke, Samir Khuller, and Quanquan C. Liu

Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)

Abstract
Massive surges of enrollments in courses have led to a crisis in several computer science departments - not only is the demand for certain courses extremely high from majors, but the demand from non-majors is also very high. Much of the time, this leads to significant frustration on the part of the students, and getting seats in desired courses is a rather ad-hoc process. One approach is to first collect information from students about which courses they want to take and to develop optimization models for assigning students to available seats in a fair manner. What makes this problem complex is that the courses themselves have time conflicts, and the students have credit caps (an upper bound on the number of courses they would like to enroll in). We model this problem as follows. We have n agents (students), and there are "resources" (these correspond to courses). Each agent is only interested in a subset of the resources (courses of interest), and each resource can only be assigned to a bounded number of agents (available seats). In addition, each resource corresponds to an interval of time, and the objective is to assign non-overlapping resources to agents so as to produce "fair and high utility" schedules. In this model, we provide a number of results under various settings and objective functions. Specifically, in this paper, we consider the following objective functions: total utility, max-min (Santa Claus objective), and envy-freeness. The total utility objective function maximizes the sum of the utilities of all courses assigned to students. The max-min objective maximizes the minimum utility obtained by any student. Finally, envy-freeness ensures that no student envies another student’s allocation. Under these settings and objective functions, we show a number of theoretical results. Specifically, we show that the course allocation under the time conflicts problem is NP-complete but becomes polynomial-time solvable when given only a constant number of students or all credits, course lengths, and utilities are uniform. Furthermore, we give a near-linear time algorithm for obtaining a constant 1/2-factor approximation for the general maximizing total utility problem when utility functions are binary. In addition, we show that there exists a near-linear time algorithm that obtains a 1/2-factor approximation on total utility and a 1/4-factor approximation on max-min utility when given uniform credit caps and uniform utilities. For the setting of binary valuations, we show three polynomial time algorithms for 1/2-factor approximation of total utility, envy-freeness up to one item, and a constant factor approximation of the max-min utility value when course lengths are within a constant factor of each other. Finally, we conclude with experimental results that demonstrate that our algorithms yield high-quality results in real-world settings.
Cite as

Arpita Biswas, Yiduo Ke, Samir Khuller, and Quanquan C. Liu. An Algorithmic Approach to Address Course Enrollment Challenges. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.FORC.2023.8,
  author =	{Biswas, Arpita and Ke, Yiduo and Khuller, Samir and Liu, Quanquan C.},
  title =	{{An Algorithmic Approach to Address Course Enrollment Challenges}},
  booktitle =	{4th Symposium on Foundations of Responsible Computing (FORC 2023)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-272-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{256},
  editor =	{Talwar, Kunal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.8},
  URN =		{urn:nbn:de:0030-drops-179297},
  doi =		{10.4230/LIPIcs.FORC.2023.8},
  annote =	{Keywords: fairness, allocation, matching, algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.91
Correlated Stochastic Knapsack with a Submodular Objective

Authors: Sheng Yang, Samir Khuller, Sunav Choudhary, Subrata Mitra, and Kanak Mahadik

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time (1 - 1/√e)/2 ≃ 0.1967 approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the (1 - 1/∜e)/2 ≃ 0.1106 approximation by Fukunaga et al. [AAAI 2019].
Cite as

Sheng Yang, Samir Khuller, Sunav Choudhary, Subrata Mitra, and Kanak Mahadik. Correlated Stochastic Knapsack with a Submodular Objective. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 91:1-91:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.ESA.2022.91,
  author =	{Yang, Sheng and Khuller, Samir and Choudhary, Sunav and Mitra, Subrata and Mahadik, Kanak},
  title =	{{Correlated Stochastic Knapsack with a Submodular Objective}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{91:1--91:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.91},
  URN =		{urn:nbn:de:0030-drops-170296},
  doi =		{10.4230/LIPIcs.ESA.2022.91},
  annote =	{Keywords: Stochastic Knapsack, Submodular Optimization, Stochastic Optimization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.18
On the Cost of Essentially Fair Clusterings

Authors: Ioana O. Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Clustering is a fundamental tool in data mining and machine learning. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters - especially if the data is already biased. At NIPS 2017, Chierichetti et al. [Flavio Chierichetti et al., 2017] proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a 4-approximation for the fair k-center problem and a O(t)-approximation for the fair k-median problem, where t is a parameter for the fairness model. For multiple protected classes, the best known result is a 14-approximation for fair k-center [Clemens Rösner and Melanie Schmidt, 2018]. We extend and improve the known results. Firstly, we give a 5-approximation for the fair k-center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximations for all of the classical clustering objectives k-center, k-supplier, k-median, k-means and facility location. The latter approximations are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where the centers are already fixed.
Cite as

Ioana O. Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the Cost of Essentially Fair Clusterings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bercea_et_al:LIPIcs.APPROX-RANDOM.2019.18,
  author =	{Bercea, Ioana O. and Gro{\ss}, Martin and Khuller, Samir and Kumar, Aounon and R\"{o}sner, Clemens and Schmidt, Daniel R. and Schmidt, Melanie},
  title =	{{On the Cost of Essentially Fair Clusterings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.18},
  URN =		{urn:nbn:de:0030-drops-112337},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.18},
  annote =	{Keywords: approximation, clustering, fairness, LP rounding}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.23
Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem

Authors: Sapna Grover, Neelima Gupta, Samir Khuller, and Aditya Pancholi

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
In this paper, we give the first constant factor approximation algorithm for capacitated knapsack median problem (CKnM) for hard uniform capacities, violating the budget by a factor of 1+epsilon and capacities by a 2+epsilon factor. To the best of our knowledge, no constant factor approximation is known for the problem even with capacity/budget/both violations. Even for the uncapacitated variant of the problem, the natural LP is known to have an unbounded integrality gap even after adding the covering inequalities to strengthen the LP. Our techniques for CKnM provide two types of results for the capacitated k-facility location problem. We present an O(1/epsilon^2) factor approximation for the problem, violating capacities by (2+epsilon). Another result is an O(1/epsilon) factor approximation, violating the capacities by a factor of at most (1 + epsilon) using at most 2k facilities for a fixed epsilon>0. As a by-product, a constant factor approximation algorithm for capacitated facility location problem with uniform capacities is presented, violating the capacities by (1 + epsilon) factor. Though constant factor results are known for the problem without violating the capacities, the result is interesting as it is obtained by rounding the solution to the natural LP, which is known to have an unbounded integrality gap without violating the capacities. Thus, we achieve the best possible from the natural LP for the problem. The result shows that the natural LP is not too bad.
Cite as

Sapna Grover, Neelima Gupta, Samir Khuller, and Aditya Pancholi. Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grover_et_al:LIPIcs.FSTTCS.2018.23,
  author =	{Grover, Sapna and Gupta, Neelima and Khuller, Samir and Pancholi, Aditya},
  title =	{{Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.23},
  URN =		{urn:nbn:de:0030-drops-99224},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.23},
  annote =	{Keywords: Capacitated Knapsack Median, Capacitated k -Facility Location}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.11
Revisiting Connected Dominating Sets: An Optimal Local Algorithm?

Authors: Samir Khuller and Sheng Yang

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
In this paper we consider the classical Connected Dominating Set (CDS) problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem - a centralized greedy approach with an approximation guarantee of H(D) +2, and a local greedy approach with an approximation guarantee of 2(H(D)+1) (where H() is the harmonic function, and D is the maximum degree in the graph). A local greedy algorithm uses significantly less information about the graph, and can be useful in a variety of contexts. However, a fundamental question remained - can we get a local greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative.
Cite as

Samir Khuller and Sheng Yang. Revisiting Connected Dominating Sets: An Optimal Local Algorithm?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{khuller_et_al:LIPIcs.APPROX-RANDOM.2016.11,
  author =	{Khuller, Samir and Yang, Sheng},
  title =	{{Revisiting Connected Dominating Sets: An Optimal Local Algorithm?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.11},
  URN =		{urn:nbn:de:0030-drops-66340},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.11},
  annote =	{Keywords: graph algorithms, approximation algorithms, dominating sets, local information algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.68
Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms

Authors: Riley Murray, Megan Chao, and Samir Khuller

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.
Cite as

Riley Murray, Megan Chao, and Samir Khuller. Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{murray_et_al:LIPIcs.ESA.2016.68,
  author =	{Murray, Riley and Chao, Megan and Khuller, Samir},
  title =	{{Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{68:1--68:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.68},
  URN =		{urn:nbn:de:0030-drops-64104},
  doi =		{10.4230/LIPIcs.ESA.2016.68},
  annote =	{Keywords: approximation algorithms, distributed computing, machine scheduling, LP relaxations, primal-dual algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.38
On Correcting Inputs: Inverse Optimization for Online Structured Prediction

Authors: Hal Daumé III, Samir Khuller, Manish Purohit, and Gregory Sanders

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
Algorithm designers typically assume that the input data is correct, and then proceed to find "optimal" or "sub-optimal" solutions using this input data. However this assumption of correct data does not always hold in practice, especially in the context of online learning systems where the objective is to learn appropriate feature weights given some training samples. Such scenarios necessitate the study of inverse optimization problems where one is given an input instance as well as a desired output and the task is to adjust the input data so that the given output is indeed optimal. Motivated by learning structured prediction models, in this paper we consider inverse optimization with a margin, i.e., we require the given output to be better than all other feasible outputs by a desired margin. We consider such inverse optimization problems for maximum weight matroid basis, matroid intersection, perfect matchings, minimum cost maximum flows, and shortest paths and derive the first known results for such problems with a non-zero margin. The effectiveness of these algorithmic approaches to online learning for structured prediction is also discussed.
Cite as

Hal Daumé III, Samir Khuller, Manish Purohit, and Gregory Sanders. On Correcting Inputs: Inverse Optimization for Online Structured Prediction. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 38-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{daumeiii_et_al:LIPIcs.FSTTCS.2015.38,
  author =	{Daum\'{e} III, Hal and Khuller, Samir and Purohit, Manish and Sanders, Gregory},
  title =	{{On Correcting Inputs: Inverse Optimization for Online Structured Prediction}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{38--51},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.38},
  URN =		{urn:nbn:de:0030-drops-56375},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.38},
  annote =	{Keywords: Inverse Optimization, Structured Prediction, Online Learning}
}
Document
DOI: 10.4230/DagSemProc.10071.5
Energy Efficient Scheduling via Partial Shutdown

Authors: Samir Khuller, Jian Li, and Barna Saha

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
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 machine $i$ having an activation cost of $a_i$. There is also a collection of N jobs that need to be performed, and $p_{ij}$ 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. 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)le A$ and find a schedule for the jobs on the machines in $S$ minimizing the makespan. In this work we develop bi-criteria approximation algorithms for this problem based on both LP rounding and a greedy approach.
Cite as

Samir Khuller, Jian Li, and Barna Saha. Energy Efficient Scheduling via Partial Shutdown. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{khuller_et_al:DagSemProc.10071.5,
  author =	{Khuller, Samir and Li, Jian and Saha, Barna},
  title =	{{Energy Efficient Scheduling via Partial Shutdown}},
  booktitle =	{Scheduling},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.5},
  URN =		{urn:nbn:de:0030-drops-25435},
  doi =		{10.4230/DagSemProc.10071.5},
  annote =	{Keywords: Unrelated parallel machine scheduling, approximation algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact