Search

This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric (1−ε) –approximation algorithms with sublinear running times are presented that improve the previous results. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The author is grateful for the support of Northeastern University for this research. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0239). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [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]

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]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. Leveraging the concavity of the objective functions in the two proposed convex integer-programming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA9550-19-1-0175 and FA9550-22-1-0172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3]. F. Qiu and R. Yao were supported in part by the U.S. Department of Energy Advanced Grid Modeling Program under [Grant DE-OE0000875]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0235. [ABSTRACT FROM AUTHOR]

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a "reduce-solve-combine" memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72371157, 61903144, 72031007]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0130) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0130). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]