We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractional optimal vertices, but there is always also an optimal integral vertex, which we can also compute in polynomial time. More specifically, we consider the multiplicative assignment problem with upgrades in which we are given a set of customers and suppliers and we seek to assign each customer to a different supplier. Each customer has a demand and each supplier has a regular and an upgraded cost for each unit demand provided to the respective assigned client. Our goal is to upgrade at most k suppliers and to compute an assignment in order to minimize the total resulting cost. This can be cast as the problem to compute an optimal matching in a bipartite graph with the additional constraint that we must select k edges from a certain group of edges, similar to selecting k red edges in the exact matching problem. Also, selecting the suppliers to be upgraded corresponds to maximizing a submodular set function under a cardinality constraint. Our result yields an efficient LP-based algorithm to solve our problem optimally. In addition, we also provide a purely strongly polynomial-time algorithm for it. As an application, we obtain exact algorithms for the upgrading variant of the problem to schedule jobs on identical or uniformly related machines in order to minimize their sum of completion times, i.e., where we may upgrade up to k jobs to reduce their respective processing times.

We study the problem of allocating items to agents with submodular valuations with the goal of maximizing the weighted Nash social welfare (NSW). The best-known results for unweighted and weighted objectives are the (4+є) approximation given by Garg, Husic, Li, Végh, and Vondrák [STOC 2023] and the (233+є) approximation given by Feng, Hu, Li, and Zhang [STOC 2025], respectively.

This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit size that must be scheduled on a single initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, Vöcking B, eds. 25th ACM Sympos. Parallelism Algorithms Architectures SPAA ‘13 (ACM, New York), 280–287] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations. For the minimization version, we present a logarithmic approximation algorithm. We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P = NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no [Formula: see text]-approximation algorithm based on the unique game conjecture. For the maximization version, we give an algorithm with approximation ratio [Formula: see text]. This improves upon the previously best-known algorithm, which has an approximation ratio of 1/3 [Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds. Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc., Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311–324]. Moreover, we also prove that our bound on the approximation ratio is tight. Although all hardness results mentioned above hold for any [Formula: see text], we provide optimal polynomial-time algorithms for T = 2 in both the minimization version and the maximization version. Finally, we show that our methods can be extended into the m identical machines case by losing some running time, whereas all algorithmic results remain the same in both versions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0430 .

We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i.e., the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G:=(L cup R, E), our problem is equivalent to selecting k vertices from R such that the maximum (weighted) number selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research. We first prove that the problem is NP-hard even if the maximum degree Delta of the input bipartite graph is 3, and the problem is in P when Delta=2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O(log n/(log log n))-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log(Delta))-approximation on bipartite graphs with a maximum degree Delta. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming.

We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a cost and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total cost does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint). While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem -- without relaxing either the knapsack or fairness constraints -- remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of (1-1/e-epsilon) can be obtained in expectation for any epsilon >0.

$k$-means++ and the related greedy $k$-means++ algorithm are celebrated algorithms that efficiently compute seeds for Lloyd's algorithm. Greedy $k$-means++ is a generalization of $k$-means++ where, in each iteration, a new seed is greedily chosen among multiple $\ell \geq 2$ points sampled, as opposed to a single seed being sampled in $k$-means++. While empirical studies consistently show the superior performance of greedy $k$-means++, making it a preferred method in practice, a discrepancy exists between theory and practice. No theoretical justification currently explains this improved performance. Indeed, the prevailing theory suggests that greedy $k$-means++ exhibits worse performance than $k$-means++ in worst-case scenarios. This paper presents an analysis demonstrating the outperformance of the greedy algorithm compared to $k$-means++ for a natural class of well-separated instances with exponentially decaying distributions, such as Gaussian, specifically when $\ell = \Theta(\log k)$, a common parameter setting in practical applications.

The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.

The paper revisits the Robust s-t Path problem, one of the most fundamental problems in robust optimization. In the problem, we are given a directed graph with n vertices and k distinct cost functions (scenarios) defined over edges, and aim to choose an s-t path such that the total cost of the path is always provable no matter which scenario is realized. Viewing each cost function as an agent, our goal is to find a fair s-t path, which minimizes the maximum cost among all agents. The problem is NP-hard to approximate within a factor of o(log k) unless NP ⊆ DTIME(npoly logn), and the best-known approximation ratio is Õ (√n), which is based on the natural flow linear program. A longstanding open question is whether we can achieve a polylogarithmic approximation for the problem; it remains open even if a quasi-polynomial running time is allowed. Our main result is a O (log n log k) approximation for the Robust s-t Path problem in quasipolynomial time, solving the open question in the quasi-polynomial time regime. The algorithm is built on a novel linear program formulation for a decision-tree-type structure, which enables us to overcome the Ω (√n) integrality gap for the natural flow LP. Furthermore, we show that for graphs with bounded treewidth, the quasi-polynomial running time can be improved to a polynomial. We hope our techniques can offer new insights into this problem and other related problems in robust optimization. © Shi Li, Chenyang Xu, and Ruilong Zhang.

In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents---thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our problem to submodular objective functions and Matroid rank constraints.

Scheduling with testing falls under the umbrella of the research on optimization with explorable uncertainty. In this model, each job has an upper limit on its processing time that can be decreased to a lower limit (possibly unknown) by some preliminary action (testing). Recently, D{ü}rr et al. \cite{DBLP:journals/algorithmica/DurrEMM20} has studied a setting where testing a job takes a unit time, and the goal is to minimize total completion time or makespan on a single machine. In this paper, we extend their problem to the budget setting in which each test consumes a job-specific cost, and we require that the total testing cost cannot exceed a given budget. We consider the offline variant (the lower processing time is known) and the oblivious variant (the lower processing time is unknown) and aim to minimize the total completion time or makespan on a single machine. For the total completion time objective, we show NP-hardness and derive a PTAS for the offline variant based on a novel LP rounding scheme. We give a $(4+ε)$-competitive algorithm for the oblivious variant based on a framework inspired by the worst-case lower-bound instance. For the makespan objective, we give an FPTAS for the offline variant and a $(2+ε)$-competitive algorithm for the oblivious variant. Our algorithms for the oblivious variants under both objectives run in time $O(poly(n/ε))$. Lastly, we show that our results are essentially optimal by providing matching lower bounds.

We study a fair resource scheduling problem, where a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents.Each job is associated with release time, deadline, and processing time such that it can be processed if its complete processing period is between its release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap.We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness.For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.