Search

We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/V002813/1]; the National Science Foundation [Grants DMS-1763817, DMS-2120644, and DMS-2303251]; and Alexander von Humboldt-Stiftung. [ABSTRACT FROM AUTHOR]

Given a fixed finite metric space (V , μ) , the minimum 0-extension problem, denoted as 0 - Ext [ μ ] , is equivalent to the following optimization problem: minimize function of the form min x ∈ V n ∑ i f i (x i) + ∑ ij c ij μ (x i , x j) where f i : V → R are functions given by f i (x i) = ∑ v ∈ V c vi μ (x i , v) and c ij , c vi are given nonnegative costs. The computational complexity of 0 - Ext [ μ ] has been recently established by Karzanov and by Hirai: if metric μ is orientable modular then 0 - Ext [ μ ] can be solved in polynomial time, otherwise 0 - Ext [ μ ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L ♮ -convex functions. We consider a more general version of the problem in which unary functions f i (x i) can additionally have terms of the form c u v ; i μ (x i , { u , v }) for { u , v } ∈ F , where set F ⊆ V 2 is fixed. We extend the complexity classification above by providing an explicit condition on (μ , F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0 - Ext [ μ ] on orientable modular graphs. [ABSTRACT FROM AUTHOR]

Enumerating the extremal submodular functions defined on subsets of a fixed base set has only been done for base sets up to five elements. This paper reports the results of attempting to generate all such functions on a six-element base set. Using improved tools from polyhedral geometry, we have computed 360 billion of them, and provide the first reasonable estimate of their total number, which is expected to be between 1000 and 10,000 times this number. The applied Double Description and Adjacency Decomposition methods require an insertion order of the defining inequalities. We introduce two novel orders, which speed up the computations significantly, and provide additional insight into the highly symmetric structure of submodular functions. We also present an improvement to the combinatorial test used as part of the Double Description method, and use statistical analyses to estimate the degeneracy of the polyhedral cone used to describe these functions. The statistical results also highlight the limitations of the applied methods. [ABSTRACT FROM AUTHOR]

Wireless power transmission has been widely used to replenish energy for wireless sensor networks, where the energy consumption rate of sensor nodes is usually time varying and indefinite. However, few works have investigated the problem of long-term charging scheduling with random variable. This article designs an optimization model for the long-term scheduling of chargers to maximize the time-averaged charging utility while ensuring its time-averaged constraints of budget and response rate. The Lyapunov optimization technique is adopted to transform the stochastic optimization problem into a deterministic optimization problem, which remains NP-hard. Thus, an approximation algorithm following greedy approach is proposed to solve the deterministic optimization problem. We further provide the theoretical analysis of feasibility and performance guarantee of the proposed scheduling algorithm. The simulation results show that our algorithm outperforms three comparison algorithms by 6.53%, 20.04%, and 19.97% in terms of time-averaged charging utility, as well as by 11.25%, 4.42%, and 3.73% in terms of time-averaged response rate on average. [ABSTRACT FROM AUTHOR]

We define a new class of set functions that, in addition to being monotone and subadditive, also admit a very limited form of submodularity defined over a permutation of the ground set. We refer to this permutation as a submodular order. This class of functions includes monotone submodular functions as a subfamily. We give fast algorithms with strong approximation guarantees for maximizing submodular order functions under a variety of constraints and show a nearly tight upper bound on the highest approximation guarantee achievable by algorithms with polynomial query complexity. Applying this new notion to the problem of constrained assortment optimization in fundamental choice models, we obtain new algorithms that are both faster and have stronger approximation guarantees (in some cases, first algorithm with constant factor guarantee). We also show an intriguing connection to the maximization of monotone submodular functions in the streaming model, where we recover best known approximation guarantees as a corollary of our results. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the NSF Division of Civil, Mechanical, and Manufacturing Innovation [Grant 2340306] and Google Research Scholar Program. Supplemental Material: The online appendices are available at https://doi.org/10.1287/mnsc.2021.04108. [ABSTRACT FROM AUTHOR]

Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this significant problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an \({\tilde{O}(\frac{{k^{2}}}{{\varepsilon}})}\) amortized update time (in the number of insertions and deletions) and yields a \({(4+O(\varepsilon))}\) -approximate solution with respect to the dynamic optimum, where \(k\) is the rank of the matroid. [ABSTRACT FROM AUTHOR]

A Unifying Framework for the Convexification of Mixed-Integer Conic Binary Sets The paper "Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications," by Fatma Kilinc-Karzan, Simge Kucukyavuz, Dabeen Lee, and Soroosh Shafieezadeh-Abadeh, develops a unifying framework for convexifying mixed-integer conic binary sets. Many applications in machine-learning and operations research give rise to integer programming models with nonlinear structures and binary variables. The paper develops general methods for generating strong valid inequalities that take into account multiple conic constraints at the same time. The authors demonstrate that their framework applies to conic quadratic programming with binary variables, fractional programming, best subset selection, distributionally robust optimization, and sparse approximation of positive semidefinite matrices. We consider a general conic mixed-binary set where each homogeneous conic constraint j involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, fj, of common binary variables. Sets of this form naturally arise as substructures in a number of applications, including mean-risk optimization, chance-constrained problems, portfolio optimization, lot sizing and scheduling, fractional programming, variants of the best subset selection problem, a class of sparse semidefinite programs, and distributionally robust chance-constrained programs. We give a convex hull description of this set that relies on simultaneous characterization of the epigraphs of fj's, which is easy to do when all functions fj's are submodular. Our result unifies and generalizes an existing result in two important directions. First, it considers multiple general convex cone constraints instead of a single second-order cone type constraint. Second, it takes arbitrary nonnegative functions instead of a specific submodular function obtained from the square root of an affine function. We close by demonstrating the applicability of our results in the context of a number of problem classes. Funding: The research is supported, in part, by ONR [Grants N00014-19-1-2321 and N00014-22-1-2602], AFOSR [Grant FA9550-22-1-0365], the Institute for Basic Science [IBS-R029-C1, Y2], the FOUR Brain Korea 21 Program [NRF-5199990113928], the National Research Foundation of Korea [NRF-2022M3J6A1063021], the KAIST Starting Fund [KAIST-G04220016], NSF [Grant CMMI 1454548], and Early Postdoc Mobility Fellowship SNSF [Grant P2ELP2_195149]. [ABSTRACT FROM AUTHOR]

In this paper, we address the bounded/unbounded determination of geodesically convex optimization on Hadamard spaces. In Euclidean convex optimization, the recession function is a basic tool to study the unboundedness and provides the domain of the Legendre–Fenchel conjugate of the objective function. In a Hadamard space, the asymptotic slope function (Kapovich et al. in J Differ Geom 81:297–354, 2009), which is a function on the boundary at infinity, plays a role of the recession function. We extend this notion by means of convex analysis and optimization and develop a convex analysis foundation for the unbounded determination of geodesically convex optimization on Hadamard spaces, particularly on symmetric spaces of nonpositive curvature. We explain how our developed theory is applied to operator scaling and related optimization on group orbits, which are our motivation. [ABSTRACT FROM AUTHOR]

This article addresses the linear optimization problem to maximize the total costs that can be shared among a group of agents, while maintaining stability in the sense of the core constraints of a cooperative transferable utility game, or TU game. When maximizing total shareable costs, the cost shares must satisfy all constraints that define the core of a TU game, except for being budget balanced. The article first gives a fairly complete picture of the computational complexity of this optimization problem, its relation to optimization over the core itself, and its equivalence to other, minimal core relaxations that have been proposed earlier. We then address minimum cost spanning tree (MST) games as an example for a class of cost sharing games with non‐empty core. While submodular cost functions yield efficient algorithms to maximize shareable costs, MST games have cost functions that are subadditive, but generally not submodular. Nevertheless, it is well known that cost shares in the core of MST games can be found efficiently. In contrast, we show that the maximization of shareable costs is NP$$ \mathsf{NP} $$‐hard for MST games and derive a 2‐approximation algorithm. Our work opens several directions for future research. [ABSTRACT FROM AUTHOR]

In this paper, we study the Minimum Cost Submodular Cover (ℳ ) problem over the ground set of size n , which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a (1 − λ , (1 +) (1 + log 1 λ)) -bicriteria approximation solution within O (log n) adaptive complexity, where λ , are fixed parameters. Our algorithm requires O (n 2 log 2 n) query complexity, however, it can reduce to O (n log 3 n) instead while retaining a low adaptive complexity of O (log 2 n). Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem. [ABSTRACT FROM AUTHOR]

In this paper, we study the budget-constrained profit maximization problem with expensive seed endorsement, a derivation of the well-studied influence maximization and profit maximization in social networks. While existing research requires the non-negativity of the objective profit function, this paper considers real-world scenarios where costs may surpass revenue. Specifically, our problem can be regarded as maximizing the difference between a non-negative submodular function and a non-negative modular function under a knapsack constraint, allowing for negative differences. To tackle this challenge, we propose two algorithms. Firstly, we employ a twin greedy and enumeration technique to design a polynomial-time algorithm with a quarter weak approximation ratio, providing a balance between computational efficiency and solution quality. Then, we incorporate a threshold decreasing technique to enhance the time complexity of the first algorithm, yielding an improved computational efficiency while maintaining a reasonable level of solution accuracy. To our knowledge, this is the first paper to study the profit maximization beyond non-negativity and to propose polynomial-time algorithms with a constant bicriteria approximation ratio. [ABSTRACT FROM AUTHOR]

The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost f (·) due to an ordering σ of the items (say [n]), i.e., min σ ∑ i ∈ [ n ] f (E i , σ) , where E i , σ is the set of items mapped by σ to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a (2 - 1 + ℓ f 1 + | E |) -approximation for monotone submodular MLOP where ℓ f = f (E) max x ∈ E f ({ x }) satisfies 1 ≤ ℓ f ≤ | E | . Our theory provides new approximation bounds for special cases of the problem, in particular a (2 - 1 + r (E) 1 + | E |) -approximation for the matroid MLOP, where f = r is the rank function of a matroid. We further show that minimum latency vertex cover is 4 3 -approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing a non-negative submodular function under the b-matching constraint, in the semi-streaming model. When the function is linear, monotone, and non-monotone, we obtain the approximation ratios of 2 + ε , 3 + 2 2 ≈ 5.828 , and 4 + 2 3 ≈ 7.464 , respectively. We also consider a generalized problem, where a k-uniform hypergraph is given, along with an extra matroid or a k ′ -matchoid constraint imposed on the edges, with the same goal of finding a b-matching that maximizes a submodular function. When the extra constraint is a matroid, we obtain the approximation ratios of k + 1 + ε , k + 2 k + 1 + 2 , and k + 2 k + 2 + 3 for linear, monotone and non-monotone submodular functions, respectively. When the extra constraint is a k ′ -matchoid, we attain the approximation ratio 8 3 k + 64 9 k ′ + O (1) for general submodular functions. [ABSTRACT FROM AUTHOR]

Quality diversity (QD) is a branch of evolutionary computation that gained increasing interest in recent years. The Map-Elites QD approach defines a feature space, i.e., a partition of the search space, and stores the best solution for each cell of this space. We study a simple QD algorithm in the context of pseudo-Boolean optimisation on the "number of ones" feature space, where the ith cell stores the best solution amongst those with a number of ones in [ (i - 1) k , i k - 1 ] . Here k is a granularity parameter 1 ≤ k ≤ n + 1 . We give a tight bound on the expected time until all cells are covered for arbitrary fitness functions and for all k and analyse the expected optimisation time of QD on OneMax and other problems whose structure aligns favourably with the feature space. On combinatorial problems we show that QD finds a (1 - 1 / e) -approximation when maximising any monotone sub-modular function with a single uniform cardinality constraint efficiently. Defining the feature space as the number of connected components of an edge-weighted graph, we show that QD finds a minimum spanning forest in expected polynomial time. We further consider QD's performance on classes of transformed functions in which the feature space is not well aligned with the problem. The asymptotic performance is unaffected by transformations on easy functions like OneMax. Applying a worst-case transformation to a deceptive problem increases the expected optimisation time from O (n 2 log n) to an exponential time. However, QD is still faster than a (1+1) EA by an exponential factor. [ABSTRACT FROM AUTHOR]

In submodular k-partition, the input is a submodular function f : 2V → ℝ ≥ 0 (given by an evaluation oracle) along with a positive integer k, and the goal is to find a partition of the ground set V into k nonempty parts V1, V2,..., Vk in order to minimize ∑i=1k f(Vi). Narayanan, Roy, and Patkar [J. Algorithms, 21 (1996), pp. 306-330] designed an algorithm for submodular k-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [European J. Oper. Res., 186 (2008), pp. 77-90]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions--namely monotone, symmetric, and posimodular--and show the following results: (1) The approximation factor of their algorithm for monotone submodular k-partition is 4/3. This result improves on the 2-factor that was known to be achievable for monotone submodular k-partition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [R. Santiago, Proceedings of the International Workshop on Combinatorial Algorithms, IWOCA, 2021, pp. 516-530]. Our upper bound of 4/3 is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular k-partition. (2) The approximation factor of their algorithm for symmetric submodular k-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. (3) The approximation factor of their algorithm for posimodular submodular k-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is Ω(n/k). [ABSTRACT FROM AUTHOR]

In today's networked society, various sources of competitive information vie for attention and strive to enhance their social influence. Agents with valuable information aim to select a strategic set of influential individuals for information dissemination. This study delves into the Competitive Influence Maximization problem based on the independent cascade model, where an agent selects a seed set to maximize their social influence while contending with uncertain sources of competition. When adopting information, individuals exhibit a bandwagon effect. We begin by demonstrating that the objective function in our problem is neither supermodular nor submodular. Subsequently, we introduce upper and lower bound problems using the Sandwich approach, showcasing their objective functions as submodular and monotone non-decreasing. We propose a greedy algorithm to solve these bounds effectively. A theoretical analysis of the Sandwich approach's performance is presented, followed by experimental evaluations to assess its effectiveness. [ABSTRACT FROM AUTHOR]

Let D = (V , A) be a digraph. For an integer k ≥ 1 , a k-arc-connected flip is an arc subset of D such that after reversing the arcs in it the digraph becomes (strongly) k-arc-connected. The first main result of this paper introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function. More specifically, given some integer τ ≥ 1 , suppose d A + (U) + (τ k - 1) d A - (U) ≥ τ for all U ⊊ V , U ≠ ∅ , where d A + (U) and d A - (U) denote the number of arcs in A leaving and entering U, respectively. Let C be a crossing family over ground set V, and let f : C → Z be a crossing submodular function such that f (U) ≥ k τ (d A + (U) - d A - (U)) for all U ∈ C . Then D has a k-arc-connected flip J such that f (U) ≥ d J + (U) - d J - (U) for all U ∈ C . The result has several applications to Graph Orientations and Combinatorial Optimization. In particular, it strengthens Nash-Williams' so-called weak orientation theorem, and proves a weaker variant of Woodall's conjecture on digraphs whose underlying undirected graph is τ -edge-connected. The second main result of this paper is even more general. It introduces a sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This sufficient condition implies the classic result of Edmonds and Giles on the box-total dual integrality of a submodular flow system. It also has the consequence that in a weakly connected digraph, the intersection of two submodular flow systems is totally dual integral. [ABSTRACT FROM AUTHOR]

Given a separation oracle SO for a convex function f defined on Rn that has an integral minimizer inside a box with radius R, we show how to find an exact minimizer of f using at most • O(n(n log log(n)/ log(n) + log(R))) calls to SO and poly(n, log(R)) arithmetic operations, or • O(n log(nR)) calls to SO and exp(O(n)) · poly(log(R)) arithmetic operations. When the set of minimizers of f has integral extreme points, our algorithm outputs an integral minimizer of f . This improves upon the previously best oracle complexity of O(n² (n + log(R))) for polynomial time algorithms and O(n² log(nR)) for exponential time algorithms obtained by [Grötschel, Lovász and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. Our improvement on Grötschel, Lovász and Schrijver’s result generalizes to the setting where the set of minimizers of f is a rational polyhedron with bounded vertex complexity. For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most O(n³ log log(n)/ log(n)) calls to an evaluation oracle, and an exponential time algorithm that makes at most O(n2 log(n)) calls to an evaluation oracle. These improve upon the previously best O(n³ log² (n)) oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, Végh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity O(n³ log(n)) given in the former work. Our result is achieved via a reduction to the Shortest Vector Problem in lattices. We show how an approximately shortest vector of an auxiliary lattice can be used to effectively reduce the dimension of the problem. Our analysis of the oracle complexity is based on a potential function that simultaneously captures the size of the search set and the density of the lattice, which we analyze via tools from convex geometry and lattice theory. [ABSTRACT FROM AUTHOR]

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1- product of matrices S 1 ∈ R m 1 × n 1 , S 2 ∈ R m 2 × n 2 is a matrix in R (m 1 + m 2) × (n 1 n 2) whose columns are the concatenation of each column of S 1 with each column of S 2. The k - product generalizes the 1-product, by taking as input two matrices S 1 , S 2 together with k − 1 special rows of each of those matrices, and outputting a certain composition of S 1 , S 2 . Our first result is a polynomial time algorithm for the following problem: given a matrix S , is S a k -product of some matrices, up to permutation of rows and columns? Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information from information theory. Our study is motivated by a close link between the 1-product of matrices and the Cartesian product of polytopes, and more generally between the k -product of matrices and the glued product of polytopes. These connections rely on the concept of a slack matrix, which gives an algebraic representation of classes of affinely equivalent polytopes. The slack matrix recognition problem is the problem of determining whether a given matrix is a slack matrix. This is an intriguing problem whose complexity is unknown. Our algorithm reduces the problem to instances which cannot be expressed as k -products of smaller matrices. In the second part of the paper, we give a combinatorial interpretation of k -products for two well-known classes of polytopes: 2-level matroid base polytopes and stable set polytopes of perfect graphs. We also show that the slack matrix recognition problem is polynomial-time solvable for such polytopes. Those two classes are special cases of 2-level polytopes, for which we conjecture that the slack matrix recognition problem is polynomial-time solvable. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f : 2 V → R , computing a k-partition { V 1 , ... , V k } of V with minimum ∑ i = 1 k f (V i) . The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for fixed k ≤ 3 . In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem. [ABSTRACT FROM AUTHOR]

Problem definition: This paper studies the single-warehouse assortment selection problem that aims to minimize the order fulfillment cost under the cardinality constraint. We propose two fulfillment-related cost functions corresponding to spillover fulfillment and order splitting. This problem includes the fill rate maximization problem as a special case. We show that although the objective function is submodular for a broad class of cost functions, the fill rate maximization problem with the largest order size being two is NP-hard. Methodology/results: To make the problem tractable to solve, we formulate the general warehouse assortment problem under the two types of cost functions as mixed integer linear programs (MILPs). We also provide a dynamic programming algorithm to solve the problem in polynomial time if orders are nonoverlapping. Furthermore, we propose a simple heuristic called the marginal choice indexing (MCI) policy that allows the warehouse to store the most popular products. This policy is easy to compute, and hence, it is scalable to large-size problems. Although the performance of MCI can be arbitrarily bad in some extreme scenarios, we find a general condition under which it is optimal. This condition is satisfied by many multi-purchase choice models. Managerial implications: Through extensive numerical experiments on a real-world data set from RiRiShun Logistics, we find that the MCI policy is surprisingly near optimal in all the settings we tested. Simply applying the MCI policy, the fill rate is estimated to improve by 9.18% on average compared with the current practice for the local transfer centers on the training data set. More surprisingly, the MCI policy outperforms the MILP optimal solution in 14 of 25 cases on the test data set, illustrating its robustness against demand fluctuations. History: This paper has been accepted as part of the 2021 M&SOM Data-Driven Research Challenge. Funding: This work was supported by the Singapore Ministry of Education (MoE) Tier 1 [Grant 23-0619-P0001]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/msom.2022.0428. [ABSTRACT FROM AUTHOR]

Two-Stage Matching and Pricing in Ride-Hailing Platforms Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem with or without pricing to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces, such as ride-hailing platforms. We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency and two-stage joint matching and pricing for maximizing market efficiency. Using various techniques, such as introducing convex programming–based matching and graph decompositions, submodular maximization, and factor-revealing linear programs, we obtain either optimal competitive or improved approximation algorithms compared with naïve solutions. We enrich our theoretical study by data-driven numerical simulations using DiDi's ride-sharing data sets. Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces, such as ride-hailing platforms. We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, using a randomized primal-dual algorithm applied to a family of "balancing" convex programs, we obtain the optimal 3/4 competitive ratio against the optimum off-line benchmark. Using a factor-revealing program and connections to submodular optimization, we improve this ratio against the optimum online benchmark to (1 − 1 / e + 1 / e 2) ≈ 0.767 for the unweighted and 0.761 for the weighted case. In the latter problem, we design an optimal 1/2-competitive joint pricing and matching algorithm by borrowing ideas from the ex ante prophet inequality literature. We also show an improved (1 − 1 / e) -competitive algorithm for the special case of demand efficiency objective using the correlation gap of submodular functions. Finally, we complement our theoretical study by using DiDi's ride-sharing data set for Chengdu city and numerically evaluating the performance of our proposed algorithms in practical instances of this problem. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2398. [ABSTRACT FROM AUTHOR]

In this article, we consider the following question: Can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions that are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature. [ABSTRACT FROM AUTHOR]

Relying on the notions of submodular function and partial metric, we introduce normed inverse semigroups as a generalization of normed groups and sup-semilattices equipped with an upper valuation. We define the property of skew-convexity for a metric on an inverse semigroup, and prove that every norm on a Clifford semigroup gives rise to a right-subinvariant and skew-convex metric; it makes the semigroup into a Hausdorff topological inverse semigroup if the norm is cyclically permutable. Conversely, we show that every Clifford monoid equipped with a right-subinvariant and skew-convex metric admits a norm for which the metric topology and the norm topology coincide. We characterize convergence of nets and show that Cauchy completeness implies conditional monotone completeness with respect to the natural partial order of the inverse semigroup. [ABSTRACT FROM AUTHOR]

In this paper, we present a thorough study of the regularized submodular maximization problem, in which the objective $ f:=g-\ell $ f := g − ℓ can be expressed as the difference between a submodular function and a modular function. This problem has drawn much attention in recent years. While existing works focuses on the case of g being monotone, we investigate the problem with a nonmonotone g. The main technique we use is to introduce a distorted objective function, which varies weights of the submodular component g and the modular component ℓ during the iterations of the algorithm. By combining the weighting technique and measured continuous greedy algorithm, we present an algorithm for the matroid-constrained problem, which has a provable approximation guarantee. In the cardinality-constrained case, we utilize random greedy algorithm and sampling technique together with the weighting technique to design two efficient algorithms. Moreover, we consider the unconstrained problem and propose a much simpler and faster algorithm compared with the algorithms for solving the problem with a cardinality constraint. [ABSTRACT FROM AUTHOR]

Stochastic optimization has experienced significant growth in recent decades, with the increasing prevalence of variance reduction techniques in stochastic optimization algorithms to enhance computational efficiency. In this paper, we introduce two projection-free stochastic approximation algorithms for maximizing diminishing return (DR) submodular functions over convex constraints, building upon the Stochastic Path Integrated Differential EstimatoR (SPIDER) and its variants. Firstly, we present a SPIDER Continuous Greedy (SPIDER-CG) algorithm for the monotone case that guarantees a (1 - e - 1) OPT - ε approximation after O (ε - 1) iterations and O (ε - 2) stochastic gradient computations under the mean-squared smoothness assumption. For the non-monotone case, we develop a SPIDER Frank–Wolfe (SPIDER-FW) algorithm that guarantees a 1 4 (1 - min x ∈ C ‖ x ‖ ∞) OPT - ε approximation with O (ε - 1) iterations and O (ε - 2) stochastic gradient estimates. To address the practical challenge associated with a large number of samples per iteration, we introduce a modified gradient estimator based on SPIDER, leading to a Hybrid SPIDER-FW (Hybrid SPIDER-CG) algorithm, which achieves the same approximation guarantee as SPIDER-FW (SPIDER-CG) algorithm with only O (1) samples per iteration. Numerical experiments on both simulated and real data demonstrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

A New Concept to Study Substitute Structures in Economics and Operations Models In "S-Convexity and Gross Substitutability," Chen and Li propose a novel concept of S-convex functions defined on continuous spaces, which extends a key concept of M-natural-convex functions in discrete convex analysis. They develop a host of fundamental properties and characterizations of S-convex functions. In a parametric maximization model with a box constraint, they show that the set of optimal solutions is nonincreasing in the parameters if the objective function is S-concave and prove the necessity of S-concavity under some conditions. The monotonicity result finds notable inventory models. Interestingly, the authors show that S-concavity is the correct notion characterizing gross substitutability, an important concept in economics for markets with divisible goods. We propose a new concept of S-convex functions (and its variant, semistrictly quasi-S- (SSQS)-convex functions) to study substitute structures in economics and operations models with continuous variables. We develop a host of fundamental properties and characterizations of S-convex functions, including various preservation properties, conjugate relationships with submodular and convex functions, and characterizations using Hessians. For a divisible market, we show that the utility function satisfies gross substitutability if and only if it is S-concave under mild regularity conditions. In a parametric maximization model with a box constraint, we show that the set of optimal solutions is nonincreasing in the parameters if the objective function is (SSQS-) S-concave. Furthermore, we prove that S-convexity is necessary for the property of nonincreasing optimal solutions under some conditions. Our monotonicity result is applied to analyze two notable inventory models: a single-product inventory model with multiple unreliable suppliers and a classic multiproduct dynamic inventory model with lost sales. Funding: This work was supported by the National Science Foundation [Grants CMMI-1538451 and CMMI-1635160] and the gift fund from JD.com. Supplemental Material: The online companion is available at https://doi.org/10.1287/opre.2022.2394. [ABSTRACT FROM AUTHOR]

Adaptivity in Stochastic Submodular Cover Solutions to stochastic optimization problems are typically sequential decision processes that make decisions one by one, waiting for (and using) the feedback from each decision. Whereas such "adaptive" solutions achieve the best objective, they can be very time-consuming because of the need to wait for feedback after each decision. A natural question is are there solutions that only adapt (i.e., wait for feedback) a few times whereas still being competitive with the fully adaptive optimal solution? In "The Power of Adaptivity for Stochastic Submodular Cover," Ghuge, Gupta, and Nagarajan resolve this question in the context of stochastic submodular cover, which is a fundamental stochastic covering problem. They provide algorithms that achieve a smooth trade-off between the number of adaptive "rounds" and the solution quality. The authors also demonstrate via experiments on real-world and synthetic data sets that, even for problems with more than 1,000 decisions, about six rounds of adaptivity suffice to obtain solutions nearly as good as fully adaptive solutions. In the stochastic submodular cover problem, the goal is to select a subset of stochastic items of minimum expected cost to cover a submodular function. Solutions in this setting correspond to sequential decision processes that select items one by one adaptively (depending on prior observations). Whereas such adaptive solutions achieve the best objective, the inherently sequential nature makes them undesirable in many applications. We show how to obtain solutions that approximate fully adaptive solutions using only a few "rounds" of adaptivity. We study both independent and correlated settings, proving smooth trade-offs between the number of adaptive rounds and the solution quality. Experiments on synthetic and real data sets show qualitative improvements in the solutions as we allow more rounds of adaptivity; in practice, solutions with a few rounds of adaptivity are nearly as good as fully adaptive solutions. Funding: R. Ghuge and V. Nagarajan were supported in part by the National Science Foundation (NSF) Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-1940766] and Division of Computing and Communication Foundations [Grant CCF-2006778]. A. Gupta was supported in part by the NSF [Grants CCF-1907820, CCF1955785, and CCF-2006953]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2388. [ABSTRACT FROM AUTHOR]

We study the problem of Regularized Unconstrained SubmodularMaximization (RegularizedUSM) as defined by Bodek and Feldman (Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case, arXiv:2204.03412, 2022): given query access to a non-negative submodular function f : 2 N → R ≥ 0 and a linear function ℓ : 2 N → R over the same ground set N , output a set T ⊆ N approximately maximizing the sum f (T) + ℓ (T) . An algorithm is said to provide an (α , β) -approximation for RegularizedUSM if it outputs a set T such that E [ f (T) + ℓ (T) ] ≥ max S ⊆ N [ α · f (S) + β · ℓ (S) ] . We also consider the setting where S and T are constrained to be independent in a given matroid, which we refer to as Regularized ConstrainedSubmodular Maximization (RegularizedCSM). The special case of RegularizedCSM with monotone f has been extensively studied (Sviridenko et al. in Math Oper Res 42(4):1197–1218, 2017; Feldman in Algorithmica 83(3):853–878, 2021; Harshaw et al., in: International conference on machine learning, PMLR, 2634–2643, 2019), whereas we are aware of only one prior work that studies RegularizedCSM with non-monotone f (Lu et al. in Optimization 1–27, 2023), and that work constrains ℓ to be non-positive. In this work, we provide improved (α , β) -approximation algorithms for both RegularizedUSM and RegularizedCSM with non-monotone f. Specifically, we are the first to provide nontrivial (α , β) -approximations for RegularizedCSM where the sign of ℓ is unconstrained, and the α we obtain for RegularizedUSM improves over (Bodek and Feldman in Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case, arXiv:2204.03412, 2022) for all β ∈ (0 , 1) . We also prove new inapproximability results for RegularizedUSM and RegularizedCSM, as well as 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving a 0.491-inapproximability result due to Oveis Gharan and Vondrak (in: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SIAM, pp 1098–1116, 2011). [ABSTRACT FROM AUTHOR]

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its "attribute", we study two fairness criteria. For instance, in one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is, for instance, relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. We establish the correctness of our integer programs, based on Frank's separation theorem [Frank, Discrete Math. 1982]. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side. [ABSTRACT FROM AUTHOR]

This study investigates a novel intervention approach to network games, in which players are delinquents whose payoffs depend on the actions of their network neighbors. The social planner aims to manipulate the delinquency costs of players, seeking to minimize the total delinquency level. We consider two intervention scenarios. First, we consider binary interventions, where the planner can either increase the cost of an offender by a fixed amount; or leave its cost unchanged. The optimal intervention problem involves maximizing a submodular function. We establish a connection between cost and structural intervention in networks. Next, we consider continuous levels of intervention, where the planner can choose how much to increase the cost of an offender. We show that the optimal intervention problem is a tractable convex optimization if the intervention function is concave. We provide a characterization of the optimal intervention which is highly related to players' centralities in the network. We further discuss the interior solution and apply our result to nested split graphs. [ABSTRACT FROM AUTHOR]

We address the challenge of identifying meaningful communities by proposing a model based on convex game theory and a measure of community strength. Many existing community detection methods fail to provide unique solutions, and it remains unclear how the solutions depend on initial conditions. Our approach identifies strong communities with a hierarchical structure, visualizable as a dendrogram, and computable in polynomial time using submodular function minimization. This framework extends beyond graphs to hypergraphs or even polymatroids. In the case when the model is graphical, a more efficient algorithm based on the max-flow min-cut algorithm can be devised. Though not achieving near-linear time complexity, the pursuit of practical algorithms is an intriguing avenue for future research. Our work serves as the foundation, offering an analytical framework that yields unique solutions with clear operational meaning for the communities identified. [ABSTRACT FROM AUTHOR]

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384. [ABSTRACT FROM AUTHOR]

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]

Federated learning (FL) has been proposed as a privacy-preserving distributed learning paradigm, which differs from traditional distributed learning in two main aspects: the systems heterogeneity, meaning that clients participating in training have significant differences in systems performance including CPU frequency, dataset size, and transmission power, and the statistical heterogeneity, indicating that the data distribution among clients exhibits Non-Independent Identical Distribution. Therefore, the random selection of clients will significantly reduce the training efficiency of FL. In this article, we propose a client selection mechanism considering both systems and statistical heterogeneity, which aims to improve the time-to-accuracy performance by trading off the impact of systems performance differences and data distribution differences among the clients on training efficiency. First, client selection is formulated as a combinatorial optimization problem that jointly optimizes systems and statistical performance. Then, we generalize it to a submodular maximization problem with knapsack constraint, and propose the Iterative Greedy with Partial Enumeration (IGPE) algorithm to greedily select the suitable clients. Then, the approximation ratio of IGPE is analyzed theoretically. Extensive experiments verify that the time-to-accuracy performance of the IGPE algorithm outperforms other compared algorithms in a variety of heterogeneous environments. [ABSTRACT FROM AUTHOR]

Let $T=(V,E)$ be a tree in which each edge is assigned a cost; let $\mathcal{P}$ be a set of source–sink pairs of vertices in V in which each source–sink pair produces a profit. Given a lower bound K for the profit, the K -prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut $M\subseteq E$ such that the total profit of the disconnected pairs after removing M from T is at least K , and the total cost of edges in M plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is $(\frac{8}{3}+\frac{4}{3}\kappa+\varepsilon)$ , where $\kappa$ is the total curvature of the submodular function and $\varepsilon$ is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases. [ABSTRACT FROM AUTHOR]

We consider a two-stage submodular maximization problem subject to a cardinality constraint and k matroid constraints, where the objective function is the expected difference of a nonnegative monotone submodular function and a nonnegative monotone modular function. We give two bi-factor approximation algorithms for this problem. The first is a deterministic $\left({{1 \over {k + 1}}\left({1 - {1 \over {{e^{k + 1}}}}} \right),1} \right)$ -approximation algorithm, and the second is a randomized $\left({{1 \over {k + 1}}\left({1 - {1 \over {{e^{k + 1}}}}} \right) - \varepsilon ,1} \right)$ -approximation algorithm with improved time efficiency. [ABSTRACT FROM AUTHOR]

Submodular function maximization is an attractive optimization model and also a well-studied problem with a variety of algorithms available. Constraint generation (CG) approaches are appealing techniques to tackle the problem with, as the mixed-integer programming formulation of the problem suffers from the exponential size of the number of constraints. Most of the problems in these topics are of combinatorial nature and involve graphs on which the maximization is defined. Inspired by the recent work of Uematsu et al. (J Oper Res Soc Jpn 63:41–59, 2020), in this paper we introduce variants of the CG algorithm which take into account certain properties of the input graph aiming at informed selection of the constraints. Benchmarking results are shown to demonstrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

We present combinatorial and parallelizable algorithms for the maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to 1/6−ε, and even further to 0.193−ε by increasing the adaptivity by a factor of O(log(k)). The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in O(log(n)) adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio 1/6 − ε, adaptivity O(log(n)), and query complexity O(n log(k)), while the second has approximation ratio 0.193 − ε, adaptivity O(log(n) log(k)), and query complexity O(n log(k)). Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension. 1. [ABSTRACT FROM AUTHOR]

Benefitting from the maturation of Wireless Power Transfer technology, Wireless Rechargeable Sensor Networks have become a promising solution for prolonging network lifetime. In practical charging scenarios, obstacles are ubiquitous. However, most prior arts have failed to consider the combined impacts of the material, size, and location of obstacles on the charging performance, making these schemes unsuitable for real applications. In this article, we study a fundamental issue of Wireless chArger placement wIth obsTacles (WAIT), that is, how to place wireless chargers by comprehensively considering these parameters of obstacles, such that the overall charging utility is maximized. To tackle theWAIT problem, we first build a practical charging model with obstacles by introducing shadow fading, and conduct experiments to verify its correctness. Then, we design a piecewise constant function to approximate the nonlinear charging power. Afterwards, we develop a Dominating Coverage Set extraction algorithm to reduce the continuous solution space to a limited number. Finally, we prove the WAIT problem is a maximizing monotone submodular function problem, and propose a 1-1/e - ε approximation algorithm to address it. Extensive simulations and field experiments show that our scheme outperforms comparison algorithms by at least 20.6% in charging utility improvement. [ABSTRACT FROM AUTHOR]

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost = f(C). We give an algorithm that given an n-vertex graph G, parameter ɛ > 0, and the function f represented by an oracle, in time n(log 1/ɛ) finds a cycle C in G with f(C)≤ (1+ɛ).. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest (s,t-Path problem, which requires exponentially many queries to the oracle for finding an n2/3-ɛ-approximation Goel et al. [7], FOCS 2009. We complement our algorithm with a matching lower bound. We show that for every ɛ > 0, obtaining a (1+ɛ)-approximation requires at least nΩ (log 1/ ɛ) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost can be found in time n(log). In particular, for = n(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n(log n) queries are required even when = (n). We also consider special cases of monotone submodular functions, corresponding to the number of different color classes needed to cover a cycle in an edge-colored multigraph G. For special cases of the corresponding minimization problem, we obtain fixed-parameter tractable algorithms and polynomial-time algorithms, when restricted to certain classes of inputs. [ABSTRACT FROM AUTHOR]

An event-based social network is a new type of social network that combines online and offline networks, and one of its important problems is recommending suitable activities to users. However, the current research seldom considers balancing the accuracy, diversity and fairness of group activity recommendations. To solve this problem, we propose a group activity recommendation approach that considers fairness and diversity perception. Firstly, we calculate activity similarity based on the context and construct an activity similarity graph. We define the weighted coverage on the similarity graph as a submodular function and transform the problem of fair and diverse group activity recommendation into maximizing the weighted coverage on the similarity graph while considering accuracy, fairness, and diversity. Secondly, we employ a greedy algorithm to find an approximate solution that maximizes the weighted coverage with an approximation ratio. Finally, we conducted experiments on two real datasets and demonstrate the superiority of our method compared to existing approaches. Specifically, in the domain of diversity-based recommendation algorithms, our method achieves a remarkable 0.02% increase in recall rate. Furthermore, in the domain of fairness-based recommendation algorithms, our proposed method outperforms the latest approach by 0.05% in terms of overall metrics. These results highlight the effectiveness of our method in achieving a better balance among accuracy, fairness, and diversity. [ABSTRACT FROM AUTHOR]

Federated learning is a promising technique in cloud computing and edge computing environments, and designing a reasonable resource allocation scheme for federated learning is particularly important. In this paper, we propose an auction mechanism for federated learning resource allocation in the edge–cloud collaborative environment, which can motivate data owners to participate in federated learning and effectively utilize the resources and computing power of edge servers, thereby reducing the pressure on cloud services. Specifically, we formulate the federated learning platform data value maximization problem as an integer programming model with multiple constraints, develop a resource allocation algorithm based on the monotone submodular value function, devise a payment algorithm based on critical price theory and demonstrate that the mechanism satisfies truthfulness and individual rationality. [ABSTRACT FROM AUTHOR]

Our research investigates a joint inventory replenishment and pricing problem, where a seller controls the price of a leading product while restocking for all the products. We demonstrate that the seller's expected value functions present an L♮-concave$L^\natural \text{-concave}$ structure, recommending an optimal order‐up‐to inventory‐level and list‐price policy. Our findings reveal divergent economic relationships between products from the seller's and customer's perspectives, suggesting managers broaden their strategies beyond customer viewpoints. We extend the pricing and inventory analysis to scenarios involving three substitute products under both price and inventory control. In these situations, we further reveal that sellers and customers uniformly view product inventories as substitutes, and the corresponding value functions are submodular and mutually diagonally dominant. [ABSTRACT FROM AUTHOR]

Multi‐agent systems are generally applicable in various fields and aim to coordinate the decisions from agents, each of which makes a local decision. In particular, research on operations management with mobile multi‐agents such as drones has gained prominence in recent years. In this article, we present a mobile multi‐agent sensing problem, which is formulated as a submodular maximization problem under a partition matroid constraint. When events detected by agents lead to severe and catastrophic consequences, obtaining (near)‐optimal solutions by using exact algorithms is crucial to reducing the probability of harmful situations. Therefore, in this article we propose an exact solution approach, using two valid inequalities for our problem to find a (near)‐optimal solution. Moreover, we deal with the risk‐averse decision and its cutting‐plane algorithm for our problem, which is to maximize conditional value‐at‐risk (CVaR). Finally, we show the performance of our algorithms through numerical experiments, including a case study on forest fires. [ABSTRACT FROM AUTHOR]