Special Topics

Discrete optimization

Default Latest Most Read

Please wait a minute... For Selected: Download Citations EndNote Ris BibTeX Toggle Thumbnails Select The Adjacency and Signless Laplacian Spectra of Cored Hypergraphs and Power Hypergraphs Jun-Jie Yue · Li-Ping Zhang· Mei Lu· Li-Qun Qi Journal of the Operations Research Society of China    2017, 5 (1): 27-.   DOI: 10.1007/s40305-016-0141-3 Abstract （10075）      PDF       Knowledge map    Save In this paper, we study the adjacency and signless Laplacian tensors of cored hypergraphs and power hypergraphs. We investigate the properties of their adjacency and signlessLaplacian H-eigenvalues.Especially,wefind out the largest H-eigenvalues of adjacency and signless Laplacian tensors for uniform squids. We also compute the H-spectra of sunflowers and some numerical results are reported for the H-spectra. Related Articles | Metrics | Comments（0） Cited: Baidu(2) Select COVID-19 Pandemic with Human Mobility Across Countries Cheng Zhang, Li-Xian Qian, Jian-Qiang Hu Journal of the Operations Research Society of China    2021, 9 (2): 229-244.   DOI: 10.1007/s40305-020-00317-6 Abstract （2841）      PDF       Knowledge map    Save This study develops a holistic view of the novel coronavirus(COVID-19) spread worldwide through a spatial–temporal model with network dynamics. By using a unique human mobility dataset containing 547 166 flights with a total capacity of 101 455 913 passengers from January 22 to April 24, 2020, we analyze the epidemic correlations across 22 countries in six continents and particularly the changes in such correlations before and after implementing the international travel restriction policies targeting different countries. Results show that policymakers should move away from the previous practices that focus only on restricting hotspot areas with high infection rates. Instead, they should develop a new holistic view of global human mobility to impose the international movement restriction. The study further highlights potential correlations between international human mobility and focal countries’ epidemic situations in the global network of COVID-19 pandemic. Reference | Related Articles | Metrics | Comments（0） Select Disruption Recovery at Airports: Ground Holding, Curfew Restrictions and an Approximation Algorithm Prabhu Manyem Journal of the Operations Research Society of China    2021, 9 (4): 819-852.   DOI: 10.1007/s40305-020-00338-1 Abstract （2736）      PDF       Knowledge map    Save We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground holding, or they cause the flights to violate airport curfew hours. We consider curfew and arrival capacities applicable at a single airport. After proving that the problem is NP-hard, we present a polynomial time approximation algorithm based on the primal–dual schema and show that if the problem is feasible, the algorithm finds a feasible solution that is both within a certain additive bound and within a certain multiplicative factor of the optimal solution. The algorithm returns a solution mix of which flights suffer no delay, which ones to be ground-held and which ones may violate the curfew (and hence pay a curfew penalty). Computational results are positive; our heuristic outperforms the integer programming solver by a wide margin. Reference | Related Articles | Metrics | Comments（0） Select A Novel MILP Model for N-vehicle Exploration Problem Guo-Jun Zhang, Jin-Chuan Cui Journal of the Operations Research Society of China    2021, 9 (2): 359-373.   DOI: 10.1007/s40305-019-00289-2 Abstract （2685）      PDF       Knowledge map    Save The N-vehicle exploration problem (NVEP) is a nonlinear discrete scheduling problem, and the complexity status remains open. To our knowledge, there is no literature until now employing mixed integer linear programming (MILP) technology to solve this problem except for Wang (J Oper Res Soc China 3(4):489–498, 2015). However, they did not give numerical experiments since their model existed strictly inequalities and the number of constraints was up to O(n3), which was inefficient to solve practical problems. This paper establishes a more concise MILP model, where the number of constraints is just O(n2). Therefore, the existing efficient MILP algorithms can be used to solve NVEP. Secondly, we provide some properties of N-vehicle problem and give three methods for cutting plane construction, which can increase the solving speed significantly. Finally, a numerical experiment is provided to verify the effectiveness and robustness for different instances and scales of acceleration techniques. Reference | Related Articles | Metrics | Comments（0） Select Linear Arboricity of Outer-1-Planar Graphs Xin Zhang, Bi Li Journal of the Operations Research Society of China    2021, 9 (1): 181-193.   DOI: 10.1007/s40305-019-00243-2 Abstract （1979）      PDF       Knowledge map    Save A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once. Zhang et al. (Edge covering pseudoouterplanar graphs with forests, Discrete Math 312:2788-2799, 2012; MR2945171) proved that the linear arboricity of every outer-1-planar graph with maximum degree △ is exactly 「△/2」 provided that △ = 3 or △ ≥ 5 and claimed that there are outer-1-planar graphs with maximum degree △ = 4 and linear arboricity 「(△ + 1)/2」 = 3. It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2, and moreover, none of the above constraints on the crossing distance and crossing width can be removed. Besides, a polynomial-time algorithm for constructing a path-2-coloring (i.e., an edge 2-coloring such that each color class induces a linear forest, a disjoint union of paths) of such an outer-1-planar drawing is given. Reference | Related Articles | Metrics | Comments（0） Select Sufficient Conditions for Maximally Edge-Connected Hypergraphs Lin-Ken Tong, Er-Fang Shan Journal of the Operations Research Society of China    2021, 9 (1): 119-129.   DOI: 10.1007/s40305-018-0224-4 Abstract （1884）      PDF       Knowledge map    Save The edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected. A graph or hypergraph is called maximally edge-connected if the edge-connectivity equals its minimum degree. In this paper, we show that some classical sufficient conditions for graphs to be maximally edge-connected can be generalized to hypergraphs. Reference | Related Articles | Metrics | Comments（0） Select The Continuous Knapsack Problem with Capacities Huynh Duc Quoc, Nguyen Chi Tam, Tran Hoai Ngoc Nhan Journal of the Operations Research Society of China    2021, 9 (3): 713-721.   DOI: 10.1007/s40305-020-00298-6 Abstract （1861）      PDF       Knowledge map    Save We address a variant of the continuous knapsack problem, where capacities regarding costs of items are given into account. We prove that the problem is NP-complete although the classical continuous knapsack problem is solvable in linear time. For the case that there exists exactly one capacity for all items, we solve the corresponding problem in O(n log n) time, where n is the number of items. Reference | Related Articles | Metrics | Comments（0） Select On the Stable Gani-Type Attainability Problem Controlled by Promotion at Maximum Entropy Virtue Uwabomwen Ekhosuehi Journal of the Operations Research Society of China    2021, 9 (3): 673-690.   DOI: 10.1007/s40305-020-00301-0 Abstract （1803）      PDF       Knowledge map    Save This study considers the attainability problem in one-step for the stable Gani-type model controlled by promotion within the context of maximum entropy. The technique adopted involves formulating the attainability problem as a constrained optimisation problem wherein the objective is to maximise the Shannon entropy rate subject to certain constraints imposed by the attainable configuration and the sub-stochastic transition matrix. The principle of maximum entropy is used to obtain results that are consistent with the exponential representation of transition probabilities for manpower systems. Reference | Related Articles | Metrics | Comments（0） Select Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi Journal of the Operations Research Society of China    2021, 9 (1): 99-117.   DOI: 10.1007/s40305-018-0229-z Abstract （1776）      PDF       Knowledge map    Save This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network. We call this problem as the integer inverse undesirable p-median location model. Exact combinatorial algorithms with $\mathcal{O}({p^2}\;n\;\log \;n)$ and $\mathcal{O}({p^2}(n\;\log \;n + n\;\log \;\eta {}_{\max }))$ running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms, respectively. Furthermore, it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in $\mathcal{O}({p^2}\;n\;\log \;n)$ time. Reference | Related Articles | Metrics | Comments（0） Select Stable Matchings in the Marriage Model with Indifferences Noelia Juarez, Jorge Oviedo Journal of the Operations Research Society of China    2021, 9 (3): 593-617.   DOI: 10.1007/s40305-020-00315-8 Abstract （1713）      PDF       Knowledge map    Save For the marriage model with indifferences, we define an equivalence relation over the stable matching set. We identify a sufficient condition, the closing property, under which we can extend results of the classical model (without indifferences) to the equivalence classes of the stable matching set. This condition allows us to extend the lattice structure over classes of equivalences and the rural hospital theorem. Reference | Related Articles | Metrics | Comments（0） Select Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs Jing Jin, Bao-Gang Xu Journal of the Operations Research Society of China    2020, 8 (1): 105-116.   DOI: 10.1007/s40305-018-0214-6 Abstract （1472）      PDF       Knowledge map    Save Suppose that G is a planar cubic graph with χi(G)> 5. We show that if χi(H) <χi(G) for each planar cubic graph H of order less than G, then G is either a 3-connected simple planar cubic graph, or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings. This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected. Reference | Related Articles | Metrics | Comments（0） Select A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem Lu Han · Da-Chuan Xu · Dong-Lei Du·Chen-Chen Wu Journal of the Operations Research Society of China    2017, 5 (2): 219-.   DOI: 10.1007/s40305-017-0164-4 Abstract （1470）      PDF       Knowledge map    Save In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph G = (V, E) and a set of vertex sets V = {V1, V2, · · · , Vl }. Every edge in E has a nonnegative cost, and every vertex set in V has a nonnegative penalty cost. For a given edge set F ⊆ E, vertex set Vi ∈ V is said to be connected by edge set F if Vi is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method. Related Articles | Metrics | Comments（0） Select A Gradient Descent Method for Estimating the Markov Chain Choice Model Lei Fu, Dong-Dong Ge Journal of the Operations Research Society of China    2023, 11 (2): 371-381.   DOI: 10.1007/s40305-021-00365-6 Abstract （1456）      PDF       Knowledge map    Save In this paper, we propose a gradient descent method to estimate the parameters in a Markov chain choice model. Particularly, we derive closed-form formula for the gradient of the log-likelihood function and show the convergence of the algorithm. Numerical experiments verify the efficiency of our approach by comparing with the expectation-maximization algorithm. We show that the similar result can be extended to a more general case that one does not have observation of the no-purchase data. Reference | Related Articles | Metrics | Comments（0） Select Approximation Algorithms for Vertex Happiness Yao Xu, Yong Chen, Peng Zhang, Randy Goebel Journal of the Operations Research Society of China    2019, 7 (3): 429-448.   DOI: 10.1007/s40305-019-00260-1 Abstract （1447）      PDF       Knowledge map    Save We investigate the maximum happy vertices (MHV) problem and its complement, the minimum unhappy vertices (MUHV) problem. In order to design better approximation algorithms, we introduce the supermodular and submodular multi-labeling (Sup-ML and Sub-ML) problems and show that MHV and MUHV are special cases of Sup-ML and Sub-ML, respectively, by rewriting the objective functions as set functions. The convex relaxation on the Lovász extension, originally presented for the submodular multi-partitioningproblem,canbeextendedfortheSub-MLproblem,therebyproving that Sub-ML (Sup-ML, respectively) can be approximated within a factor of 2-2/k (2/k, respectively), where k is the number of labels. These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k, respectively, using the same approximation algorithms. For the MUHV problem, we also show that it is approximation-equivalent to the hypergraph multiway cut problem; thus, MUHV is Unique Games-hard to achieve a (2-2/k-ε)-approximation, for any ε > 0. For the MHV problem, the 2/k-approximation improves the previous best approximation ratio max{1/k, 1/Δ + 1/g(Δ) }, where Δ is the maximum vertex degree of the input graph and g(Δ)=(√Δ+√Δ+1)2 Δ > 4Δ2. We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovász extension for Sup-ML; we then prove an upper bound of 2/k on the integrality gap of this LP relaxation, which suggests that the 2/k-approximation is the best possible based on this LP relaxation. Lastly, we prove that it is Unique Games-hard to approximate the MHV problem within a factor of Ω(log2 k/k). Reference | Related Articles | Metrics | Comments（0） Select Conditional Edge Connectivity of the Locally Twisted Cubes Hui Shang, Eminjan Sabir, Ji-Xiang Meng Journal of the Operations Research Society of China    2019, 7 (3): 501-509.   DOI: 10.1007/s40305-019-00259-8 Abstract （1407）      PDF       Knowledge map    Save The k-component edge connectivity cλk(G) of a non-complete graph G is the minimum number of edges whose deletion results in a graph with at least k components. In this paper, we extend some results by Guo et al. (Appl Math Comput 334:401-406, 2018) by determining the component edge connectivity of the locally twisted cubes LTQn, i.e., cλk+1(LTQn)=kn -exk/2 for 1 ≤ k ≤ 2[n/2], n ≥ 7, where exk=∑i=0s ti2ti +∑i=0s 2·i·2ti, and k is a positive integer with decomposition k=∑i=0s 2ti such that t0=⎣log2k⎦ and ti=⎣log2(k -∑r=0i-12tr)⎦ for i ≥ 1. As a by-product, we characterize the corresponding optimal solutions. Reference | Related Articles | Metrics | Comments（0） Select The Myerson Value on Local Structures of Coalitions Daniel Li Li, Er-Fang Shan Journal of the Operations Research Society of China    2019, 7 (3): 461-473.   DOI: 10.1007/s40305-019-00254-z Abstract （1362）      PDF       Knowledge map    Save The Myerson value introduced by Mayerson (Math Oper Res 2:225-229, 1977) is a solution for cooperative games under the partial cooperation structures described by graphs, in which feasible coalitions are connected but their structures are ignored. To extend the Myerson value, we define a mapping to describe local structures of coalitions and obtain a new solution for cooperative games, called Myerson value with local structures. We propose an axiomatic characterization of the Myerson value associated with local cooperative structures. Reference | Related Articles | Metrics | Comments（0） Select Combinatorial Algorithms for Reverse Selective Undesirable Center Location Problems on Cycle Graphs Roghayeh Etemad · Behrooz Alizadeh Journal of the Operations Research Society of China    2017, 5 (3): 347-361.   DOI: 10.1007/s40305-016-0144-0 Abstract （1182）      PDF       Knowledge map    Save This paper deals with a general variant of the reverse undesirable (obnoxious) center location problem on cycle graphs. Given a ‘selective’ subset of the vertices of the underlying cycle graph as location of the existing customers, the task is to modify the edge lengths within a given budget such that the minimum of distances between a predetermined undesirable facility location and the customer points is maximized under the perturbed edge lengths. We develop a combinatorial O(n log n) algorithm for the problem with continuous modifications. For the uniform-cost model, we solve this problem in linear time by an improved algorithm. Furthermore, exact solution methods are proposed for the problem with integer modifications. Related Articles | Metrics | Comments（0） Select Minimizing Ratio of Monotone Non-submodular Functions Yi-Jing Wang, Da-Chuan Xu, Yan-Jun Jiang, Dong-Mei Zhang Journal of the Operations Research Society of China    2019, 7 (3): 449-459.   DOI: 10.1007/s40305-019-00244-1 Abstract （1182）      PDF       Knowledge map    Save In this paper, we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g. We take advantage of the greedy technique and get a performance guarantee depending on the generalized curvature and inverse generalized curvature of f, as well as the submodularity ratio of g. Our results generalize the works of Bai et al. (Algorithms for optimizing the ratio of submodular functions. In:Proceedings of the 33rd International Conference on Machine Learning, 2016) and Qian et al. (Optimizing ratio of monotone set functions. In:Proceedings of the 26th International Joint Conference on Artificial Intelligence, 2017). Reference | Related Articles | Metrics | Comments（0） Select Compromising Solution of Geometric Programming Problem with Bounded Parameters Mrinal Jana · Geetanjali Panda Journal of the Operations Research Society of China    2017, 5 (3): 377-390.   DOI: 10.1007/s40305-016-0145-z Abstract （1138）      PDF       Knowledge map    Save This paper addresses a geometric programming problem, where the objective function and constraints are interval-valued functions. The concept of acceptable feasible region is introduced, and a methodology is developed to transform this model to a general optimization problem, which is free from interval uncertainty. Relationship between the solution of the original problem and the transformed problem is established. The methodology is illustrated through numerical examples. Solutions by the proposed method and previous methods are analyzed. Related Articles | Metrics | Comments（0） Select Competitive and Collaborative Influence in Social Networks Qi Qi, Wen-Wei Wang, Ling-Fei Yu Journal of the Operations Research Society of China    2019, 7 (1): 169-182.   DOI: 10.1007/s40305-018-00237-6 Abstract （1082）      PDF       Knowledge map    Save We consider revenue maximization in viral marketing of competitive and collaborative products through social networks, focusing on the word-of-mouth effect on personal decisions in adopting products, technologies, or Internet applications. In our model, each advertiser submits its value per consumer, and its total budget. The publisher pays a selected set of users on social networks as seed nodes. It demands a payment (equal to its value) from an advertiser for each influenced node in social networks. The publisher's revenue equals to the total payment from the influenced users minus its cost of seed nodes.In this paper,we study the efficient allocation problem of the publisherto maximize its revenue. Our work is motivated by recent extensive studies on influence models for social networks. It has been noted that the promoted products could either be competitive or complementary such as Kindle versus Nook e-reader or Kindle cover with Kindle, respectively. Our models evaluate the revenue/cost effect of marketing those types of products through a social network, focusing on the issues of revenue maximization and complementary and competitive effects of products on each other. We take the algorithmic complexity approach for revenue maximization under those models and prove NP-hardness, non-approximability results for general structures, and polynomial time algorithms and applications for special classes of networks. Reference | Related Articles | Metrics | Comments（0）

page Page 1 of 3 Total 44 records First page Prev page Next page Last page