Search

Truck platooning technology allows trucks to drive at short headways to save fuel and associated emissions. However, fuel savings from platooning are relatively small, so forming platoons should be convenient and associated with minimum detours and delays. In this paper, we focus on developing optimization technology to form truck platoons. We formulate a mathematical program for the platoon routing problem with time windows (PRP-TW) based on a time–space network. We provide polynomial-time algorithms to solve special cases of PRP-TW with two-truck platoons. Based on these special cases, we build several fast heuristics. An extensive set of numerical experiments shows that our heuristics perform well. Moreover, we show that simple two-truck platoons already capture most of the potential savings of platooning. History: Accepted by Pascal van Hentenryck, Area Editor for Computational Modeling: Methods and Analysis. Funding: This work was supported by the Netherlands Organization for Scientific Research (NWO) as part of the Spatial and Transport Impacts of Automated Driving [Grant 438-15-161] project. 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.2020.0302) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2020.0302). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper we consider the fundamental scheduling problem of minimizing the weighted number of tardy jobs on a single machine. We present a simple pseudo polynomial-time algorithm for this problem that improves upon the classical Lawler and Moore algorithm from the late 60's under certain scenarios and parameter settings. Our algorithm uses (max,+)-convolutions as its main tool, exploiting recent improved algorithms for computing such convolutions, and obtains several different running times depending on the specific improvement used. We also provide a related lower bound for the problem under a variant of the well-known Strong Exponential Time Hypothesis (SETH). History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Israel Science Foundation [Grant 1070/20]. [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]

For an unbalanced cooperative game, its grand coalition can be stabilized by some instruments, such as subsidization and penalization, that impose new cost terms to certain coalitions. In this paper, we study an alternative instrument, referred to as cost adjustment, that does not need to impose any new coalition-specific cost terms. Specifically, our approach is to adjust existing cost coefficients of the game under which (i) the game becomes balanced so that the grand coalition becomes stable, (ii) a desired way of cooperation is optimal for the grand coalition to adopt, and (iii) the total cost to be shared by the grand coalition is within a prescribed range. Focusing on a broad class of cooperative games, known as integer minimization games, we formulate the problem on how to optimize the cost adjustment as a constrained inverse optimization problem. We prove NP -hardness and derive easy-to-check feasibility conditions for the problem. Based on two linear programming reformulations, we develop two solution algorithms. One is a cutting-plane algorithm, which runs in polynomial time when the corresponding separation problem is polynomial time solvable. The other needs to explicitly derive all the inequalities of a linear program, which runs in polynomial time when the linear program contains only a polynomial number of inequalities. We apply our models and solution algorithms to two typical unbalanced games, including a weighted matching game and an uncapacitated facility location game, showing that their optimal cost adjustments can be obtained in polynomial time. History: Accepted by Area Editor Andrea Lodi for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72022018 and 72091210]; the Research Grants Council of the Hong Kong SAR, China [Grant 16210020]; Hong Kong Polytechnic University [Grant P0032007]; and the Youth Innovation Promotion Association, Chinese Academy of Sciences [Grant 2021454]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0268. [ABSTRACT FROM AUTHOR]

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. 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.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Motivated by applications arising on social networks, we study a generalization of the celebrated dominating set problem called the Positive Influence Dominating Set (PIDS). Given a graph G with a set V of nodes and a set E of edges, each node i in V has a weight bi, and a threshold requirement gi. We seek a minimum weight subset T of V, so that every node i not in T is adjacent to at least gi members of T. When gi is one for all nodes, we obtain the weighted dominating set problem. First, we propose a strong and compact extended formulation for the PIDS problem. We then project the extended formulation onto the space of the natural node-selection variables to obtain an equivalent formulation with an exponential number of valid inequalities. Restricting our attention to trees, we show that the extended formulation is the strongest possible formulation, and its projection (onto the space of the node variables) gives a complete description of the PIDS polytope on trees. We derive the necessary and sufficient facet-dening conditions for the valid inequalities in the projection and discuss their polynomial time separation. We embed this (exponential size) formulation in a branch-and-cut framework and conduct computational experiments using real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. On a test-bed of 100 real-world graph instances, our approach finds solutions that are on average 0.2% from optimality and solves 51 out of the 100 instances to optimality. Summary of Contribution: In influence maximization problems, a decision maker wants to target individuals strategically to cause a cascade at a minimum cost over a social network. These problems have attracted significant attention as their applications can be found in many different domains including epidemiology, healthcare, marketing, and politics. However, computationally solving large-scale influence maximization problems to near optimality remains a substantial challenge for the computing community, which thus represent significant opportunities for the development of operations-research based models, algorithms, and analysis in this interface. This paper studies the positive influence dominating set (PIDS) problem, an influence maximization problem on social networks that generalizes the celebrated dominating set problem. It focuses on developing exact methods for solving large instances to near optimality. In other words, the approach results in strong bounds, which then provide meaningful comparative benchmarks for heuristic approaches. The paper first shows that straightforward generalizations of well-known formulations for the dominating set problem do not yield strong (i.e., computationally viable) formulations for the PIDS problem. It then strengthens these formulations by proposing a compact extended formulation and derives its projection onto the space on the natural node-selection variables, resulting in two equivalent (stronger) formulations for the PIDS problem. The projected formulation on the natural node-variables contains a new class of valid inequalities that are shown to be facet-defining for the PIDS problem. These theoretical results are complemented by in-depth computational experiments using a branch-and-cut framework, on a testbed of 100 real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. They demonstrate the effectiveness of the proposed formulation in solving large scale problems finding solutions that are on average 0.2% from optimality and solving 51 of the 100 instances to optimality. [ABSTRACT FROM AUTHOR]

Targeted marketing strategies are of significant interest in the smartapp economy. Typically, one seeks to identify individuals to strategically target in a social network so that the network is influenced at a minimal cost. In many practical settings, the effects of direct influence predominate, leading to the positive influence dominating set with partial payments (PIDS-PP) problem that we discuss in this paper. The PIDS-PP problem is NP-complete because it generalizes the dominating set problem. We discuss several mixed integer programming formulations for the PIDS-PP problem. First, we describe two compact formulations on the payment space. We then develop a stronger compact extended formulation. We show that when the underlying graph is a tree, this compact extended formulation provides integral solutions for the node selection variables. In conjunction, we describe a polynomial-time dynamic programming algorithm for the PIDS-PP problem on trees. We project the compact extended formulation onto the payment space, providing an equivalently strong formulation that has exponentially many constraints. We present a polynomial time algorithm to solve the associated separation problem. Our computational experience on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) demonstrates the efficacy of our strongest payment space formulation. It finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality. Summary of Contribution: The study of influence propagation is important in a number of applications including marketing, epidemiology, and healthcare. Typically, in these problems, one seeks to identify individuals to strategically target in a social network so that the entire network is influenced at a minimal cost. With the ease of tracking consumers in the smartapp economy, the scope and nature of these problems have become larger. Consequently, there is considerable interest across multiple research communities in computationally solving large-scale influence maximization problems, which thus represent significant opportunities for the development of operations research–based methods and analysis in this interface. This paper introduces the positive influence dominating set with partial payments (PIDS-PP) problem, an influence maximization problem where the effects of direct influence predominate, and it is possible to make partial payments to nodes that are not targeted. The paper focuses on model development to solve large-scale PIDS-PP problems. To this end, starting from an initial base optimization model, it uses several operations research model strengthening techniques to develop two equivalent models that have strong computational performance (and can be theoretically shown to be the best model for trees). Computational experiments on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) attest to the efficacy of the best model, which finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality. [ABSTRACT FROM AUTHOR]

To reduce unproductive picker walking in traditional picker-to-parts warehousing systems, automated guided vehicles (AGVs) are used to support human order pickers. In an AGV-assisted order-picking system, each human order picker is accompanied by an AGV during the order-picking process. AGVs receive the picked items and, once a picking order is complete, autonomously bring the collected items to the shipping area. Meanwhile, a new AGV is requested to meet the picker at the first storage position of the next picking order. Thus, the picker does not have to return to a central depot and continuously picks order after order. This paper addresses both the routing of an AGV-assisted picker through a single-block, parallel-aisle warehouse and the sequencing of incoming orders. We present an exact polynomial time routing algorithm for the case of a given order sequence, which is an extension of the algorithm of Ratliff and Rosenthal [Ratliff HD, Rosenthal AS (1983) Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem. Oper. Res. 1(3):507–521], and a heuristic for the case in which order sequencing is part of the problem. In addition, we investigate the use of highly effective traveling salesman problem (TSP) solvers that can be applied after a transformation of both problem types into a standard TSP. The numerical studies address the performance of these methods and study the impact of AGV usage on picker travel: by using AGVs to avoid returns to the depot and by sequencing in (near-) optimal fashion, picker walking can be reduced by about 20% compared with a traditional setting. Sharing AGVs among the picker workforce enables a pooling effect so that, in larger warehouses, only about 1.5 AGVs per picker are required to avoid picker waiting. Summary of Contribution: New technologies, such as automatic guided vehicles (AGVs) are currently considered as options to increase the efficiency of the order-picking process in warehouses, which is responsible for a large part of operational warehousing costs. In addition, picker-routing decisions are more and more often based on algorithmic decision support because of their relevance for decreasing unproductive picker walking time. This paper addresses both aspects and investigates routing algorithms for AGV-assisted order picking in parallel-aisle warehouses. We present a dynamic programming routine with polynomial runtime to solve the problem variant in which the sequence of picking orders is fixed. For the variant in which this sequence is a decision, we show that the problem becomes NP-hard, and we propose a greedy heuristic and investigate the use of state-of-the-art exact and heuristic traveling salesman problem solution methods to address the problem. The numerical studies demonstrate the effectiveness of the algorithms and indicate that AGV assistance promises strong improvements in the order-fulfillment process. Because of the practical relevance of AGV-assisted order picking and the presented algorithmic contributions, we believe that the paper is relevant for practitioners and researchers alike. [ABSTRACT FROM AUTHOR]

Summary of Contribution: Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees (Fenwick 1994) and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. Local polynomial regression is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multidimensional binary indexed trees. Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach. Summary of Contribution. Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. [ABSTRACT FROM AUTHOR]

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomial-time hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers time-dependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the field of computing. Different cases are considered depending on which of the nodes contribute to the waiting cost or waiting limit (all nodes, all nodes except the origin, a subset of nodes...). The computational complexity of all cases is determined, providing complexity proofs for the variants that are NP-Hard and polynomial time algorithms for the variants that are in P. [ABSTRACT FROM AUTHOR]

Best subset of groups selection (BSGS) is the process of selecting a small part of nonoverlapping groups to achieve the best interpretability on the response variable. It has attracted increasing attention and has far-reaching applications in practice. However, due to the computational intractability of BSGS in high-dimensional settings, developing efficient algorithms for solving BSGS remains a research hotspot. In this paper, we propose a group-splicing algorithm that iteratively detects the relevant groups and excludes the irrelevant ones. Moreover, coupled with a novel group information criterion, we develop an adaptive algorithm to determine the optimal model size. Under certain conditions, it is certifiable that our algorithm can identify the optimal subset of groups in polynomial time with high probability. Finally, we demonstrate the efficiency and accuracy of our methods by comparing them with several state-of-the-art algorithms on both synthetic and real-world data sets. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms-Discrete. Funding: This work was supported by National Natural Science Foundation of China [Grants 72171216, 71921001, and 71991474], the Key Research and Development Program of Guangdong [Grant 2019B020228001], the Science and Technology Program of Guangzhou, China [Grant 202002030129], The Fundamental Research Funds for the Central Universities and the Research Funds of Renmin University of China [Grant 22XNH161], and the Outstanding Graduate Student Innovation and Development Program of Sun Yat-Sen University [Grant 19lgyjs64]. Supplemental Material: The online appendix and video are available at https://doi.org/10.1287/ijoc.2022.1241. [ABSTRACT FROM AUTHOR]

We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of min sum set cover, several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the min sum ordering problem (MSOP), which generalizes all these problems using a cost and a weight function defined on subsets of a finite set. Assuming a polynomial time α-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time 4 α -approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results. Summary of Contribution: This paper provides a general framework for min sum ordering problems. Within the realm of theoretical computer science, these problems include min sum set cover and its generalizations, as well as problems in Boolean function evaluation. On the operations research side, they include problems in search theory and scheduling. We present and analyze a very general algorithm for these problems, unifying several previous results on various min sum ordering problems and resulting in new constant factor guarantees for others. [ABSTRACT FROM AUTHOR]

We discuss the method recently proposed by S. Chubanov [Chubanov S (2012a) A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(3):533–570] for the linear feasibility problem. We present new, concise proofs and geometric interpretations of some of his results. From our ideas we derive the first strongly polynomial time algorithm based on relaxation method techniques for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos for combinatorial linear programs. The paper ends with some experimental investigations. [ABSTRACT FROM AUTHOR]

We study the design of large-scale group testing schemes under a heterogeneous population (i.e., subjects with potentially different risk) and with the availability of multiple tests. The objective is to classify the population as positive or negative for a given binary characteristic (e.g., the presence of an infectious disease) as efficiently and accurately as possible. Our approach examines components often neglected in the literature, such as the dependence of testing cost on the group size and the possibility of no testing, which are especially relevant within a heterogeneous setting. By developing key structural properties of the resulting optimization problem, we are able to reduce it to a network flow problem under a specific, yet not too restrictive, objective function. We then provide results that facilitate the construction of the resulting graph and finally provide a polynomial time algorithm. Our case study, on the screening of HIV in the United States, demonstrates the substantial benefits of the proposed approach over conventional screening methods. Summary of Contribution: This paper studies the problem of testing heterogeneous populations in groups in order to reduce costs and hence allow for the use of more efficient tests for high-risk groups. The resulting problem is a difficult combinatorial optimization problem that is NP-complete under a general objective. Using structural properties specific to our objective function, we show that the problem can be cast as a network flow problem and provide a polynomial time algorithm. [ABSTRACT FROM AUTHOR]

Computing and minimizing the worst-case bound on the expected shortfall risk of a portfolio given partial information on the distribution of the asset returns is an important problem in risk management. One such bound that been proposed is for the worst-case distribution that is "close" to a reference distribution where closeness in distance among distributions is measured using φ -divergence. In this paper, we advocate the use of such ambiguity sets with a tree structure on the univariate and bivariate marginal distributions. Such an approach has attractive modeling and computational properties. From a modeling perspective, this provides flexibility for risk management applications where there are many more choices for bivariate copulas in comparison with multivariate copulas. Bivariate copulas form the basis of the nested tree structure that is found in vine copulas. Because estimating a vine copula is fairly challenging, our approach provides robust bounds that are valid for the tree structure that is obtained by truncating the vine copula at the top level. The model also provides flexibility in tackling instances when the lower dimensional marginal information is inconsistent that might arise when multiple experts provide information. From a computational perspective, under the assumption of a tree structure on the bivariate marginals, we show that the worst-case expected shortfall is computable in polynomial time in the input size when the distributions are discrete. The corresponding distributionally robust portfolio optimization problem is also solvable in polynomial time. In contrast, under the assumption of independence, the expected shortfall is shown to be #P-hard to compute for discrete distributions. We provide numerical examples with simulated and real data to illustrate the quality of the worst-case bounds in risk management and portfolio optimization and compare it with alternate probabilistic models such as vine copulas and Markov tree distributions. [ABSTRACT FROM AUTHOR]

In this paper, we address two models of nondeterministic discrete time finite-horizon dynamic programs (DPs): implicit stochastic DPs (the information about the random events is given by value oracles to their cumulative distribution functions) and sample-based DPs (the information about the random events is deduced by drawing random samples). Such data-driven models frequently appear in practice, where the cumulative distribution functions of the underlying random variables are either unavailable or too complicated to work with. In both models, the single-period cost functions are accessed via value oracle calls and assumed to possess either monotone or convex structure. We develop the first near-optimal relative approximation schemes for each of the two models. Applications in stochastic inventory control (that is, several variants of the so-called newsvendor problem) are discussed in detail. Our results are achieved by a combination of Bellman equation calculations, density estimation results, and extensions of the technique of K-approximation sets and functions introduced by Halman et al. (2009) [Halman N, Klabjan D, Mostagir M, Orlin J, Simchi-Levi D (2009) A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Math. Oper. Res. 34(3):674–685.]. [ABSTRACT FROM AUTHOR]

We study an integrated production and transportation problem for a make-to-order manufacturing company that operates under the commit-to-delivery mode and uses third-party logistics service providers to deliver products to customers on or before certain committed delivery dates. Such third-party logistics service providers often provide various shipping modes with quantity discounts and different guaranteed shipping times. As a result, the company's shipping costs need to be represented by general shipping cost functions that are typically nondecreasing, subadditive, and piecewise linear with shipping quantities, and nonincreasing with guaranteed shipping times. To the best of our knowledge, this paper is the first attempt to solve such an integrated production and transportation problem for the commit-to-delivery mode with general shipping costs. We prove that with general shipping costs, the problem is strongly N P -hard when the planning horizon consists of an arbitrary number of days. For the two-day problem, we show that it is ordinarily N P -hard, but is unlikely to have a fully polynomial time approximation scheme (FPTAS) unless N P = P. Interestingly, we find that when the unit inventory holding cost is relatively small, which is often true in practice, there exists an FPTAS for the two-day problem, the development of which hinges on a newly discovered property for minimizing the sum of two general piecewise linear functions. For the multiday problem, we develop a heuristic algorithm based on column generation, which novelly uses a dynamic program for a variant of the problem with a single customer. Results from computational experiments demonstrate that the heuristic algorithm can find near-optimal solutions with optimality gaps less than 1% in a short running time. [ABSTRACT FROM AUTHOR]

We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition (SLC) is satisfied. A practical algorithm based on this potential function is implemented in a software package named . The implementation in maintains global linear and polynomial time convergence properties, while achieving practical performance. It either successfully solves the problem, or concludes that the SLC is not satisfied. When compared with the mature software package (barrier solver version ), solves convex quadratic programming problems, convex quadratically constrained quadratic programming problems, and general convex programming problems in fewer iterations. Moreover, several problems for which fails are solved to optimality. We also find that detects infeasibility more reliably than the general nonlinear solvers (version ) and (version ). [ABSTRACT FROM AUTHOR]

Access control mechanisms in software systems administer user privileges by granting users permission to perform certain operations while denying unauthorized access to others. Such mechanisms are essential to ensure that important business functions in an organization are conducted securely and smoothly. Currently, the dominant access control approach in most major software systems is role-based access control. In this approach, permissions are first assigned to roles, and users acquire permissions by becoming members of certain roles. However, given the dynamic nature of organizations, a fixed set of roles usually cannot meet the demands that users (existing or new) have to conduct business. The typical response to this problem is to myopically create new roles to meet immediate demand that cannot be satisfied by an existing set of roles. This ad hoc creation of roles invariably leads to a proliferation in the number of roles with the accompanying administrative overhead. Based on discussions with practitioners, we propose a role refinement scheme that reconstructs a system of roles to reduce the cost of role management. We first show that the role-refinement problem is strongly NP-hard and then provide two polynomial-time approximation algorithms (a greedy algorithm and a randomized rounding algorithm) and establish their performance guarantees. Finally, numerical experiments--based on a real data set from a firm's enterprise resource planning system--are conducted to demonstrate the applicability and performance of our refinement scheme. [ABSTRACT FROM AUTHOR]

We consider the stochastic obstacle scene problem wherein an agent needs to traverse a spatial arrangement of possible obstacles, and the status of the obstacles may be disambiguated en route at a cost. The goal is to find an algorithm that decides what and where to disambiguate en route so that the expected length of the traversal is minimized. We present a polynomial-time method for a graph-theoretical version of the problem when the associated graph is restricted to parallel avenues with fixed policies within the avenues. We show how previously proposed algorithms for the continuous space version can be adapted to a discrete setting. We propose a generalized framework encompassing these algorithms that uses penalty functions to guide the navigation in real time. Within this framework, we introduce a new algorithm that provides near-optimal results within very short execution times. Our algorithms are illustrated via computational experiments involving synthetic data as well as an actual naval minefield data set. [ABSTRACT FROM AUTHOR]