Journal of Combinatorial Optimization
Journal Prestige (SJR): 0.579 Citation Impact (citeScore): 1 Number of Followers: 7 Hybrid journal (It can contain Open Access articles) ISSN (Print) 15732886  ISSN (Online) 13826905 Published by SpringerVerlag [2468 journals] 
 EPTAS for parallel identical machine scheduling with time restrictions

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider the nonpreemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of nonconstant values of B on one machine was not known to admit a PTAS.
PubDate: 20240222

 On the packing number of antibalanced signed simple planar graphs of
negative girth at least 5
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The packing number of a signed graph \((G, \sigma )\) , denoted \(\rho (G, \sigma )\) , is the maximum number l of signatures \(\sigma _1, \sigma _2,\ldots , \sigma _l\) such that each \(\sigma _i\) is switching equivalent to \(\sigma \) and the sets of negative edges \(E^{}_{\sigma _i}\) of \((G,\sigma _i)\) are pairwise disjoint. A signed graph packs if its packing number is equal to its negative girth. A reformulation of some wellknown conjecture in extension of the 4color theorem is that every antibalanced signed planar graph and every signed bipartite planar graph packs. On this class of signed planar graph the case when negative girth is 3 is equivalent to the 4color theorem. For negative girth 4 and 5, based on the dual language of packing Tjoins, a proof is claimed by B. Guenin in 2002, but never published. Based on this unpublished work, and using the language of packing Tjoins, proofs for girth 6, 7, and 8 are published. We have recently provided a direct proof for girth 4 and in this work extend the technique to prove the case of girth 5.
PubDate: 20240212

 On convexity in split graphs: complexity of Steiner tree and domination

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Given a graph G with a terminal set \(R \subseteq V(G)\) , the Steiner tree problem (STREE) asks for a set \(S\subseteq V(G) {\setminus } R\) such that the graph induced on \(S\cup R\) is connected. A split graph is a graph which can be partitioned into a clique and an independent set. It is known that STREE is NPcomplete on split graphs White et al. (Networks 15(1):109–124, 1985). To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomialtime solvable for treeconvex split graphs with convexity on clique (K), whereas STREE is NPcomplete on treeconvex split graphs with convexity on independent set (I). We further strengthen our NPcomplete result by establishing a dichotomy which says that for unarytreeconvex split graphs (pathconvex split graphs), STREE is polynomialtime solvable, and NPcomplete for binarytreeconvex split graphs (combconvex split graphs). We also show that STREE is polynomialtime solvable for triadconvex split graphs with convexity on I, and circularconvex split graphs. Further, we show that STREE can be used as a framework for the dominating set problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of STREE and DS is the same for all these subclasses of split graphs. Finally, from the parameterized perspective with solution size being the parameter, we show that the Steiner tree problem on split graphs is W[2]hard, whereas when the parameter is treewidth, we show that the problem is fixedparameter tractable, and if the parameter is the solution size and the maximum degree of I (d), then we show that the Steiner tree problem on split graphs has a kernel of size at most \((2d1)k^{d1}+k,~k= S \) .
PubDate: 20240212

 An extension of the Christofides heuristic for a singledepot multiple
Hamiltonian path problem
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study a generalization of the classical Hamiltonian path problem, where multiple salesmen are positioned at the same depot, of which no more than k can be selected to service n destinations, with the objective to minimize the total travel distance. Distances between destinations (and the single depot) are assumed to satisfy the triangle inequality. We develop a nontrivial extension of the wellknown Christofides heuristic for this problem, which achieves an approximation ratio of \(21/(2+k)\) with \(O(n^3)\) running time for arbitrary \(k\ge 1\) .
PubDate: 20240212

 Improved shuffled Frog leaping algorithm with unsupervised population
partitioning strategies for complex optimization problems
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Shuffled Frog leaping algorithm (SFLA) is a multi population swarm intelligence algorithm which employs population partitioning techniques during the evolutionary stage. Methods adopted by SFLA for partitioning the population into memeplexes play a critical role in determining its ability to solve complex optimization problems. However, limited research is done in this direction. This work presents supervised machine learning based methods Spectral Partitioning (SCP), Agglomerative Partitioning (AGP) and Ward Hierarchical Partitioning (WHP) for distributing the solutions into memeplexes. The efficacy of variants of SFLA with these methods is assessed over CEC2015 Bound Constrained SingleObjective Computationally Expensive Numerical Optimisation problems. Analysis of results establishes that proposed SCP, AGP and WHP methods outperform Shuffled complex evolution (SCE) partitioning technique; Seed and distance based partitioning technique (SEED), Random partitioning (RAND) and Dynamic subswarm partitioning (DNS) for more than 10 functions. Time complexity of all the algorithms is comparable with each other. Statistical analysis using Wilcoxon signed rank sum test indicates that SCP, AGP and WHP perform significantly better than existing approaches for small dimensions.
PubDate: 20240211

 The prediction model of water level in front of the check gate of the LSTM
neural network based on AIWCLPSO
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract To solve the problem of predicting water level in front of check gate under different time scales, a different time scale prediction model with a long short term memory (LSTM) neural network based on adaptive inertia weight comprehensive learning particle swarm optimization (AIWCLPSO) is proposed. The AIW and CLPSO are adopted to improve the global optimization ability and convergence velocity of particle swarm optimization in the proposed model. The model was applied to the water level prediction in front of the Chaohu Lake check gate. The example of the water level prediction in front of the Chaohu Lake check gate shows that the proposed model predicts the trend of water level fluctuation better than LSTM with high accuracy of Nash coefficient up to 0.9851 and root mean square error up to 0.0273 m. The optimized algorithm can obtain the optimal parameters of the LSTM neural network, overcome the limitations of the traditional LSTM neural network in parameter selection and inaccurate prediction, and maintain good prediction results in the predicting water level in front of the check gate at different time scales.This study can provide important reference for water level prediction, scheduling warning, water resources scheduling decision and intelligent gate control in long distance water transfer projects.
PubDate: 20240128

 A branchandcut algorithm for the balanced traveling salesman problem

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The balanced traveling salesman problem (BTSP) is a variant of the traveling salesman problem, in which one seeks a tour that minimizes the difference between the largest and smallest edge costs in the tour. The BTSP, which is obviously NPhard, was first investigated by Larusic and Punnen (Comput Oper Res 38(5):868–875, 2011). They proposed several heuristics based on the doublethreshold framework, which converge to goodquality solutions though not always optimal. In this paper, we design a specialpurpose branchandcut algorithm for exactly solving the BTSP. In contrast with the classical TSP, due to the BTSP’s objective function, the efficiency of algorithms for solving the BTSP depends heavily on determining correctly the largest and smallest edge costs in the tour. In the proposed branchandcut algorithm, we develop several mechanisms based on local cutting planes, edge elimination, and variable fixing to locate those edge costs more precisely. Other critical ingredients in our method are algorithms for initializing lower and upper bounds on the optimal value of the BTSP, which serve as warm starts for the branchandcut algorithm. Experiments on the same testbed of TSPLIB instances show that our algorithm can solve 63 out of 65 instances to proven optimality.
PubDate: 20240128

 Integrating supplier selection decisions into an inventory location
problem for designing the supply chain network
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper proposes a novel InventoryLocation problem that integrates supplier selection decisions to design a threeechelon supply chain network, under a continuous (s,Q) inventory control policy at the warehouses. In this problem, a set of warehouses must be selected within a set of potential locations to serve several customers or demand zones, additionally involving the selection of the suppliers for fulfilling incoming orders from the located warehouses. The optimal solution must be determined while minimizing total system costs including supplier selection, transportation (i.e., supplierswarehouses and warehousescustomers), inventory (i.e., cycle and safety stock), and warehouse location costs. A key element of the problem is the consideration of variable leadtimes for the warehouses, which are dependent on the selection of the supplier that serve them, thus increasing model complexity. Accordingly, an efficient algorithm based on the Generalized Benders Decomposition is developed and implemented to solve the proposed Mixed Integer, Nonlinear, Nonconvex, Programming Model. The proposed solution approach relies on a convenient model formulation and decomposition that yields a Mixed Integer Linear master problem and a continuous, convex subproblem. A wide set of mediumsized synthetic instances are optimally solved in affordable times, denoting the efficiency and effectiveness of the proposed model along with the proposed solution approach. Significant scientific and managerial insights are provided and discussed.
PubDate: 20240124

 Concentration behavior: 50 percent of hextra edge connectivity of
pentanary ncube with exponential faulty edges
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Edge disjoint paths have a closed relationship with edge connectivity and are anticipated to garner increased attention in the study of the reliability and edge fault tolerance of a readily scalable interconnection network. Note that this interconnection network is always modeled as a connected graph G. The minimum of some of modified edgecuts of a connected graph G, also known as the hextra edgeconnectivity of a graph G ( \(\lambda _{h}(G)\) ), is defined as the maximum number of the edge disjoint paths connecting any two disjoint connected subgraphs with h vertices in the graph G. From the perspective of edgecut, the smallest cardinality of a collection of edges, whose removal divides the whole network into several connected subnetworks having at least h vertices, is the hextra edgeconnectivity of the underlying topological architecture of an interconnection network G. This paper demonstrates that the hextra edgeconnectivity of the pentanary ncube ( \(\lambda _{h}(K_{5}^{n})\) ) appears a concentration behavior for around 50 percent of \(h\le \lfloor 5^{n}/2\rfloor \) as n approaches infinity. Let \(e=1\) for n is even and \(e=0\) for n is odd. It mainly concentrates on the value \([4g(\lceil \frac{n}{2}\rceil r)g(g1)]5^{\lfloor \frac{n}{2}\rfloor +r}\) for \(g5^{\lfloor \frac{n}{2}\rfloor +r}\lfloor \frac{[(g1)^{2}+1]5^{2r+e}}{3}\rfloor \le h\le g5^{\lfloor \frac{n}{2}\rfloor +r}\) , where \(r=1, 2,\cdots , \lceil \frac{n}{2}\rceil 2\) , \(g\in \{1, 2,3,4\}\) ; \(r=\lceil \frac{n}{2}\rceil 1\) , \(g\in \{1,2\}\) . Furthermore, it is shown that the above upper bound and lower bound of h are sharp.
PubDate: 20240124

 On the Alon–Tarsi number of semistrong product of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The Alon–Tarsi number was defined by Jensen and Toft (Graph coloring problems, Wiley, New York, 1995). The Alon–Tarsi number AT(G) of a graph G is the smallest integer k such that G has an orientation D with maximum outdegree \(k1\) and the number of even circulation is not equal to that of odd circulations in D. It is known that \(\chi (G)\le \chi _l(G)\le AT(G)\) for any graph G, where \(\chi (G)\) and \(\chi _l(G)\) are the chromatic number and the list chromatic number of G. Denote by \(H_1 \square H_2\) and \(H_1\bowtie H_2\) the Cartesian product and the semistrong product of two graphs \(H_1\) and \(H_2\) , respectively. Kaul and Mudrock (Electron J Combin 26(1):P1.3, 2019) proved that \(AT(C_{2k+1}\square P_n)=3\) . Li, Shao, Petrov and Gordeev (Eur J Combin 103697, 2023) proved that \(AT(C_n\square C_{2k})=3\) and \(AT(C_{2m+1}\square C_{2n+1})=4\) . Petrov and Gordeev (Mosc. J. Comb. Number Theory 10(4):271–279, 2022) proved that \(AT(K_n\square C_{2k})=n\) . Note that the semistrong product is noncommutative. In this paper, we determine \(AT(P_m \bowtie P_n)\) , \(AT(C_m \bowtie C_{2n})\) , \(AT(C_m \bowtie P_n)\) and \(AT(P_m \bowtie C_{n})\) . We also prove that \(5\le AT(C_m \bowtie C_{2n+1})\le 6\) .
PubDate: 20240105

 Optimal investment decision for photovoltaic projects in China: a real
options method
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In an uncertain environment, it is important to investigate whether to postpone, abandon or immediately invest in photovoltaic (PV) projects. This paper applies a real options model to explore the optimal investment decision for investors and the government’s optimal incentive strategy in China’s distributed PV market. The uncertainties of feedin tariffs (FIT) and investment costs are included in this study as critical factors affecting the options value of PV projects. Multiple scenarios are designed from different dimensions, including various subsidy durations, different resource areas, and distinct regulatory policies. The results show that not only the current FIT and investment cost affect the investment choice, but also the potential change trend of FIT and investment cost affect the investor’s preference. The results also reveal that appropriate FIT regulation can effectively induce investors who abandon investment to choose to delay investment, and significantly shorten the delay time. These conclusions can provide valuable insights for investors to optimize investment decisions.
PubDate: 20231124
DOI: 10.1007/s10878023010965

 Capacity decisions and revenue sharing in a telemedicine healthcare system

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper studies the operations of a telemedicine service system consisting of independent hospitals [general hospital (GH) and telemedicine firm (TF)]. Through the healthcare alliance, the GH and the TF collaborate in capacity decisions and revenue sharing, and establish a green channel to refer patients. We adopt a twostage game model to study a revenue sharing scheme of the telemedicine healthcare alliance. In the firststage the game, the GH and the TF negotiate a revenuesharing ratio to distribute the revenue of the referred patients. In the second stage game, given the profitsharing ratio, GH makes capacity allocation decisions, and TF determines its own price to maximize its own revenue. Results show that the revenue sharing scheme can increase profits and promote collaboration between GH and TF. When a large number of mild patients arrive at the GH, the GH tends to participate in the alliance. For the TF, high prices do not always yield high profit under the comprehensive influence of the alliance.
PubDate: 20231124
DOI: 10.1007/s10878023010956

 Methods for determining cycles of a specific length in undirected graphs
with edge weights
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we consider the \({{\mathcal{N}\mathcal{P}}}\) hard problem of determining fixedlength cycles in undirected edgeweighted graphs. Two solution methods are proposed, one based on integer programming (IP) and one that uses bespoke local search operators. These methods are executed under a common algorithmic framework that seeks to partition problem instances into a series of smaller subproblems. Largescale empirical tests indicate that the local search algorithm is generally preferable to IP, even with short run times. However, it can still produce suboptimal solutions, even with relatively small graphs.
PubDate: 20231119
DOI: 10.1007/s1087802301091w

 Algorithmic and complexity aspects of problems related to total restrained
domination for graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Let G be a graph with vertex set V and a subset \(D\subseteq V\) . D is a total dominating set of G if every vertex in V is adjacent to a vertex in D. D is a restrained dominating set of G if every vertex in \(V\setminus D\) is adjacent to a vertex in D and another vertex in \(V\setminus D\) . D is a total restrained dominating set if D is both a total dominating set and a restrained dominating set. The minimum cardinality of total dominating sets (resp. restrained dominating sets, total restrained dominating sets) of G is called the total domination number (resp. restrained domination number, total restrained domination number) of G, denoted by \(\gamma _{t}(G)\) (resp. \(\gamma _{r}(G)\) , \(\gamma _{tr}(G)\) ). The MINIMUM TOTAL RESTRAINED DOMINATION (MTRD) problem for a graph G is to find a total restrained dominating set of minimum cardinality of G. The TOTAL RESTRAINED DOMINATION DECISION (TRDD) problem is the decision version of the MTRD problem. In this paper, firstly, we show that the TRDD problem is NPcomplete for undirected path graphs, circle graphs, SCB graphs and CCB graphs, respectively, and that, for a SCB graph or CCB graph with n vertices, the MTRD problem cannot be approximated within a factor of \((1\epsilon )\textrm{ln} n\) for any \(\epsilon >0\) unless \(NP\subseteq DTIME(n^{O(\textrm{loglog}n)})\) . Secondly, for a graph G, we prove that the problem of deciding whether \(\gamma _{r}(G) =\gamma _{tr}(G)\) is NPhard even when G is restricted to planar graphs with maximum degree at most 4, and that the problem of deciding whether \(\gamma _{t}(G) =\gamma _{tr}(G)\) is NPhard even when G is restricted to planar bipartite graphs with maximum degree at most 5. Thirdly, we show that the MTRD problem is APXcomplete for bipartite graphs with maximum degree at most 4. Finally, we design a lineartime algorithm for solving the MTRD problem for generalized series–parallel graphs.
PubDate: 20231117
DOI: 10.1007/s1087802301090x

 Partial inverse min–max spanning tree problem under the weighted
bottleneck hamming distance
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract 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.
PubDate: 20231116
DOI: 10.1007/s10878023010938

 Bounding the total forcing number of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract 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\setminus S\) no color, if one vertex \(u\in S\) has a unique neighbor v in \(V\setminus 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 \(\delta (G[S])\ge 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 \(\phi (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)\le p(G)+q(G)+2\phi (G)\) . Furthermore, all graphs achieving the equality are determined.
PubDate: 20231116
DOI: 10.1007/s10878023010894

 On decreasing the orders of $$(k,g)$$ graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract A \((k,g)\) graph is a kregular graph of girth \(g\) . Given \(k\ge 2\) and \(g\ge 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 nonisomorphic smallest examples are known to exist, and address the question of the distance between these nonisomorphic examples based on the number of changes required to move from one example to another.
PubDate: 20231116
DOI: 10.1007/s10878023010929

 Dominated coloring in product graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The dominated coloring (domcoloring) of a graph G is a proper coloring such that each color class is dominated by at least one vertex. The dominated chromatic number (domchromatic number) of G is the minimum number of color classes among all dominated colorings of G, denoted by \(\chi _{\text {dom}}(G)\) . In this paper, we study the dominated coloring of Cartesian product, direct product, lexicographic product and strong product of some graphs.
PubDate: 20231110
DOI: 10.1007/s10878023010947

 Minmax for facility location game with optional preference under minimum
distance requirement
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract 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\le d\le 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.
PubDate: 20231101
DOI: 10.1007/s10878023010876

 Semionline early work maximization problems on two hierarchical uniform
machines with partial information of processing time
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we consider four semionline 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 highhierarchy jobs. When the total size of all jobs is known, we design an optimal online algorithm with a competitive ratio of \(\min \{1+s,\frac{2+2s}{1+2s}\}\) . When the total size of lowhierarchy jobs is known, we design an optimal online algorithm with a competitive ratio of \(\min {\{1+s, \frac{\sqrt{9\,s^2+10\,s+1}s1}{2\,s}}\}\) . When the total size of highhierarchy jobs is known, we design an optimal online algorithm with a competitive ratio of \(\min \{\sqrt{s+1}, \sqrt{s^2+2\,s+2}s\}\) . When both the total sizes of lowhierarchy and highhierarchy jobs are known, we give a lower bound \(\frac{2s+2}{s+2}\) for the case \(s\le \frac{2}{3}\) , and an optimal online algorithm with a competitive ratio of \(\frac{3s+3}{3s+2}\) for the case \(s>\frac{2}{3}\) .
PubDate: 20231015
DOI: 10.1007/s10878023010867
