Search

In edge computing, the edge node can provide certain accessible storage and computing resources for the surrounding users. Caching data on the edge node can quickly retrieve the required data and complete the user's requests with low delay. However, the resources of edge servers are limited and sometimes have to gain the data by transfering from other servers or buying from data centers at the cloud. Traditionally, data center is just regard as a place of purchasing data, and the data is always available for the buyer after purchase. However, we believe that these data have a validity period. After the buyer purchases the data, it only provides limited calls for free. Based on this assumption, in this paper, we study the data caching problem in the edge-cloud collaborative system to minimize the total cost. Without knowing the information of users' future request flow, we propose an online algorithm. What's more, the asymptotic competition ratio of the algorithm in the worst case is 3. [ABSTRACT FROM AUTHOR]

In this paper, we define a new flavour of well-composedness, called strong Euler well-composedness. In the general setting of regular cell complexes, a regular cell complex of dimension n is strongly Euler well-composed if the Euler characteristic of the link of each boundary cell is 1, which is the Euler characteristic of an (n - 1) -dimensional ball. Working in the particular setting of cubical complexes canonically associated with n D pictures, we formally prove in this paper that strong Euler well-composedness implies digital well-composedness in any dimension n ≥ 2 and that the converse is not true when n ≥ 4 . [ABSTRACT FROM AUTHOR]

This paper provides a theoretical characterization of monotonically connected image surface regions, called slope regions. The characterization is given by several topological properties described in terms of critical points relative to the region. We formally prove the necessary and sufficient conditions that a region needs to satisfy to be a slope region. We also provide a prototype of slope regions which is general and contains, as particular cases, the prototypes studied and published in previous conference papers. [ABSTRACT FROM AUTHOR]

The topic of this paper includes graph cuts based computed tomography reconstruction methods in binary and multi-gray level cases. This approach combines the graph cuts and a gradient based method. The present paper introduces and analyses the shape circularity as a new regularization and incorporates it in a graph cuts based computed tomography reconstruction approach, thus introducing a new energy-minimization based reconstruction algorithm for binary tomography. Proposed method is capable for reconstructions in cases of limited projection view availability. Results of experimental evaluation of the considered graph cuts type reconstruction methods for both binary and multi-level tomography are presented. [ABSTRACT FROM AUTHOR]

Sorting is studied in this paper as an archetypal example to explore the optimizing power of consensus. In conceptualizing the consensus sort, the classical hill-climbing method of optimization is paired with the modern notion that value and fitness can be judged by data mining. Consensus sorting is a randomized sorting algorithm which is based on randomly selecting pairs of elements within an unsorted list (expressed in this paper as a permutation), and deciding whether to swap them based on appeals to a database of other permutations. The permutations in the database are all scored via some adaptive sorting metric, and the decision to swap depends on whether the database consensus suggests a better score as a result of swapping. This uninformed search process does not require the definition of the concept of sorting, but rather depends on selecting a metric which does a good job of distinguishing a good path to the goal, a sorted list. A previous paper has shown that the ability of the algorithm to converge on the goal depends strongly on the metric which is used, and analyzed the performance of the algorithm when number of inversions was used as a metric. This paper continues by analyzing the performance of a much more efficient metric, the number of cycles in the permutation. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum power partial cover problem (MinPPC). Suppose X is a set of points and S is a set of sensors on the plane, each sensor can adjust its power and the covering range of a sensor s with power p(s) is a disk of radius r(s) satisfying p (s) = c · r (s) α . Given an integer k ≤ | X | , the MinPPC problem is to determine the power assignment on every sensor such that at least k points are covered and the total power consumption is the minimum. We present a primal-dual algorithm for MinPPC with approximation ratio at most 3 α . This ratio coincides with the best known ratio for the minimum power full cover problem, and improves previous ratio (12 + ε) for MinPPC which was obtained only for α = 2 . [ABSTRACT FROM AUTHOR]

This paper studies the accurate prediction of the trajectory of aircraft that is in low-lever emergency medical rescue so as to achieve effective and safe real-time scheduling. The paper acquires real-time flight state (position, speed and heading) by taking advantage of the information derived from Automatic Dependence Surveillance-broadcasting and improved A∗ algorithm. Then Interacting Multiple Model is introduced to predict the flight state and model of the aircraft at next point-in-time based on the current state information. Then combining the result and flight plan information together, short-term flight intent is inferred. Integrated with Interacting Multiple Model algorithm and improved Intent Inference algorithm, a trajectory prediction algorithm is put forward based on the flight state and intent inference, and finally a real time scheduling plan is coming into being. Case simulation shows the result of this algorithm is more accurate than using intent inference algorithm alone. It helps to guarantee the safety of the medical rescue aircraft and improve the efficiency of the emergency rescue. [ABSTRACT FROM AUTHOR]

In this paper, we define a new domination-like invariant of graphs. Let R + be the set of non-negative numbers. Let c ∈ R + - { 0 } be a number, and let G be a graph. A function f : V (G) → R + is a c-self-dominating function of G if for every u ∈ V (G) , f (u) ≥ c or max { f (v) : v ∈ N G (u) } ≥ 1 . The c-self-domination number γ c (G) of G is defined as γ c (G) : = min { ∑ u ∈ V (G) f (u) : f is a c-self-dominating function of G } . Then γ 1 (G) , γ ∞ (G) and γ 1 2 (G) are equal to the domination number, the total domination number and the half of the Roman domination number of G, respectively. Our main aim is to continuously fill in the gaps among such three invariants. In this paper, we give a sharp upper bound of the c-self-domination number for all c ≥ 1 2 . [ABSTRACT FROM AUTHOR]

This paper introduces a new environment of online scheduling in which jobs are scheduled under the non-delayed processing (NDP) constraint, where NDP means that the available jobs cannot be delayed for processing when some machine is idle. We study in this paper the single-machine online scheduling to minimize the maximum weighted completion time ( WC max ) or the maximum delivery completion time ( L max ) under the NDP constraint. For the first problem, we establish a lower bound 2 and provide an online algorithm which has a competitive ratio of (3 + 5) / 2 ≈ 2.618 . We present a 3/2-competitive best possible online algorithm for the second problem. [ABSTRACT FROM AUTHOR]

A (k , g) -graph is a k-regular graph of girth g . Given k ≥ 2 and g ≥ 3 , (k , g) -graphs of infinitely many orders are known to exist and the problem of finding a (k, g)-graph of the smallest possible order is known as the Cage Problem. The aim of our paper is to develop systematic (programmable) ways for lowering the orders of existing (k , g) -graphs, while preserving their regularity and girth. Such methods, in analogy with the previously used excision, may have the potential for constructing smaller (k, g)-graphs from current smallest examples—record holders—some of which have not been improved in years. In addition, we consider constructions that preserve the regularity, the girth and the order of the considered graphs, but alter the graphs enough to possibly make them suitable for the application of our order decreasing methods. We include a detailed discussion of several specific parameter cases for which several non-isomorphic smallest examples are known to exist, and address the question of the distance between these non-isomorphic examples based on the number of changes required to move from one example to another. [ABSTRACT FROM AUTHOR]

Min–max spanning tree problem is a classical problem in combinatorial optimization. Its purpose is to find a spanning tree to minimize its maximum edge in a given edge weighted graph. Given a connected graph G, an edge weight vector w and a forest F, the partial inverse min–max spanning tree problem (PIMMST) is to find a new weighted vector w ∗ , so that F can be extended into a min–max spanning tree with respect to w ∗ and the gap between w and w ∗ is minimized. In this paper, we research PIMMST under the weighted bottleneck Hamming distance. Firstly, we study PIMMST with value of optimal tree restriction, a variant of PIMMST, and show that this problem can be solved in strongly polynomial time. Then, by characterizing the properties of the value of optimal tree, we present first algorithm for PIMMST under the weighted bottleneck Hamming distance with running time O (| E | 2 log | E |) , where E is the edge set of G. Finally, by giving a necessary and sufficient condition to determine the feasible solution of this problem, we present a better algorithm for this problem with running time O (| E | log | E |) . Moreover, we show that these algorithms can be generalized to solve these problems with capacitated constraint. [ABSTRACT FROM AUTHOR]

In recent years, a dynamic coloring, named as zero forcing, of the vertices in a graph have attracted many researchers. For a given G and a vertex subset S, assigning each vertex of S black and each vertex of V \ S no color, if one vertex u ∈ S has a unique neighbor v in V \ S , then u forces v to color black. S is called a zero forcing set if S can be expanded to the entire vertex set V by repeating the above forcing process. S is regarded as a total forcing set if the subgraph G[S] satisfies δ (G [ S ]) ≥ 1 . The minimum cardinality of a total forcing set in G, denoted by F t (G) , is named the total forcing number of G. For a graph G, p(G), q(G) and ϕ (G) denote the number of pendant vertices, the number of vertices with degree at least 3 meanwhile having one pendant path and the cyclomatic number of G, respectively. In the paper, by means of the total forcing set of a spanning tree regarding a graph G, we verify that F t (G) ≤ p (G) + q (G) + 2 ϕ (G) . Furthermore, all graphs achieving the equality are determined. [ABSTRACT FROM AUTHOR]

The dominated coloring (dom-coloring) of a graph G is a proper coloring such that each color class is dominated by at least one vertex. The dominated chromatic number (dom-chromatic number) of G is the minimum number of color classes among all dominated colorings of G, denoted by χ dom (G) . In this paper, we study the dominated coloring of Cartesian product, direct product, lexicographic product and strong product of some graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study the optional preference model for the facility location game with two heterogeneous facilities on a line interval [0, 1], by further enforcing the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Each agent has one of three favorable preferences towards the two facilities, i.e., facility 1, facility 2, or optional preference. Here, we consider two variants of the optional preference model: Min (caring for the closer one) and Max (caring for the further one). In both variants, each agent wishes to get close to his preferred facilities, and thus his cost is his distance to his preferred facility. In this game, we consider agents' locations as public information and agents' preferences as private information which needs to be reported by agents. The objective is to design a mechanism for the two facilities' locations such as to minimize the maximum cost of agents (MinMax) and achieve truthful report of agents' preferences. Given any value of d, for both variants, we propose a strategyproof mechanism with an approximation ratio of 2. We also establish lower bounds of any deterministic strategyproof mechanism for both variants and show that the gaps between the lower bounds and the upper bounds are relatively small. [ABSTRACT FROM AUTHOR]

A graph G is called (H 1 , H 2) -free if G contains no induced subgraph isomorphic to H 1 or H 2 . Let P k be a path with k vertices and C s , t , k ( s ≤ t ) be a graph consisting of two intersecting complete graphs K s + k and K t + k with exactly k common vertices. In this paper, using an iterative method, we prove that the class of (P 5 , C s , t , k) -free graphs with clique number ω has a polynomial χ -binding function f (ω) = c (s , t , k) ω max { s , k } . In particular, we give two improved chromatic bounds: every (P 5 , b u t t e r f l y) -free graph G has χ (G) ≤ 3 2 ω (G) (ω (G) - 1) ; every (P 5 , C 1 , 3) -free graph G has χ (G) ≤ 9 ω (G) . [ABSTRACT FROM AUTHOR]

In this paper, we consider four semi-online early work maximization problems on two hierarchical uniform machines M 1 and M 2 , where machine M 1 with speed s > 0 is available for all jobs and machine M 2 with speed 1 is only available for high-hierarchy jobs. When the total size of all jobs is known, we design an optimal online algorithm with a competitive ratio of min { 1 + s , 2 + 2 s 1 + 2 s } . When the total size of low-hierarchy jobs is known, we design an optimal online algorithm with a competitive ratio of min { 1 + s , 9 s 2 + 10 s + 1 - s - 1 2 s } . When the total size of high-hierarchy jobs is known, we design an optimal online algorithm with a competitive ratio of min { s + 1 , s 2 + 2 s + 2 - s } . When both the total sizes of low-hierarchy and high-hierarchy jobs are known, we give a lower bound 2 s + 2 s + 2 for the case s ≤ 2 3 , and an optimal online algorithm with a competitive ratio of 3 s + 3 3 s + 2 for the case s > 2 3 . [ABSTRACT FROM AUTHOR]

Ordering polytopes have been instrumental to the study of combinatorial optimization problems arising in a variety of fields including comparative probability, computational social choice, and group decision-making. The weak order polytope is defined as the convex hull of the characteristic vectors of all binary orders on n alternatives that are reflexive, transitive, and total. By and large, facet defining inequalities (FDIs) of this polytope have been obtained through simple enumeration and through connections with other combinatorial polytopes. This paper derives five new large classes of FDIs by utilizing the equivalent representations of a weak order as a ranking of n alternatives that allows ties; this connection simplifies the construction of valid inequalities, and it enables groupings of characteristic vectors into useful structures. We demonstrate that a number of FDIs previously obtained through enumeration are actually special cases of the large classes. This work also introduces novel construction procedures for generating affinely independent members of the identified ranking structures. Additionally, it states two conjectures on how to derive many more large classes of FDIs using the featured techniques. [ABSTRACT FROM AUTHOR]

A complete forcing set of a graph G with a perfect matching is a subset of E(G) on which the restriction of each perfect matching M is a forcing set of M. The complete forcing number of G is the minimum cardinality of complete forcing sets of G. It was shown that a complete forcing set of G also antiforces each perfect matching. Previously, some closed formulas for the complete forcing numbers of some types of hexagonal systems including cata-condensed hexagonal systems and parallelograms have been derived. In this paper, we show that the subset of E(G) obtained from E(G) by deleting all edges that are incident with some vertices of a 2-independent set of G is a complete forcing set. As applications, we give some expressions for the complete forcing numbers of complete multipartite graphs, 2n-vertex graphs with minimum degree at least 2 n - 3 and 2n-vertex balanced bipartite graphs with minimum degree at least n - 2 , by showing that each sufficiently short cycle is a nice cycle. [ABSTRACT FROM AUTHOR]

Mantel’s theorem is a classical result in extremal graph theory which implies that the maximum number of edges of a triangle-free graph of order n. In 1970, Nosal obtained a spectral version of Mantel’s theorem which gave the maximum spectral radius of a triangle-free graph of order n. In this paper, the clique tensor of a graph G is proposed and the spectral Mantel’s theorem is extended via the clique tensor. Furthermore, a sharp upper bound of the number of cliques in G via the spectral radius of the clique tensor is obtained. These results imply that a result of Erdős (Magyar Tud Akad Mat Kutató Int Közl 7:459–464, 1962) under certain conditions. [ABSTRACT FROM AUTHOR]

For a purchase-to-order seller, there is no inventory and the seller has to purchase goods to fulfill orders already placed. For each purchase, there is a constant ordering cost. For each order, delay cost will be incurred if it is not fulfilled timely. Consequently, there is a tradeoff between the ordering cost and the delay cost for the seller to make replenishment decisions minimizing the total cost. In practice it is impossible or difficult for the seller to know demand information about future orders in advance, and thus this decision-making problem is of an online fashion. In the previous work, this online problem is classified into three cases according to capacity limit and demand quantity, and a 10-competitive online policy is proposed for the general case. In the present paper, an improved 4-competitive online policy is proposed. Besides, an asymptotic lower bound of 2 is derived for this online decision-making problem. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a transportation game first introduced by Fotakis, Gourvès, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, to achieve this goal, they have to choose one of the available buses. We introduce a sequential version of this game and provide bounds for the Sequential Price of Stability and the Sequential Price of Anarchy in both metric and non-metric instances, considering three social cost functions: the total traveled distance by all buses, the maximum distance traveled by a bus, and the sum of the distances traveled by all players (a new social cost function that we introduce). Finally, we analyze the Price of Stability and the Price of Anarchy for this new function in simultaneous transportation games. [ABSTRACT FROM AUTHOR]

An essential aspect of a closed-loop supply chain (CLSC) involves its optimization. In this context, systematizing the publications on optimization methods applied in CLSC constitutes this research's primary objective. In this sense, a comprehensive literature review was carried out on 354 papers published from January 2008 to October 2020 to find future directions involving CLSC optimization. It was found stochastic methods are the primary approach in the studies regarding CLSC optimization, being applied in 27.68% of the publications investigated, while hybrid methods appeared in 21.75%, and deterministic methods were used in 20.62%. It was verified that 49.71% of the publications were related exclusively to strategic decisions concerning organizational decision-making levels, 22.03% analyzed tactical decisions, and 13.56% studied operational aspects. Regarding the sustainability dimensions, it was found that only the economic dimension was investigated in 70.62% of the analyzed publications. The three dimensions (economic, environmental, and social) were investigated simultaneously in only 6.21% of the publications. As the main conclusion, a lack of research covering the whole spectrum of the CLSC environment was found, comprising the various levels of organization decisions and sustainability dimensions of the triple bottom line. [ABSTRACT FROM AUTHOR]

This paper proposes an online leasing problem considering both price fluctuations and the second-hand transaction. In the studied problem, the price of the required equipment is assumed to fluctuate over time and lie in a predetermined range [1, M]. Moreover, the price between two adjacent times is controlled within an acceptable range [1/α, α]. The equipment can be sold through second-hand transaction after its end of use. The selling price in the second-hand transaction is assumed to vary along with the price fluctuations. The aim of this paper is to find the best possible online leasing strategy which generates a minimal cost for using the equipment. We present an online leasing algorithm for solving this problem and prove it to be the optimal online algorithm. Computational experiments are conducted to evaluate the characteristics of the problem and the performance of the proposed online leasing algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the optimization of linearly constrained stochastic problem which only noisy measurements of the loss function are available. We propose a method which combines genetic algorithm (GA) with simultaneous perturbation stochastic approximation (SPSA) to solve linearly constrained stochastic problems. The hybrid method uses GA to search for optimum over the whole feasible region, and SPSA to search for optimum at local region. During the GA and SPSA search process, the hybrid method generates new solutions according to gradient projection direction, which is calculated based on active constraints. Because the gradient projection method projects the search direction into the subspace at a tangent to the active constraints, it ensures new solutions satisfy all constraints strictly. This paper applies the hybrid method to nine typical constrained optimization problems and the results coincide with the ideal solutions cited in the references. The numerical results reveal that the hybrid method is suitable for multimodal constrained stochastic optimization problem. Moreover, each solution generated by the hybrid method satisfies all linear constraints strictly. [ABSTRACT FROM AUTHOR]

This paper considers the bandwidth reduction problem for large-scale sparse matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix. Thus, the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. This manuscript proposes two heuristics for the bandwidth reduction of large-scale matrices. The first is a variant of the Fast Node Centroid Hill-Climbing algorithm, and the second is an algorithm based on the iterated local search metaheuristic. This paper then experimentally compares the solutions yielded by the new reordering algorithms with the bandwidth solutions delivered by state-of-the-art heuristics for the problem, including tests on large-scale problem matrices. A considerable number of results for a range of realistic test problems showed that the performance of the two new algorithms compared favorably with state-of-the-art heuristics for bandwidth reduction. Specifically, the variant of the Fast Node Centroid Hill-Climbing algorithm yielded the overall best bandwidth results. [ABSTRACT FROM AUTHOR]

Shop scheduling problem is one of the most classical problems in combinatorial optimization. In this paper, we study two-machine open shop scheduling problem, provided that one machine is subject to maintenance period which has to be performed in a fixed time interval. The target is to minimize the makespan. This paper considers non-resumable scenario, i.e., if a job which starts before the maintenance period cannot be completed before the maintenance period, then it must be restarted after the interval from scratch. We only discuss the case that the maintenance period is performed on the first machine, while the case of the maintenance period on the second machine is symmetric. We obtain a polynomial time approximation scheme, which is better than the best previous result 4 3 . [ABSTRACT FROM AUTHOR]

A subset of vertices in a graph G is called a maximum dissociation set if it induces a subgraph with vertex degree at most 1 and the subset has maximum cardinality. The dissociation number of G, denoted by ψ (G) , is the cardinality of a maximum dissociation set. A subcubic tree is a tree of maximum degree at most 3. In this paper, we give the lower and upper bounds on the dissociation number in a subcubic tree of order n and show that the number of maximum dissociation sets of a subcubic tree of order n and dissociation number ψ is at most 1. 466 4 n - 5 ψ + 2 . [ABSTRACT FROM AUTHOR]

In this paper, we consider several scheduling problems with rejection on m ≥ 1 identical machines. Each job is either accepted and processed on the machines, or it is rejected by paying a certain rejection cost. The objective is to minimize the sum of the k-th power of the makespan of accepted jobs and the total rejection cost of rejected jobs, where k > 0 is a given constant. We also introduce the conception of “job splitting" in our problems. First, we consider the single machine scheduling problem, i.e., m = 1 . When job splitting is allowed, we propose an O (n log n) -time optimal algorithm for the problem. When job splitting is not allowed, we show that this problem is polynomially solvable when k ∈ (0 , 1 ] and it becomes binary NP-hard when k > 1 . Furthermore, for the NP-hard problem, we propose a pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS). Finally, we also extend our problems and some results to m ≥ 2 identical parallel machines. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem (TSP) is a well known problem in operations research with various studies and applications. In this paper, we address a variant of the TSP in which the customers are divided into several priority groups and the order of servicing groups can be flexibly changed with a rule called the d-relaxed priority rule. The problem is called the Clustered Traveling Salesman Problem with Relaxed Priority Rule (CTSP-d). We propose two new Mixed Integer Linear Programming (MILP) models for the CTSP-d and a metaheuristic based on Iterated Local Search (ILS) with operators designed for or adapted to the problem. The experimental results obtained on the benchmark instances show that two new models performs better than previous ones, and ILS also proves its performance with 13 new best known solutions found and significant stability compared to existing metaheuristics. [ABSTRACT FROM AUTHOR]

The demographic phenomenon of population aging in China has attained the apex of global prevalence. The insufficiency of social pension resources in China has resulted in an increase in tensions in public finance, thereby necessitating a sustained and proactive approach towards addressing this issue as a strategic imperative. The study of the determinants of consumer behavior in the realm of intelligent eldercare products holds pragmatic implications for directing and stimulating the advancement of the intelligent eldercare sector. This paper presents a demand model for intelligent eldercare products, drawing upon the AISAS and Unified Theory of Acceptance and Use of Technology (UTAUT) models. The integrated framework identifies four distinct categories of influencing factors: Attention and Interest, Search and Action, Public Support, and Sharing Motivation. The survey has been constructed using six secondary variables, namely Performance Expectation (PE), Social Impact (SI), Perceived Ease of Use (PEU), Perceived Value (PV), Attitude, and Willingness to Use (WU). The study employs various statistical techniques, including regression analysis, correlation analysis, and empirical analysis, to investigate the determinants of consumers’ intentions towards products. The conclusion suggests that the Perceived Ease of Use factor holds the most significant influence on the intention of consumers to use intelligent eldercare products or services. [ABSTRACT FROM AUTHOR]

This paper considers a combination of the joint replenishment problem with single machine scheduling. There is a single resource, which is required by all the unit-time jobs, and a job can be started at time point t on the machine if and only if the machine does not process another job at t, and the resource is replenished between its release date and t. Each replenishment has a cost, which is independent of the amount replenished. The objective is to minimize the total replenishment cost plus the maximum flow time of the jobs. We consider the online variant of the problem, where the jobs are released over time, and once a job is inserted into the schedule, its starting time cannot be changed. We propose a deterministic 2-competitive online algorithm for the general input. Moreover, we show that for a certain class of inputs (so-called p-bounded input), the competitive ratio of the algorithm tends to 2 as the number of jobs tends to infinity. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions. [ABSTRACT FROM AUTHOR]

The paper considers the assignment of items to groups according to their attribute values such that the groups are as balanced as possible. Although the problem is in general NP-hard, we prove that it can be solved in pseudo-polynomial time if attribute values are integer. We point out a relation to partition and more general to multi-way number partitioning. Furthermore, we introduce a mixed-integer programming (MIP) formulation, a variable reduction technique, and an efficient lower bound for the objective value. Our computational results show that the lower bound meets the optimal objective value in the most of our instances of realistic size. Hence, the MIP solves instances with several thousand items within seconds to optimality. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicle (UAV) plays an increasingly role in data collection from Wireless Sensor Networks (WSNs) with the advantages of its high mobility and flexibility. However, the energy limitation of UAV restricts its application for data collection tasks. To solve the problem, we install solar panel on UAV to acquire energy from sunlight. This paper studies Data Collection Maximization based on Solar-powered UAV (DCMS) problem in urban environment with lots of obstacles, where one UAV equipped with solar panel is used to collect data from WSN. The problem aims at optimizing the flight trajectory of UAV such that the amount of data collected from WSN is maximized. We prove that the problem is NP-hard. To solve the DCMS problem, we first propose three algorithms: Bypass Obstacles during Flight Algorithm (BOFA), Auxiliary Graph Flight Path (AGFP), Construct Flight Plan in data collection Area (CFPA). Their objectives are to bypass the obstacles, to obtain the flight path connecting all data collection areas in WSN, to optimize the flight trajectories of UAV in the data collection areas, respectively. Afterwards, we propose an approximation algorithm called DCMSA to solve the DCMS problem based on BOFA, AGFP, CFPA algorithms. Finally, the proposed algorithm is verified by extensive simulations. [ABSTRACT FROM AUTHOR]

The k-2-distance coloring of graph G is a mapping c : V (G) → { 1 , 2 , … , k } such that any two vertices at distance at most two from each other get different colors. The 2-distance chromatic number is the smallest integer k such that G has a k-2-distance coloring, denoted by χ 2 (G) . In this paper, we prove that every planar graph G without adjacent 5-cycles and g (G) ≥ 5 and Δ (G) ≥ 17 has χ 2 (G) ≤ Δ + 3 . [ABSTRACT FROM AUTHOR]

The 0-1 linear programming problem with non-negative constraint matrix and objective vector e origins from many NP-hard combinatorial optimization problems. In this paper, we consider under what condition an optimal solution of the 0-1 problem can be obtained from a weighted linear programming. To this end, we first formulate the 0-1 problem as a sparse minimization problem. Any optimal solution of the 0-1 linear programming problem can be obtained by rounding up an optimal solution of the sparse minimization problem. Then, we establish a condition under which the sparse minimization problem and the weighted linear programming problem have the same optimal solution. The condition is based on the defined non-negative partial s-goodness of the constraint matrix and the weight vector. Further, we use two quantities to characterize a sufficient condition and necessary condition for the non-negative partial s-goodness. However, the two quantities are difficult to calculate, therefore, we provide a computable upper bound for one of the two quantities to verify the non-negative partial s-goodness. Furthermore, we propose two operations of the constraint matrix and weight vector that still preserve non-negative partial s-goodness. Finally, we give some examples to illustrate that our theory is effective and verifiable. [ABSTRACT FROM AUTHOR]

Thanks to the mass adoption of internet and mobile devices, users of the social media can seamlessly and spontaneously connect with their friends, followers and followees. Consequently, social media networks have gradually become the major venue for broadcasting and relaying information, and is casting great influences on the people in many aspects of their daily lives. Thus locating those influential users in social media has become crucially important for the successes of many viral marketing, cyber security, politics, and safety-related applications. In this study, we address the problem through solving the tiered influence and activation thresholds target set selection problem, which is to find the seed nodes that can influence the most users within a limited time frame. Both the minimum influential seeds and maximum influence within budget problems are considered in this study. Besides, this study proposes several models exploiting different requirements on seed nodes selection, such as maximum activation, early activation and dynamic threshold. These time-indexed integer program models suffer from the computational difficulties due to the large numbers of binary variables to model influence actions at each time epoch. To address this challenge, this paper designs and leverages several efficient algorithms, i.e., Graph Partition, Nodes Selection, Greedy algorithm, recursive threshold back algorithm and two-stage approach in time, especially for large-scale networks. Computational results show that it is beneficial to apply either the breadth first search or depth first search greedy algorithms for the large instances. In addition, algorithms based on node selection methods perform better in the long-tailed networks. [ABSTRACT FROM AUTHOR]

The effects of demand forecasting information (IDF) and information sharing on the pricing strategy and emission abatement decision-making in the green supply chain (GSC) are big concerns in this research. We consider a three-level GSC consisting of a data company (DC), a manufacturer and a retailer. DC can predict potential market demand and sell this information to the manufacturer as a product of data services. The manufacturer has the discretion to share IDF with a downstream retailer. By equilibrium analysis, we find that the manufacturer is reluctant to share IDF. When the information is not shared, the more accurate the IDF is, the more profits the manufacturer and DC will get, while the less profit the retailer will get. When information is shared, the profits of all participants increase with prediction accuracy. Moreover, the more accurate the prediction is, the higher the value that information sharing brings to the retailer, but the higher the loss of value to other supply chain members and the whole system. The supply chain system can always benefit from the IDF, which makes DC has the incentive to adopt scientific forecasting methods for demand forecasting in practice. Regarding emission abatement, we find that consumers’ preferences for green products always have a positive influence on the optimal decisions of GSC. Besides, the impacts do not depend on whether forecast information is shared. Thus, highlighting the low carbon preferences of consumers is crucial to the management decisions of the GSC in this paper. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is perhaps the most widely studied nonlinear combinatorial optimization problem. It has many applications in various fields, yet has proven to be extremely difficult to solve. This difficulty has motivated researchers to identify special objective function structures that permit an optimal solution to be found efficiently. Previous work has shown that certain such structures can be explained in terms of a mixed 0–1 linear reformulation of the QAP known as the level-1 reformulation–linearization-technique (RLT) form. Specifically, the objective function structures were shown to ensure that a binary optimal extreme point solution exists to the continuous relaxation. This paper extends that work by considering classes of solvable cases in which the objective function coefficients have special chess-board and graded structures, and similarly characterizing them in terms of the level-1 RLT form. As part of this characterization, we develop a new relaxed version of the level-1 RLT form, the structure of which can be readily exploited to study the special instances under consideration. [ABSTRACT FROM AUTHOR]

Product family concept predicates to a products’ group or services that derive from a common base and they have usually the same production process and physical features, in different industries. In this paper, we assume two manufacturers that produce some homogeneous product families that they want to decide upon their wholesale price and national advertising expenditure, as a new problem in the multi-agent environment. According to this problem, we propose the non-cooperative, cooperative and two-stage game models to maximize manufacturers' profits and then, based on the optimization approaches i.e., Nash and Stackelberg methods, we obtain the appropriate equilibrium strategies in a special example. Also, we propose a new profit-sharing approach for the Stackelberg model of the defined problem and discuss the solutions as some propositions and marginal points, based on the numerical studies. The results show that the centralized model leads to better profit than the non-centralized and Stackelberg models. [ABSTRACT FROM AUTHOR]

In this paper, we aim to find new approaches to assess venous thrombus embolism (VTE) risk level. We have obtained valid data by filtering all data relevant to the VTE risk rating which was collected in Shanghai general hospital from May to July 2018. In our research, the distribution rule of the valid data was found and the differences of VTE risk scores before and after the surgery was analyzed via variance analysis. We also explored the correlation between the VTE risk score and inner diameter and flow rate of deep vein in lower extremities. Meanwhile, We build linear model, nonlinear model and ordered multinamial probit model to give out the VTE risk scores. After repeated test,it was concluded that the ordered multinamial probit model was the optimum way in the assessment of VTE risk scores. In short, this paper suggests that surgery has increased VTE risk level which is closely associated with inner diameter and flow rate of deep vein in lower extremities. By deploying ordered multinamial probit model, we are able to assess the VTE risk level. The paper is significant both in theory and the practical application of risk assessment,prevention and treatment of VTE and it is also a theoretical support in VTE risk forecasting for patients with operation in hospital. [ABSTRACT FROM AUTHOR]

This paper studies the supply chain management of medical supply-processing-distribution (SPD) and models the logistics scheduling of drugs and consumables in SPD warehouse under uncertain environment. Firstly, the key management materials are determined, and then SPD distributors are set up for the key management materials to speed up the turnover of drugs and consumables, reduce the loss and unnecessary wastage, and reduce and control the operating costs of hospital departments. This paper establishes an optimization model for achieving the highest total efficiency of drug or consumables distribution and receipt on the premise of sending the least SPD distributors to release the nurses who plan to apply for, count and keep the materials in the second-level warehouse, and return the nursestime to patients. Through the example of SPD distribution of infusion devices consumed by respiratory consumables in a large scale A hospital, the feasibility of using this model to calculate the optimal allocation method of SPD material distributors and the establishment of SPD material distributors in each department is verified. Finally, this paper compares the effects before and after practice and verifies the correctness and effectiveness of the model. [ABSTRACT FROM AUTHOR]

Inconsistent data indicates that there is conflicted information in the data, which can be formalized as the violations of given semantic constraints. To improve data quality, repair means to make the data consistent by modifying the original data. Using the feedbacks of users to direct the repair operations is a popular solution. Under the setting of big data, it is unrealistic to let users give their feedbacks on the whole data set. In this paper, the repair position selection problem (RPS for short) is formally defined and studied. Intuitively, the RPS problem tries to find an optimal set of repair positions under the limitation of repairing cost such that we can obtain consistent data as many as possible. First, the RPS problem is formalized. Then, by considering three different repair strategies, the complexities and approximabilities of the corresponding RPS problems are studied. [ABSTRACT FROM AUTHOR]