Search

In modern manufacturing and service industries, urgent orders and service tasks are common, and the speed of handling such urgent tasks is an important indicator of production and service efficiency. In this study, we consider scheduling jobs on two parallel machines with the random arrival of an emergency job. The objective is to minimise the makespan, subject to a given maximum waiting time of the emergency job. We first show that the worst-case ratio of the existing algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l is at least 3/2 when m = 2. We then analyse some properties of the optimal schedule and derive lower bounds on the optimal makespan. Finally, we present an improved approximation algorithm with a tight worst-case ratio of 4/3. We also provide numerical results showing that our proposed algorithm outperforms algorithm LPT $ _l $ l -SPT $ _{m-l} $ m − l . [ABSTRACT FROM AUTHOR]

We improve the approximation ratio for Maximum Weight Series-Parallel Subgraph from 1 / 2 to 1 / 2 + 1 / 60. [ABSTRACT FROM AUTHOR]

In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B + 1) -approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network. [ABSTRACT FROM AUTHOR]

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree δ and maximum degree Δ . We provide a linear-time algorithm for computing a cycle C ′ ≠ C of length at least n - 4 α (n + 2 α) + 8 , where α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of Δ δ = o (n) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0 < p ≤ 0.02 , if the minimum degree of G is at least 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least 1 - 1 n 50 p 4 + 1 in p o l y (n) · 2 4 p n time. This result implies that, when the minimum degree δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when δ = ω (log n) , our probabilistic algorithm works in 2 o (n) time. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm to obtain the sampling factors to model any frequency partitioning so that it is realized using low complexity rational decimated non-uniform filter banks (RDNUFBs). The proposed algorithm is employed to approximate the Bark scale to find a rational frequency partitioning that can be realized using RDNUFBs with less approximation error. The proposed Bark frequency partitioning is found to reduce the average deviation in centre frequency and bandwidth by 65.04% and 48.50%, respectively, and root-mean-square bandwidth deviation by 54.46% when compared to those of the existing perceptual wavelet approximation of Bark scale. In the first filter bank design approach discussed in the paper, a near-perfect reconstruction partially cosine modulated filter bank is employed to obtain the improved Bark frequency partitioning. In the second design approach, the hardware complexity of the PCM-based RDNUFB is reduced by deriving the channels with different sampling factors from the same prototype filter by the method of channel merging. There is a considerable reduction of 40.83% in the number of multipliers when merging of partially cosine modulated channels is employed. It is also found that both the proposed approaches can reduce the delay by 95.17% when compared to the existing rational tree approximation methods and hence, are suitable for real-time applications. [ABSTRACT FROM AUTHOR]

In this study, we propose a novel cloud-edge collaborative task assignment model for smart farms that consists of a cloud server, m edge servers, and n sensors. The edge servers rely solely on solar-generated energy, which is limited, whereas the cloud server has access to a limitless amount of energy supplied by the smart grid. Each entire task from a sensor is processed by either an edge server or the cloud server. We consider the task to be unsplittable. Building on the algorithm for the multimachine job scheduling problem, we develop a corresponding approximation algorithm. In addition, we propose a new discrete heuristic based on the dwarf mongoose optimization algorithmm, named the discrete dwarf mongoose optimization algorithm, and we utilize the proposed approximation algorithm to improve the convergence speed of this heuristic while yielding better solutions. In this study, we consider task sets with heavy tasks independently, where a heavy task is a task that requires many computing resources to process. If such tasks are assigned as ordinary tasks, the assignment results may be poor. Therefore, we propose a new method to solve this kind of problem. [ABSTRACT FROM AUTHOR]

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

In multi-objective mixed-integer convex optimization, multiple convex objective functions need to be optimized simultaneously while some of the variables are restricted to take integer values. In this paper, we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization problem into several multi-objective continuous convex optimization problems, which we refer to as patches. We then dynamically compute and improve coverages of the nondominated sets of those patches to finally combine them to obtain an enclosure of the nondominated set of the multi-objective mixed-integer convex optimization problem. Additionally, we introduce a mechanism to reduce the number of patches that need to be considered in total. Our new algorithm is the first of its kind and guaranteed to return an enclosure of prescribed quality within a finite number of iterations. For selected numerical test instances we compare our new criterion space based approach to other algorithms from the literature and show that much larger instances can be solved with our new algorithm. [ABSTRACT FROM AUTHOR]

Emergency medical services (EMS) are an important part of the modern healthcare system that tries to provide timely medical care and transportation to patients to reduce morbidity and mortality. Performance evaluation of such EMS systems to determine measures such as mean service rates, dispatch probabilities, busy probabilities, and on-scene times is necessary to design effective and efficient systems. In this paper, we consider an urban EMS system that employs three types of emergency vehicles, including advanced life support (ALS), basic life support (BLS) and first responder vehicle (FRV). We consider two types of patients: type A requires ALS to be dispatched, while type B patients are expected to be served by BLS ambulances. We also consider co-located servers so ambulances of different types can be co-located at the same station. The presence of different types of servers (ambulances) and the patients with different dispatch policies, along with co-located servers, makes it applicable to a more realistic system. We first discuss a modification of the hypercube queueing model for the proposed system and then present an approximate approach for application in large EMS systems. These approaches are compared against a simulation-based model by computing server utilization, service times and on-scene time of ambulances. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a function f: V → {0, 1, 2, 3, 4} is a triple Roman dominating function (TRDF) of G, for each vertex v ∈ V, (i) if f (v) = 0, then v must have either one neighbour in V4, or either two neighbours in V2 ∪ V3 (one neighbour in V3) or either three neighbours in V2, (ii) if f (v) = 1, then v must have either one neighbour in V3 ∪ V4 or either two neighbours in V2, and if f (v) = 2, then v must have one neighbour in V2 ∪ V3 ∪ V4. The triple Roman domination number of G is the minimum weight of an TRDF f of G, where the weight of f is v V f (v). The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at most 4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an (2H (Δ(G) + 1) - 1)-approximation algorithm for solving the problem for any graph G, where Δ(G) is the maximum degree of G and H (d) denotes the first d terms of the harmonic series. In addition, we prove that for any ε > 0 there is no (1/4 - ε) ln |V |-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP ⊆ DTIME (|V |O(log log |V |)). [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, the maximum triangle problem asks for finding a triangle with three vertices in P that encloses the maximum number of points from P. While the problem is easily solvable in O(n³) time, it has been open whether a subcubic solution is possible. In this paper, we show that the problem can be solved in o(n3) time, using a reduction to min-plus matrix multiplication. We also provide some improved approximation algorithms for the problem, including a 4-approximation algorithm running in O(n log n log h) time, and a 3-approximation algorithm with O(nh log n+nh²) runtime, where h is the size of the convex hull of P. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V and edge set E , a vertex set D is a dominating set (DS) of G , if every vertex v ∈ V is either in D or adjacent to a vertex in D. If D is a DS of G and for every vertex v ∈ V ∖ D there exists a vertex u ∈ D adjacent to v such that (D ∖ { u }) ∪ { v } is also a DS of G , then D is a secure dominating set (SDS). The minimum secure dominating set problem (MinSDS) is to find an SDS of G with the minimum cardinality. In this paper, we design PTASs for MinSDS on planar graphs and growth-bounded graphs, that is, the computed solutions approximate the optimal value within factor (1 + ɛ) for any constant ɛ ∈ (0 , 1). [ABSTRACT FROM AUTHOR]

This paper studies a two-agent scheduling problem on mixed batch machines in parallel. A mixed batch machine can process several jobs simultaneously as a batch, as long as the number of jobs in the batch does not exceed the machine capacity. The processing time of a mixed batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimise the weighted sum of two agents' makespans. We present four approximation algorithms based on two strategies: the machine-centric strategy and the agent-centric strategy. For each strategy, a full batch longest processing time (FBLPT) rule and a longest processing time greedy (LPTG) rule are used. We conduct theoretical analyses based on the worst-case performance ratio to provide the provable guarantees on the performances of the algorithms, and simulation analyses based on randomly generated instances to evaluate the average performances of the algorithms. Furthermore, we verify the consistency between the theoretical and simulation results. The algorithms using agent-centric strategy perform better than ones using machine-centric strategy. Finally, we provide managerial insights for the problem by analysing the technological parameters of batches, importance of agents, and demand seasonality. [ABSTRACT FROM AUTHOR]

Personalized travel itinerary recommendation algorithms are the focus of research in smart tourism and tourism GIS. Aiming to address issues present in travel itinerary recommendations for the increasingly popular "self-drive tour" mode, this study proposes an algorithm based on comprehensive tourist satisfaction to mitigate problems such as the neglect of important relevant factors and low degree of personalization. First, we construct a model of tourist satisfaction for travel itineraries by comprehensively considering factors including time utilization, the attractiveness of attractions, itinerary feasibility, and the diversity of attraction types. Unlike previous studies, we consider dining and accommodation time during the itinerary, the physical condition of tourists, and the diversity of attraction types, and establish penalty functions to flexibly constrain deviations from the expected conditions in itinerary planning. Then, with the optimization of comprehensive tourist satisfaction as the objective, we design a new algorithm to address the itinerary recommendation problem, supporting tourists in selecting must-visit attractions, restaurants, and hotels, as well as personalized preferences such as the sightseeing sequence. The experimental results demonstrate that our proposed algorithm outperforms two baseline algorithms, providing higher comprehensive tourist satisfaction while also exhibiting greater feasibility in itinerary planning. The proposed algorithm effectively addresses the issue of personalized travel itinerary recommendation, presenting an efficient, feasible, and practical solution. [ABSTRACT FROM AUTHOR]

In MAXSPACE, given a set of ads A , one wants to schedule a subset A ′ ⊆ A into K slots B 1 , ⋯ , B K of size L. Each ad A i ∈ A has a size s i and a frequency w i . A schedule is feasible if the total size of ads in any slot is at most L, and each ad A i ∈ A ′ appears in exactly w i slots and at most once per slot. The goal is to find a feasible schedule that maximizes the sum of the space occupied by all slots. We consider a generalization called MAXSPACE-R for which an ad A i also has a release date r i and may only appear in a slot B j if j ≥ r i . For this variant, we give a 1/9-approximation algorithm. Furthermore, we consider MAXSPACE-RDV for which an ad A i also has a deadline d i (and may only appear in a slot B j with r i ≤ j ≤ d i ), and a value v i that is the gain of each assigned copy of A i (which can be unrelated to s i ). We present a polynomial-time approximation scheme for this problem when K is bounded by a constant. This is the best factor one can expect since MAXSPACE is strongly NP-hard, even if K = 2 . [ABSTRACT FROM AUTHOR]

A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01. [ABSTRACT FROM AUTHOR]

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. [ABSTRACT FROM AUTHOR]

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

We revisit the problem of property testing for convex position for point sets in ℝ. Our results draw from previous ideas of Czumaj, Sohler, and Ziegler (2000). First, their testing algorithm is redesigned and its analysis is revised for correctness. Second, its functionality is expanded by (i) exhibiting both negative and positive certificates along with the convexity determination, and (ii) significantly extending the input range for moderate and higher dimensions. The behavior of the randomized tester on input set ⊂ ℝ is as follows: (i) if is in convex position, it accepts; (ii) if is far from convex position, with probability at least 2/3, it rejects and outputs a (+2)-point witness of non-convexity as a negative certificate; (iii) if is close to convex position, with probability at least 2/3, it accepts and outputs a subset in convex position that is a suitable approximation of the largest subset in convex position. The algorithm examines a sublinear number of points and runs in subquadratic time for every fixed dimension. [ABSTRACT FROM AUTHOR]

In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r j , deadline d j , and processing time p j . They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [ r j , d j ] window. This problem has been studied extensively (even for the case of m = 1 ). Several special cases of the problem remain open. Bar-Noy et al. (Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, USA, pp. 622–631. ACM, 1999, https://doi.org/10.1145/301250.301420) presented an algorithm with ratio 1 - 1 / (1 + 1 / m) m for m machines, which approaches 1 - 1 / e as m increases. For m = 1 , Chuzhoy et al. (42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 348–356. IEEE Computer Society, 2001) presented an algorithm with approximation with ratio 1 - 1 e - ε (for any ε > 0 ). Recently Im et al. (SIAM J Discrete Math 34(3):1649–1669, 2020) presented an algorithm with ratio 1 - 1 / e + ε 0 for some absolute constant ε 0 > 0 for any fixed m. They also presented an algorithm with ratio 1 - O (log m / m) - ε for general m which approaches 1 as m grows. The approximability of the problem for m = O (1) remains a major open question. Even for the case of m = 1 and c = O (1) distinct processing times the problem is open (Sgall in: Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceedings, pp 2–11, 2012). In this paper we study the case of m = O (1) and show that if there are c distinct processing times, i.e. p j 's come from a set of size c, then there is a randomized (1 - ε) -approximation that runs in time O (n m c 7 ε - 6 log T) , where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning. [ABSTRACT FROM AUTHOR]

In offline scheduling models, jobs are given with their exact processing times. In their online counterparts, jobs arrive in sequence together with their processing times and the scheduler makes irrevocable decisions on how to execute each of them upon its arrival. We consider a semi-online variant which has equally rich application background, called scheduling with testing, where the exact processing time of a job is revealed only after a required testing operation is finished, or otherwise the job has to be executed for a given possibly over-estimated length of time. For multiprocessor scheduling with testing to minimize the total job completion time, we present several first approximation algorithms with constant competitive ratios for various settings, including a 2 φ -competitive algorithm for the non-preemptive general testing case and a (0.0382 + 2.7925 (1 - 1 2 m)) -competitive randomized algorithm, when the number of machines m ≥ 37 or otherwise 2.7925-competitive, where φ = (1 + 5) / 2 < 1.6181 is the golden ratio and m is the number of machines, a (3.5 - 3 2 m) -competitive algorithm allowing job preemption when m ≥ 3 or otherwise 3-competitive, and a (φ + φ + 1 2 (1 - 1 m)) -competitive algorithm for the non-preemptive uniform testing case when m ≥ 5 or otherwise (φ + 1) -competitive. Our results improve three previous best approximation algorithms for the single machine scheduling with testing problems, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of finding a regression in a version control system (VCS), such as git. The set of versions is modelled by a directed acyclic graph (DAG) where vertices represent versions of the software, and arcs are the changes between different versions. We assume that somewhere in the DAG, a bug was introduced, which persists in all of its subsequent versions. It is possible to query a vertex to check whether the corresponding version carries the bug. Given a DAG and a bugged vertex, the Regression Search Problem consists in finding the first vertex containing the bug in a minimum number of queries in the worst-case scenario. This problem is known to be NP-complete. We study the algorithm used in git to address this problem, known as git bisect. We prove that in a general setting, git bisect can use an exponentially larger number of queries than an optimal algorithm. We also consider the restriction where all vertices have indegree at most 2 (i.e. where merges are made between at most two branches at a time in the VCS), and prove that in this case, git bisect is a 1 log 2 (3 / 2) -approximation algorithm, and that this bound is tight. We also provide a better approximation algorithm for this case. Finally, we give an alternative proof of the NP-completeness of the Regression Search Problem, via a variation with bounded indegree. [ABSTRACT FROM AUTHOR]

In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V , E , A) , where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F ⊆ E ( H ⊆ A ) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A . The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = ∅ and H = A For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27 4 -approximation algorithm. This algorithm achieves an approximation ratio of 33 5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling with a non-renewable resource. In this setting, we are given a set of jobs, each characterized by a processing time, a weight, and a resource requirement. At fixed points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has enough resource available at the start of its processing. The objective that we consider is the minimization of the sum of weighted completion times. The main contribution of the paper is a PTAS for the case of 0 processing times ( 1 | r m = 1 , p j = 0 | ∑ w j C j ). In addition, we show strong NP-hardness of the case of unit resource requirements and weights ( 1 | r m = 1 , a j = 1 | ∑ C j ), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem. Finally, we investigate a variant of the problem where processing times are 0 and the resource arrival times are unknown. We present a (4 + ϵ) -approximation algorithm, together with a (4 - ε) -inapproximability result, for any ε > 0 . [ABSTRACT FROM AUTHOR]

Given a graph G, the minimum Connected- k -Subgraph Cover problem (MinC k SC) is to find a minimum vertex subset C of G such that every connected subgraph of G on k vertices has at least one vertex in C. If furthermore the subgraph of G induced by C is connected, then the problem is denoted as MinC k SC $_{con}$. In this paper, we first present a PTAS for MinC k SC on an H -minor-free graph, where H is a graph with a constant number of vertices. Then, we design an $O((\omega+1)(2(k-1)(\omega+2))^{3\omega+3})|V|$ -time FPT algorithm for MinC k SC $_{con}$ on a graph with treewidth $\omega$ , based on which we further design an $O(2^{O(\sqrt{t}\log t)}|V|^{O(1)})$ time subexponential FPT algorithm for MinC k SC $_{con}$ on an H -minor-free graph, where t is an upper bound of solution size. [ABSTRACT FROM AUTHOR]

In this paper, we study the regular sensory data collection of Points of Interest (PoIs) with multiple Unmanned Aerial Vehicles (UAVs) during an extended monitoring period, where each PoI is visited multiple times before its data update deadline to keep the data fresh. We observe that most existing studies ignored the important differences in the data stored in the PoIs, scheduled a plan that dispatched UAVs to visit all PoIs before the same deadline, and simply repeated the plan during the monitoring period, which undoubtedly increased the service cost of the UAVs. Considering the specific data update deadline of each PoI, we formulate a novel UAV cost minimization problem to collect the data stored in each PoI before its deadline by finding a series of plans for UAVs such that the service cost of the UAVs during the monitoring period is minimized; the service cost of the UAVs is composed of the consumed energy of the UAVs utilized for hovering for data collection and the consumed energy of the UAVs utilized for flying. To deal with the above NP-hard problem, we devise an approximation algorithm by grouping the PoIs and accessing them in batches. Then, we analyze the proposed algorithm and evaluate the performance of the algorithm through experimental simulations. The experimental results show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]

We consider bicriteria flowshop scheduling problems with two machines to simultaneously minimize the makespan and the total completion time without any prioritization between the two objectives. An approximation relative to the optimal value of the problem with regard to each objective is adopted, even though a schedule with both objectives reaching their minimum at the same time may not exist. We consider several problems with ordered aspects on processing times such as job ordered and machine ordered. For each problem, we propose a fast (ρ 1 , ρ 2) -approximation algorithm, where ρ 1 and ρ 2 indicate the approximation ratios with regard to the makespan and the total completion time, respectively, and we explore the problem's inapproximability region that cannot be reached by any algorithm. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence-constrained single-machine scheduling and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints. Funding: This work has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. [ABSTRACT FROM AUTHOR]

This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacity constraints. The paper focuses on the bin packing with linear usage cost (BPLUC) variant of bin packing, which includes fixed and variable costs in the calculation of the cost of a used bin. We prove that every approximation algorithm for the bin and vector bin packing can be used for BPLUC and VBPLUC, respectively. We propose a more power-efficient approach to VMP by applying a vector bin packing algorithm to minimize power consumption in data centers. We test the proposed algorithm on various synthetic and real workloads, and the experimental results demonstrate that it is more power-efficient than existing algorithms for VMP. The findings suggest that the proposed algorithm has significant implications for energy-efficient strategies in cloud data centers. Generally, this study makes contributes to the development of energy-efficient approaches to VMP that can help reduce power consumption and improve the sustainability of cloud data centers. [ABSTRACT FROM AUTHOR]

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

Over the past few decades, there has been a significant increase in the number of Earth observation satellites, and the area of ground targets requiring observation has also been expanding. To effectively utilize the capabilities of these satellites and capture larger areas of ground targets, it has become essential to plan imaging tasks for large regional coverage using multiple satellites. First, we establish a 0-1 integer programming model to accurately describe the problem and analyze the challenges associated with solving the model. Second, we propose a heuristic algorithm based on the triple grids method. This approach utilizes a generated grid to create fewer candidate strips, a calculation grid to determine the effective coverage area more accurately, and a refined grid to solve the issue of repeated coverage of strips. Furthermore, we employ an approximation algorithm to further improve the solutions obtained from the heuristic algorithm. By comparing the proposed method to the traditional greedy heuristic algorithm and three evolutionary algorithms, the results show that our method has better performance in terms of coverage and efficiency. [ABSTRACT FROM AUTHOR]

We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input. We also complement our positive result with a lower bound showing that any constant (non bi-criteria) approximation algorithm has amortized cost at least linear in z. Finally, we conduct an in-depth experimental analysis of our algorithm on Twitter, Flickr, and Air-Quality datasets showing the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χ d (G). Graphs with χ d (G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4 , deciding whether χ d (G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q -dominator partization problem (Min- q -D-Partz). In Min- q -D-Partz, given a graph G , the objective is to find a vertex set S of minimum size such that χ d (G [ V ∖ S ]) ≤ q. We prove that Min- 2 -D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min- 3 -D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O (log n). [ABSTRACT FROM AUTHOR]

We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2 / 3. We propose a new approximation algorithm which improves the ratio to 7 / 10. [ABSTRACT FROM AUTHOR]

In "Sequential Competitive Facility Location: Exact and Approximate Algorithms," Qi et al. consider a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets and maximize their market shares of demand following a probabilistic choice model. They derive an equivalent, single-level mixed-integer nonlinear program (MINLP) reformulation of the bilevel MINLP and exploit the problem structures to derive valid inequalities based on submodularity and concave overestimation. They also develop an approximation algorithm with a constant approximation guarantee. They further study several extensions of CFLP that have general facility-opening costs, outside competitors, and diverse facility-planning decisions. Their approaches significantly accelerate the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods. We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities based on submodularity and concave overestimation, respectively. We use the two valid inequalities in a branch-and-cut algorithm to find globally optimal solutions. Then, we propose an approximation algorithm to find good-quality solutions with a constant approximation guarantee. We develop several extensions by considering general facility-opening costs and outside competitors as well as diverse facility-planning decisions, and we discuss solution approaches for each extension. We conduct numerical studies to demonstrate that the exact algorithm significantly accelerates the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods, and the approximation algorithm can quickly find high-quality solutions. We derive managerial insights based on sensitivity analysis of different settings that affect customers' probabilistic choices and the ensuing demand. Funding: M. Qi was partially supported by the National Natural Science Foundation of China [Grant 71772100] to work on this project. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2339. [ABSTRACT FROM AUTHOR]

We consider parallel-machine scheduling with identical machine resource capacity limits and DeJong's learning effect. Each job has a resource consumption requirement and a normal processing time. The actual processing time of a job is a function of its normal processing time, subject to DeJong's learning effect, while the resource consumption of a job is a function of its actual processing time. Each machine has the same resource capacity limit. The objective is to maximise the minimum machine load. Considering three resource consumption functions, namely, linear, concave, and convex, we show that all three scheduling models are NP-hard and propose two approximation algorithms for the models and analyse their worst-case ratios. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [ABSTRACT FROM AUTHOR]

Summary: With the rise of industrialization, the importance of the industrial Internet of Things (IIoT) has increased significantly, and with it comes a variety of security threats. Therefore, the security of these networks is critical. Industrial Response Systems (IRSs), as the last line of security, plays an important role in the security system of the Industrial Internet of Things. In this paper, a new IRS model based on the non‐cooperative game is proposed. First, by combining the Partially Observable Markov Decision Process (POMDP) model with the stochastic game model based on the expanded attack tree, our model could effectively perceive the changes at each node. Second, our model incorporates the alarms of intrusion detection system (IDS) and the physical quantities of sensors in Industrial Cyber‐Physical System (ICPS) into the quantization system so that the model can respond to intruders more accurately and comprehensively. Finally, we develop this model based on multiprocessors to speed up the solution process, and adopt an approximation algorithm to reduce the number of iterations of the POMDP [ABSTRACT FROM AUTHOR]

In this paper, the first fixed-ratio approximation algorithms are proposed for a series of asymmetric settings of well-known combinatorial routing problems. Among them are the Steiner cycle problem, the prize-collecting traveling salesman problem, the minimum cost cycle cover problem by a bounded number of cycles, etc. Almost all of the proposed algorithms rely on original reductions of the considered problems to auxiliary instances of the asymmetric traveling salesman problem and employ the breakthrough approximation results for this problem obtained recently by O. Svensson, J. Tarnawski, L. Végh, V. Traub, and J. Vygen. On the other hand, approximation of the cycle cover problem was proved by applying a deeper extension of their approach. [ABSTRACT FROM AUTHOR]

We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single transporter. The goal is to minimize the time that all the jobs are delivered to their destination, such that the transporter returns. We propose a 11 / 6 + ε -approximation algorithm which improves upon the best-known approximation ratio of 2. [ABSTRACT FROM AUTHOR]

We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called crossing swords that requires at most - times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples. [ABSTRACT FROM AUTHOR]

Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3 2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3 2 -approximation algorithm in [A. SebH o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v ∈ V is contained in exactly one path of P . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover [MinPC (MaxPC)], is defined as follows: Let U = { 0 , 1 , ⋯ , n - 1 } . Given a graph G = (V , E) and a weight function f : U → R ∪ { + ∞ , - ∞ } that defines a weight for each path based on its length, the objective of MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and P L be the set of paths such that each path is of length ℓ ∈ L . We consider Min P L PC with binary cost, i.e., the cost function is f (ℓ) = 1 if ℓ ∈ L ; otherwise, f (ℓ) = 0 . We also consider Max P L PC with f (ℓ) = ℓ + 1 , if ℓ ∈ L ; otherwise, f (ℓ) = 0 . Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using Min P L PC and Max P L PC. In this paper, we first show that deciding whether Min P { 0 , 1 , 2 } PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (i) for any constant σ ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio σ for Min P { 0 , 1 , 2 } PC unless P = NP, and (ii) Max P { 3 , ⋯ , n - 1 } PC is NP-hard for the same graph class. Next, we present a polynomial-time algorithm for Min P { 0 , 1 , ⋯ , k } PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for Max P { 3 , ⋯ , n - 1 } PC, which becomes a 2.5-approximation algorithm for subcubic graphs. [ABSTRACT FROM AUTHOR]

Nowadays, the flourish of the internet of things incurs a great demand for progressive technologies to prolong the lifetime of Wireless Sensor Networks. Exploiting a fleet of Mobile Chargers (MCs) to replenish the energycritical sensor nodes provides a new dimension to maintain long-term network operations, but may suffer from high charging delay due to MC’s limited mobility. Most existing studies focus on the reduction of server-oriented delay, i.e., the overall time taken by MCs (servers) to carry out sensor charging and travel inside the sensing field. However, these solutions may not be robust enough as some energy-critical sensor nodes will run out of the stored energy before the charger’s arrival. In this article, we address this challenge by reducing the client-oriented delay—referred to as the wait-for delay—which is defined as the “arrival times” at the to-be-charged sensor nodes (clients). To this end, we first formulate a novel wait-for charging delay minimization problem under the multi-node energy charging scheme. We then prove the NP-hardness of the proposed problem. Inspired by empirical observations, we devise an efficient approximation algorithm with a provable approximation ratio for the problem. We have evaluated the proposed algorithm using real-life system settings. The experimental results suggest that the proposed algorithm certainly performs better than the existing benchmarks; it could reduce the wait-for delay by up to 87.4 percent. [ABSTRACT FROM AUTHOR]

Matrix decomposition is a widely used tool in machine learning with many applications such as dimension reduction or visualization. In this paper we consider decomposing X, a matrix of size n × m , to a product WS where we require that S, a matrix of size n × k , needs to have consecutive ones property. More specifically, we require that each row of S needs to be in the form of 0 , ... , 0 , 1 , ... , 1 , 0 , ... , 0 . Such decompositions are particularly meaningful if X is a matrix where each row represents a time series; in such a case the ones in each row in S represent a time segment. We show that the optimization problem is inapproximable. To solve the problem we propose 5 different algorithms. The first two algorithms are based on solving iteratively S while keeping W fixed and then solving W while keeping S fixed. The next two algorithms are based on greedily optimizing a single row in S and the corresponding column in W. The last algorithm first finds the optimal decomposition of with 2 k - 1 non-overlapping rows, and then greedily combines the rows until k rows remain. We compare the algorithms experimentally, focusing on the quality of the decomposition as well as the computational time. We show experimentally that our algorithms yield interpretable results in practical time. [ABSTRACT FROM AUTHOR]

In this paper, we propose and investigate the individually fair k-center with outliers (IFkCO). In the IFkCO, we are given an n-sized vertex set in a metric space, as well as integers k and q. At most k vertices can be selected as the centers and at most q vertices can be selected as the outliers. The centers are selected to serve all the not-an-outlier (i.e., served) vertices. The so-called individual fairness constraint restricts that every served vertex must have a selected center not too far way. More precisely, it is supposed that there exists at least one center among its ⌈ (n - q) / k ⌉ closest neighbors for every served vertex. Because every center serves (n - q) / k vertices on the average. The objective is to select centers and outliers, assign every served vertex to some center, such that the maximum fairness ratio over all served vertices is minimized, where the fairness ratio of a vertex is defined as the ratio between its distance with the assigned center and its distance with a ⌈ (n - q) / k ⌉ th closest neighbor. As our main contribution, a 4-approximation algorithm is presented, based on which we develop an improved algorithm from a practical perspective. Extensive experiment results on both synthetic datasets and real-world datasets are presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H = (V , E , w) into three disjoint subsets V 1 , V 2 , and V 3 such that the sum of edge weights cross different parts is maximized subject to | | V i | - | V l | | ≤ B ( ∀ i ≠ l ∈ { 1 , 2 , 3 } ) for a given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique. [ABSTRACT FROM AUTHOR]

We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7 / 3. This allows us to derive a 7 / 3 -approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach. [ABSTRACT FROM AUTHOR]