Traditional clustering methods assume that precise pairwise distances for the input data are readily available. However, this assumption is often impractical in real-world scenarios where data points cannot be measured accurately. For instance, machine learning-based techniques for estimating distances may fail when the dataset consists of images, videos, or natural language. This paper studies clustering and graph problems in settings where direct access to pairwise distances between all pairs is expensive. We adopt oracle-based methods as defined by Galhotra et al. (2024), focusing on two types of oracles: the quadruplet oracle, a weak and inexpensive comparator that answers binary queries of the form "Is A closer to B or C closer to D?" and the distance oracle, a stronger but costlier oracle that returns exact pairwise distances. The quadruplet oracle can be implemented via crowdsourcing, trained classifiers, or other predictive models. As these sources are often unreliable, the oracle’s responses may be noisy; we consider both probabilistic and adversarial noise models. Consider a finite metric space $\Sigma=(\mathcal{V},d)$ of size $|\mathcal{V}|=n$ that supports the quadruplet and the distance oracle. When the input dataset has low intrinsic (doubling) dimension, for each of the $k$-center, $k$-median, and $k$-means clustering problem on $\mathcal{V}$, we design constant approximation algorithms that perform $\widetilde{O}(n+k^2)$ calls to the quadruplet oracle and $\widetilde{O}(1)$ calls to the distance oracle in both noise models. For general metric spaces, our algorithms achieve constant approximation while making $\widetilde{O}(nk)$ calls to the quadruplet oracle and $\widetilde{O}(1)$ calls to the distance oracle. In all cases, we improve the quadruplet oracle query complexity by a factor of $k$ and the distance oracle call complexity by a factor of $k^2$ compared to Galhotra et al. (2024). Furthermore, in low dimensional settings, if the spread of the input data is polynomially bounded, we construct a data structure performing $\widetilde{O}(n)$ queries to the quadruplet oracle and $\widetilde{O}(1)$ queries to the distance oracle, such that given any query pair of vertices $(u,v)\in \mathcal{V}\times \mathcal{V}$, it approximates the distance $d(u,v)$ without using any oracle queries. Once the data structure is constructed, we can emulate standard algorithms for various graph problems on $\Sigma$ without additional oracle queries. In summary, our results show that access to a noisy pairwise ranker for distances is to sufficient to efficiently solve a large class of problems while almost entirely bypassing exact distance computations.

Flow sparsification is a classic graph compression technique which, given a capacitated graph G on k terminals, aims to construct another capacitated graph H, called a flow sparsifier, that preserves, either exactly or approximately, every multicommodity flow between terminals (ideally, with size as a small function of k). Cut sparsifiers are a restricted variant of flow sparsifiers which are only required to preserve maximum flows between bipartitions of the terminal set. It is known that exact cut sparsifiers require 2^Ω(k) many vertices [Krauthgamer and Rika, SODA 2013], with the hard instances being quasi-bipartite graphs, where there are no edges between non-terminals. On the other hand, it has been shown recently that exact (or even (1+ε)-approximate) flow sparsifiers on networks with just 6 terminals require unbounded size [Krauthgamer and Mosenzon, SODA 2023, Chen and Tan, SODA 2024]. In this paper, we construct exact flow sparsifiers of size 3^k³ and exact cut sparsifiers of size 2^k² for quasi-bipartite graphs. In particular, the flow sparsifiers are contraction-based, that is, they are obtained from the input graph by (vertex) contraction operations. Our main contribution is a new technique to construct sparsifiers that exploits connections to polyhedral geometry, and that can be generalized to graphs with a small separator that separates the graph into small components. We also give an improved reduction theorem for graphs of bounded treewidth [Andoni et al., SODA 2011], implying a flow sparsifier of size O(k⋅w) and quality O((log w)/log log w), where w is the treewidth.

Smart factories have data packets with a mix of stringent and non-stringent deadlines with varying levels of importance that need to be delivered via a wireless network. However, the scheduling of packets in the wireless network is crucial to satisfy the deadlines. In this work, we propose a technique of utilizing IEEE 802.11ax, popularly known as WiFi 6, for such applications. IEEE 802.11ax has a few unique characteristics, such as specific configurations of dividing the channels into resource units (RU) for packet transmission and synchronized parallel transmissions. We model the problem of scheduling packets by assigning profit to each packet and then maximizing the sum of profits. We first show that this problem is strongly NP-Hard, and then propose an approximation algorithm with a 12-approximate algorithm. Our approximation algorithm uses a variant of local search to associate the right RU configuration to each packet and identify the duration of each parallel transmission. Finally, we extensively simulate different scenarios to show that our algorithm works better than other benchmarks.

Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point in its trip. We give an algorithm HGR, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to each individual rider's traveling time. This suggests that HGR enhances rider experience while being energy-efficient.

IEEE 802.11ax introduces OFDMA where multiple users transmit concurrently. This is particularly useful in dense scenarios where the density of WiFi connected devices is very high in settings such as stadiums, airports, classrooms, etc. The effectiveness of such a system relies heavily upon an efficient Scheduling and Resource Allocation (SRA) algorithm. One approach towards designing such an algorithm is to model this problem as a constrained optimization problem that maximizes a linear utility function. Such a framework attempts to adapt several standard SRA rules, like maximizing the Sum Rate, Proportional Fair, to the OFDMA settings. State-of-the-art (SOTA) SRA heuristics lack theoretical guarantees. In this paper, we show a reduction of the SRA problem in OFDMA to a budgeted variant of the maximum weight matching problem on bipartite graphs. We observe that this problem is NP-hard. Hence, we design an efficient approximation algorithm, FAIRSPLIT, with provable guarantees. We demonstrate the effectiveness of our algorithm through a variety of simulations. We see that FAIRSPLIT outperforms SOTA by 11-48% in terms of aggregate throughput while utilizing the bandwidth more efficiently.

Ranking algorithms find extensive usage in diverse areas such as web search, employment, college admission, voting, etc. The related rank aggregation problem deals with combining multiple rankings into a single aggregate ranking. However, algorithms for both these problems might be biased against some individuals or groups due to implicit prejudice or marginalization in the historical data. We study ranking and rank aggregation problems from a fairness or diversity perspective, where the candidates (to be ranked) may belong to different groups and each group should have a fair representation in the final ranking. We allow the designer to set the parameters that define fair representation. These parameters specify the allowed range of the number of candidates from a particular group in the top-$k$ positions of the ranking. Given any ranking, we provide a fast and exact algorithm for finding the closest fair ranking for the Kendall tau metric under {\em strong fairness}, i.e., when the final ranking is fair for all values of $k$. We also provide an exact algorithm for finding the closest fair ranking for the Ulam metric under strong fairness when there are only $O(1)$ number of groups. Our algorithms are simple, fast, and might be extendable to other relevant metrics. We also give a novel meta-algorithm for the general rank aggregation problem under the fairness framework. Surprisingly, this meta-algorithm works for any generalized mean objective (including center and median problems) and any fairness criteria. As a byproduct, we obtain 3-approximation algorithms for both center and median problems, under both Kendall tau and Ulam metrics. Furthermore, using sophisticated techniques we obtain a $(3-\varepsilon)$-approximation algorithm, for a constant $\varepsilon>0$, for the Ulam metric under strong fairness.

Ride-sharing is one of the most popular models of economical and eco-friendly transportation in modern smart cities, especially when riding hybrid and electric vehicles. Usually multiple passengers with similar itineraries are grouped together, which significantly reduces travel cost (or time), road congestion, and traffic emissions. In this paper, we study the ride-sharing problem where each vehicle is shared by exactly $łambda$ riders for any fixed $łambda>0$, and the goal is to minimize the total travel distance. The min-cost ride-sharing problem is intractable even in the case of exactly two riders sharing a vehicle \citeBeiZ18-carsharing, and hence we can only hope for an approximate solution. We propose a novel two-phase algorithm: a hierarchical grouping phase that partitions requests into disjoint groups of fixed size, followed by an assignment of request groups to individual vehicles and planning a feasible route for each vehicle. This is the first non-trivial approximation algorithm for the ride-sharing problem with vehicle capacity larger than two. We verify the efficacy of our algorithm on both synthetic and realworld datasets. Our experimental results show that, the ride-sharing scheme produced by our algorithm not only has small total travel distance compared to state-of-the-art baselines, but also enjoys a small makespan and total latency, which crucially relate to each single rider's traveling time. This suggests that our algorithm also enhances rider experience while being energy-efficient.

Center-based clustering techniques are fundamental to many real-world applications such as data summarization and social network analysis. In this work, we study the problem of fairness aware k-center clustering over large datasets. We are given an input dataset comprising a set of n points, where each point belongs to a specific demographic group characterized by a protected attribute, such as race or gender. The goal is to identify k clusters such that all clusters have considerable representation from all groups and the maximum radius of these clusters is minimized.

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(c log n)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) with non-negative real edge lengths and an integer parameter k, the (uncapacitated) Min-Max Tree Cover problem seeks to find a set of at most k trees which together span V and each tree is a subgraph of G. The objective is to minimize the maximum length among all the trees. In this paper, we consider a capacitated generalization of the above and give the first constant factor approximation algorithm. In the capacitated version, there is a hard uniform capacity (λ) on the number of vertices a tree can cover. Our result extends to the rooted version of the problem, where we are given a set of k root vertices, R and each of the covering trees is required to include a distinct vertex in R as the root. Prior to our work, the only result known was a (2k-1)-approximation algorithm for the special case when the total number of vertices in the graph is kλ [Guttmann-Beck and Hassin, J. of Algorithms, 1997]. Our technique circumvents the difficulty of using the minimum spanning tree of the graph as a lower bound, which is standard for the uncapacitated version of the problem [Even et al.,OR Letters 2004] [Khani et al.,Algorithmica 2010]. Instead, we use Steiner trees that cover λ vertices along with an iterative refinement procedure that ensures that the output trees have low cost and the vertices are well distributed among the trees.

IEEE 802.11ax introduces OFDMA (Orthogonal Frequency Division Multiple Access) that allows multiple users to transmit or receive frames concurrently. The OFDMA transmission duration is decided by the client with maximum transmission duration. We focus on minimizing the maximum transmission duration. The standard restricts assignment of at max one RU to a client and provides a specific way of splitting the channel into smaller RUs. In this paper, we come up with a generic framework, MMRU-Alloc (Min Max Resource Unit Allocation) to allocate RUs to clients under the given constraints for a single OFDMA transmission. The framework allows one to define any non-negative cost function such as data transmission time or the padding length required for synchronized end time of all clients for a client-RU pair and we believe this can capture a wide variety of scenarios. We design provably efficient and optimal algorithms for this general problem. We demonstrate the applicability of our framework for two specific problems pertaining to transmission of one OFDMA frame. (1) Minimizing the transmission duration of one OFDMA frame for a given set of clients. (2) Minimizing the maximum padding length required by any client to ensure synchronized end time. We implemented (1) in NS-3 and evaluated its performance. We compare it with two popular scheduling and resource allocation algorithms: Max Rate (MR) and Proportional Fairness (PF). We find that it outperforms both MR and PF by upto 91.3% in terms of frame transmission time and upto 91.1% terms of throughput achieved.

In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph $G=(V,E)$ on $n$ vertices, a root vertex $r$ and a collection of groups $\{S_i\}_{i\in[h]}: S_i\subseteq V(G)$. The goal is to find a min-cost subgraph $H$ that connects the root to every group. We consider a fault-tolerant variant of GST, which we call Restricted (Rooted) Group SNDP. In this setting, each group $S_i$ has a demand $k_i\in[k],k\in\mathbb N$, and we wish to find a min-cost $H\subseteq G$ such that, for each group $S_i$, there is a vertex in $S_i$ connected to the root via $k_i$ (vertex or edge) disjoint paths. While GST admits $O(\log^2 n\log h)$ approximation, its high connectivity variants are Label-Cover hard, and for the vertex-weighted version, the hardness holds even when $k=2$. Previously, positive results were known only for the edge-weighted version when $k=2$ [Gupta et al., SODA 2010; Khandekar et al., Theor. Comput. Sci., 2012] and for a relaxed variant where the disjoint paths may end at different vertices in a group [Chalermsook et al., SODA 2015]. Our main result is an $O(\log n\log h)$ approximation for Restricted Group SNDP that runs in time $n^{f(k, w)}$, where $w$ is the treewidth of $G$. This nearly matches the lower bound when $k$ and $w$ are constant. The key to achieving this result is a non-trivial extension of the framework in [Chalermsook et al., SODA 2017], which embeds all feasible solutions to the problem into a dynamic program (DP) table. However, finding the optimal solution in the DP table remains intractable. We formulate a linear program relaxation for the DP and obtain an approximate solution via randomized rounding. This framework also allows us to systematically construct DP tables for high-connectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in low-treewidth graphs.

We study the classical scheduling problem of assigning jobs to machines in order to minimize the makespan. It is well-studied and admits an EPTAS on identical machines and a (2-1/m)-approximation algorithm on unrelated machines. In this paper we study a variation in which the input jobs are partitioned into bags and no two jobs from the same bag are allowed to be assigned on the same machine. Such a constraint can easily arise, e.g., due to system stability and redundancy considerations. Unfortunately, as we demonstrate in this paper, the techniques of the above results break down in the presence of these additional constraints. Our first result is a PTAS for the case of identical machines. It enhances the methods from the known (E)PTASs by a finer classification of the input jobs and careful argumentations why a good schedule exists after enumerating over the large jobs. For unrelated machines, we prove that there can be no (log n)^{1/4-epsilon}-approximation algorithm for the problem for any epsilon > 0, assuming that NP nsubseteq ZPTIME(2^{(log n)^{O(1)}}). This holds even in the restricted assignment setting. However, we identify a special case of the latter in which we can do better: if the same set of machines we give an 8-approximation algorithm. It is based on rounding the LP-relaxation of the problem in phases and adjusting the residual fractional solution after each phase to order to respect the bag constraints.

The Group Steiner Tree (GST) problem is a classical problem in combinatorial optimization and theoretical computer science. In the Edge-Weighted Group Steiner Tree (EW-GST) problem, we are given an undirected graph G = (V, E) on n vertices with edge costs c : E → ℝ≥0, a source vertex s and a collection of subsets of vertices, called groups, S1,…, Sk ⊆ V. The goal is to find a minimum-cost tree H ⊆ G that connects s to some vertex from each group Si, for all i = 1, 2,…, k. The Node-Weighted Group Steiner Tree (NW-GST) problem has the same setting, but the costs are associated with nodes. The goal is to find a minimum- cost node set X ⊆ V such that G[X] connects every group to the source. When G is a tree, both EW-GST and NW-GST admit a polynomial-time O (log n log k) approximation algorithm due to the seminal result of [Garg et al., SODA'98 and J. Algorithm]. The matching hardness of log2 −∊ n is known even for tree instances of EW-GST and NW-GST [Halperin and Krauthgamer STOC'03]. In general graphs, most of polynomial-time approximation algorithms for EW- GST reduce the problem to a tree instance using the metric- tree embedding, incurring a loss of O(log n) on the approximation factor [Bartal, FOCS'96; Fakcharoenphol et al., FOCS'03 and JCSS]. This yields an approximation ratio of O(log n log k) for EW-GST. Using metric-tree embedding, this factor cannot be improved: The loss of O(log n) is necessary on some input graphs (e.g., grids and expanders). There are alternative approaches that avoid metric-tree embedding, e.g., the algorithm of [Chekuri and Pal, FOCS'05], which gives a tight approximation ratio, but none of which achieves polylogarithmic approximation in polynomial-time. This state of the art shows a clear lack of understanding of GST in general graphs beyond the metric-tree embedding technique. For NW-GST (for which the metric-tree embedding does not apply), not even a polynomial-time polyloga- rithmic approximation algorithm is known. In this paper, we present O(log n log k) approximation algorithms that run in time nÕ(tw(G)2 ‘for both NW-GST and EW-GST1, where tw(G) denotes the treewidth of graph G. The key to both results is a different type of “tree- embedding” that produces a tree of much bigger size, but does not cause any loss on the approximation factor. Our embedding is inspired by dynamic programming, a technique which is typically not applicable to Group Steiner problems.

We consider the online scheduling problem to minimize the weighted ell_p-norm of flow-time of jobs. We study this problem under the rejection model introduced by Choudhury et al. (SODA 2015) - here the online algorithm is allowed to not serve an eps-fraction of the requests. We consider the restricted assignments setting where each job can go to a specified subset of machines. Our main result is an immediate dispatch non-migratory 1/eps^{O(1)}-competitive algorithm for this problem when one is allowed to reject at most eps-fraction of the total weight of jobs arriving. This is in contrast with the speed augmentation model under which no online algorithm for this problem can achieve a competitive ratio independent of p.

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(log2 l/ε)-competitive algorithm which rejects at most an ε-fraction of the jobs. For the problem of minimizing the maximum weighted flow-time, we give an O(1/ε4)-competitive algorithm which can reject at most an ε-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/ε6)-competitive algorithm in this case. Our algorithms are immediate dispatch, though they may not be immediate reject. All these problems have strong lower bounds in speed augmentation model.