Subjects -> STATISTICS (Total: 130 journals)
 Showing 1 - 151 of 151 Journals sorted alphabetically Advances in Complex Systems       (Followers: 10) Advances in Data Analysis and Classification       (Followers: 52) Applied Categorical Structures       (Followers: 5) Argumentation et analyse du discours       (Followers: 8) Asian Journal of Mathematics & Statistics       (Followers: 8) AStA Advances in Statistical Analysis       (Followers: 2) Australian & New Zealand Journal of Statistics       (Followers: 13) Biometrical Journal       (Followers: 9) Biometrics       (Followers: 53) British Journal of Mathematical and Statistical Psychology       (Followers: 18) Building Simulation       (Followers: 2) CHANCE       (Followers: 5) Communications in Statistics - Simulation and Computation       (Followers: 9) Communications in Statistics - Theory and Methods       (Followers: 11) Computational Statistics       (Followers: 15) Computational Statistics & Data Analysis       (Followers: 36) Current Research in Biostatistics       (Followers: 8) Decisions in Economics and Finance       (Followers: 15) Demographic Research       (Followers: 14) Engineering With Computers       (Followers: 5) Environmental and Ecological Statistics       (Followers: 7) ESAIM: Probability and Statistics       (Followers: 4) Extremes       (Followers: 2) Fuzzy Optimization and Decision Making       (Followers: 8) Geneva Papers on Risk and Insurance - Issues and Practice       (Followers: 13) Handbook of Numerical Analysis       (Followers: 4) Handbook of Statistics       (Followers: 7) IEA World Energy Statistics and Balances -       (Followers: 2) International Journal of Computational Economics and Econometrics       (Followers: 6) International Journal of Quality, Statistics, and Reliability       (Followers: 17) International Journal of Stochastic Analysis       (Followers: 2) International Statistical Review       (Followers: 12) Journal of Algebraic Combinatorics       (Followers: 3) Journal of Applied Statistics       (Followers: 20) Journal of Biopharmaceutical Statistics       (Followers: 24) Journal of Business & Economic Statistics       (Followers: 40, SJR: 3.664, CiteScore: 2) Journal of Combinatorial Optimization       (Followers: 7) Journal of Computational & Graphical Statistics       (Followers: 21) Journal of Econometrics       (Followers: 84) Journal of Educational and Behavioral Statistics       (Followers: 7) Journal of Forecasting       (Followers: 20) Journal of Global Optimization       (Followers: 7) Journal of Mathematics and Statistics       (Followers: 6) Journal of Nonparametric Statistics       (Followers: 6) Journal of Probability and Statistics       (Followers: 10) Journal of Risk and Uncertainty       (Followers: 33) Journal of Statistical and Econometric Methods       (Followers: 3) Journal of Statistical Physics       (Followers: 12) Journal of Statistical Planning and Inference       (Followers: 7) Journal of Statistical Software       (Followers: 16, SJR: 13.802, CiteScore: 16) Journal of the American Statistical Association       (Followers: 74, SJR: 3.746, CiteScore: 2) Journal of the Korean Statistical Society Journal of the Royal Statistical Society Series C (Applied Statistics)       (Followers: 37) Journal of the Royal Statistical Society, Series A (Statistics in Society)       (Followers: 28) Journal of the Royal Statistical Society, Series B (Statistical Methodology)       (Followers: 40) Journal of Theoretical Probability       (Followers: 3) Journal of Time Series Analysis       (Followers: 16) Journal of Urbanism: International Research on Placemaking and Urban Sustainability       (Followers: 27) Law, Probability and Risk       (Followers: 6) Lifetime Data Analysis       (Followers: 7) Mathematical Methods of Statistics       (Followers: 4) Measurement Interdisciplinary Research and Perspectives       (Followers: 1) Metrika       (Followers: 4) Monthly Statistics of International Trade - Statistiques mensuelles du commerce international       (Followers: 3) Multivariate Behavioral Research       (Followers: 8) Optimization Letters       (Followers: 2) Optimization Methods and Software       (Followers: 5) Oxford Bulletin of Economics and Statistics       (Followers: 34) Pharmaceutical Statistics       (Followers: 15) Queueing Systems       (Followers: 7) Research Synthesis Methods       (Followers: 7) Review of Economics and Statistics       (Followers: 161) Review of Socionetwork Strategies Risk Management       (Followers: 16) Sankhya A       (Followers: 3) Scandinavian Journal of Statistics       (Followers: 9) Sequential Analysis: Design Methods and Applications Significance       (Followers: 7) Sociological Methods & Research       (Followers: 45) SourceOECD Measuring Globalisation Statistics - SourceOCDE Mesurer la mondialisation - Base de donnees statistiques Stata Journal       (Followers: 8) Statistica Neerlandica       (Followers: 1) Statistical Inference for Stochastic Processes       (Followers: 3) Statistical Methods and Applications       (Followers: 6) Statistical Methods in Medical Research       (Followers: 30) Statistical Modelling       (Followers: 18) Statistical Papers       (Followers: 4) Statistics & Probability Letters       (Followers: 13) Statistics and Computing       (Followers: 14) Statistics and Economics Statistics in Medicine       (Followers: 150) Statistics: A Journal of Theoretical and Applied Statistics       (Followers: 12) Stochastic Models       (Followers: 2) Stochastics An International Journal of Probability and Stochastic Processes: formerly Stochastics and Stochastics Reports       (Followers: 2) Structural and Multidisciplinary Optimization       (Followers: 12) Teaching Statistics       (Followers: 8) Technology Innovations in Statistics Education (TISE)       (Followers: 2) TEST       (Followers: 2) The American Statistician       (Followers: 26) The Canadian Journal of Statistics / La Revue Canadienne de Statistique       (Followers: 10) Wiley Interdisciplinary Reviews - Computational Statistics       (Followers: 1)
Similar Journals
 Journal of Combinatorial OptimizationJournal Prestige (SJR): 0.579 Citation Impact (citeScore): 1Number of Followers: 7      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1573-2886 - ISSN (Online) 1382-6905 Published by Springer-Verlag  [2467 journals]
• AHI: a hybrid machine learning model for complex industrial information
systems

Abstract: Abstract A summary of the numerous hybrid machine learning (HML) patterns is provided in this paper, which covers the complete ML lifecycle from model construction to data preparation to training to deployment to ongoing management. As a resource for the primary decision and control of production systems, industrial information systems (IIS) is a major research field in industrial systems management. Industrial and manufacturing methods are being inundated with massive amounts of data due to the increasing use of industrial information systems (IIS). Data management in networked industrial systems is examined in this paper. We recommend hybrid machine learning (HML) patterns for these customers as a stop-gap measure on the road to the cloud. To overcome the missing data problem, we propose using hybrid machine learning (HML) to solve this issue. This challenge has been given a more comprehensive range of possible solutions thanks to advances in machine learning technology. Here, a complex industrial information system based on a hybrid machine learning model (CIIS-HMLM) is proposed to address recovering the sensor’s lost data that failed. Nonlinear data modeling using an intelligent algorithm is discussed in detail. In addition, this presents a method for processing data to ensure uninterrupted service for consumers using HML. We classify many research difficulties related to the effective design and proper implementation of CIIS-HMLM. As a wrap-up, we provide a few ideas for further research on this topic.
PubDate: 2023-01-23

• Smart logistics with IoT-based enterprise management system using global
manufacturing

Abstract: Abstract Smart logistics will encourage replacing manual systems with the Internet of Things (IoT) or automated handling equipment taking care of repetitive tasks in the enterprise management system. Opportunities to address the issues arise from the development of smart logistics. When used with other quantitative analytic tools and techniques, today’s IoT may generate vast amounts of data and reveal intricate correlations between the many transactions represented by that data. Smart logistics can benefit from the inclusion of these features. The complication and variety of consumer orders necessitate a change in warehouse operations. There is a need for real-time data and contextual data on highly tailored orders' large diversity and small batch sizes. To achieve on-time order fulfilment, the synchronization of purchase orders to support production is critical to the frequent changes in customer needs. Order fulfilment suffers as a result of inefficient and erroneous order selection. Computational intelligence techniques are used in the research to provide an advanced data analysis methodology for Industry 4.0’s smart logistics through global manufacturing. Advanced data analysis methods for Industry 4.0’s smart logistics are developed using computational intelligence approaches. However, IoT-SL can increase logistics productivity, picking accuracy, and efficiency based on data obtained from a case firm and is resilient to order unpredictability. Smart contracts, logistics planners, and asset condition monitoring are included in the paper's smart logistics system. A prototype solution is implemented to demonstrate responsibility, traceability, and obligation for asset management across the supply chain by multiple stakeholders participating in a logistics scenario. It is important to look at how IoT technologies are being used in the smart logistics industry from transportation, storage, loading/unloading, carrying, distributed processing and information transfer, thereby achieving real-time monitoring, increased logistics productivity, logistics management, increased delivery of goods and efficiency of 98.3%.
PubDate: 2023-01-19

• ARX and ARMAX modelling of SBCNC-60 machine for surface roughness and MRR
with optimization of system response using PSO

Abstract: Abstract In the process of attaining high-end machines, control of machining systems via optimized machining parameters along with their transient responses is highly essential. By implementing system detection methodologies, a new methodology is proposed to introduce the best mathematical model, which subsumes the best FIT, fewer parameters, minimum MSE, and residuals amongst ARX and ARMAX models for an SBCNC-60 Machine to gratify the controller’s design requirement. From the CNC machine, the real-time measurement data samples are obtained for model detection; then, they are simulated with the aid of MATLAB. Here, for the study of Metal Removal Rate (MRR), the multiple inputs with the single-output system are utilized; similarly, for tuning operation, the Surface Roughness (SR) is measured; subsequently, the MRR is utilized for drilling operation on P8 (H-13, High-Speed-Steels) materials, which were detected by ARX and ARMAX for varying orders. To optimize the output MRR, the best-fit models were selected for control regarding the PID as well as FOPID controller; moreover, in the ‘3’ inputs’ SR, one input differs at a time whilst retaining the other 2 constants at their mid-levels. Better time-domain characteristics were obtained by the PSO tuned FOPID controlled ARX 331 model than the PSO-PID controller for MRR (tr = 6.86 s., Mp = 1.94%, ts = 8.93 s.) and SR (tr = 1.13 s., Mp = 2.47%, ts = 2.68 s.) in case of turning operation, the ARX 311 is the best-suited model for MRR (tr = 0.0818 s., Mp = 1.8%, ts = 2.78 s.) while running for drilling operation. A prominent effect of the varied cutting speed input variable was illustrated by these models; thus, affecting the output performance like MRR and SR for various operations performed during the machining process.
PubDate: 2023-01-19

• On streaming algorithms for maximizing a supermodular function plus a
MDR-submodular function on the integer lattice

Abstract: Abstract In this paper, we provide a streaming algorithm for the problem of maximizing the sum of a supermodular function and a nonnegative monotone diminishing return submodular (MDR-submodular) function with a knapsack constraint on the integer lattice. Inspired by the SIEVE-STREAMING algorithm, we present a two-pass streaming algorithm by using the threshold technique. Then, we improve the two-pass streaming algorithm to one-pass and further reduce its space complexity. The proposed algorithms are proved to have polynomial time and space complexity, and a performance guarantee dependent on the curvature of the supermodular function. Finally, we carry out numerical experiments to verify the performance of the algorithm.
PubDate: 2023-01-17

• Two approximation algorithms for maximizing nonnegative weakly monotonic
set functions

Abstract: Abstract Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns characteristic. This paper studies the problem of maximizing weakly-monotone non-submodular non-negative set functions without constraints, and extends the normal submodular ratio to weakly-monotone submodular ratio $$\widehat{\gamma }$$ . In this paper, two algorithms are given for the above problems. The first one is a deterministic greedy approximation algorithm, which realizes the approximation ratio of $$\frac{\widehat{\gamma }}{\widehat{\gamma }+2}$$ . When $$\widehat{\gamma }=1$$ , the approximate ratio is 1/3, which matches the ratio of the best deterministic algorithm known for the maximization of submodular function without constraints. The second algorithm is a random greedy algorithm, which improves the approximation ratio to $$\frac{\widehat{\gamma }}{\widehat{\gamma }+1}$$ . When $$\widehat{\gamma }=1$$ , the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions.
PubDate: 2023-01-11

• The mechanism and test of the impact of environmental regulation and
technological innovation on high quality development

Abstract: Abstract Environmental regulation and technological innovation are two important measures to realize high-quality economic development under the current "double cycle" new development pattern in our country. Exploring the mechanism of environmental regulation and technological innovation on high-quality economic development is of great significance to realize high-quality economic development. Firstly, analyze the theoretical mechanism that technological innovation and environmental regulation affect the high-quality development of economy, and put forward the theoretical hypothesis that technological innovation, environmental regulation and their interaction items can promote the high-quality development of economy; Secondly, construct the measurement index system of the high-quality development level of economy based on the new development concept, measure the high-quality development level of economy, and find that the high-quality development level of economy in the whole country is on the rise year by year, with great differences between regions, it presents the characteristics of the eastern region > the central region > the western region; Once again, the fixed effect model is adopted to explore the impact of environmental regulation and technological innovation on high-quality economic development at the national level and the eastern, central and western regions. The results show that environmental regulation and technological innovation not only have independent effect, but also have synergistic effect of mutual promotion on high-quality economic development, and the impact of the two on high-quality economic development has regional heterogeneity. At last, some countermeasures and suggestions are put forward: increase the investment in technological innovation, improve the backward effect of environmental regulations on high-quality economic development, at the same time, pay attention to the coordinated development of environmental regulations and technological innovation, and promote high-quality economic development in both ways.
PubDate: 2023-01-10

• Cycle-connected mixed graphs and related problems

Abstract: Abstract In this paper, motivated by applications of vertex connectivity of digraphs or graphs, we consider the cycle-connected mixed graph (CCMG, for short) problem, which is in essence different from the connected mixed graph (CMG, for short) problem, and it is modelled as follows. Given a mixed graph $$G=(V,A\cup E)$$ , for each pair $$\{u, v\}$$ of two distinct vertices in G, we are asked to determine whether there exists a mixed cycle C in G to contain such two vertices u and v, where C passes through its arc (x, y) along the direction only from x to y and its edge xy along one direction either from x to y or from y to x. Particularly, when the CCMG problem is specialized to either digraphs or graphs, we refer to the related version of the CCMG problem as either the cycle-connected digraph (CCD, for short) problem or the cycle-connected graph (CCG, for short) problem, respectively, where such a graph in the CCG problem is called as a cycle-connected graph. Similarly, we consider the weakly cycle-connected (in other words, circuit-connected) mixed graph (WCCMG, for short) problem, only substituting a mixed circuit for a mixed cycle in the CCMG problem. Moreover, given a graph $$G=(V,E)$$ , we define the cycle-connectivity $$\kappa _c(G)$$ of G to be the smallest number of vertices (in G) whose deletion causes the reduced subgraph either not to be a cycle-connected graph or to become an isolated vertex; Furthermore, for each pair $$\{s, t\}$$ of two distinct vertices in G, we denote by $$\kappa _{sc}(s,t)$$ the maximum number of internally vertex-disjoint cycles in G to only contain such two vertices s and t in common, then we define the strong cycle-connectivity $$\kappa _{sc}(G)$$ of G to be the smallest of these numbers $$\kappa _{sc}(s,t)$$ among all pairs $$\{s, t\}$$ of distinct vertices in G. We obtain the following three results. (1) Using a transformation from the directed 2-linkage problem, which is NP-complete, to the CCD problem, we prove that the CCD problem is NP-complete, implying that the CCMG problem still remains NP-complete, and however, we design a combinatorial algorithm in time $$O(n^2m)$$ to solve the CCG problem, where n is the number of vertices and m is the number of edges of a graph $$G=(V,E)$$ ; (2) We provide a combinatorial algorithm in time O(m) to solve the WCCMG problem, where m is the number of edges of a mixed graph $$G=(V,A\cup E)$$ ; (3) Given a graph $$G=(V,E)$$ , we present twin combinatorial algorithms to compute cycle-connectivity $$\kappa _c(G)$$ and strong cycle-connectivity $$\kappa _{sc}(G)$$ , respectively.
PubDate: 2023-01-10

• Online scheduling of two-machine flowshop with lookahead and incompatible
job families

Abstract: Abstract This paper considers online scheduling on two unit flowshop machines, which there exists unbounded parallel-batch scheduling with incompatible job families and lookahead intervals. The unit flowshop machine means that the processing time of any job on each machine is unit processing time. The objective is to minimize the maximum completion time. The lookahead model means that an online algorithm can foresee the information of all jobs arriving in time interval $$(t,t+\beta ]$$ at time t. There exist incompatible job families, that is, jobs belonging to different families cannot be processed in the same batch. In this paper, we address the lower bound of the proposed problem, and provide a best possible online algorithm of competitive ratio $$1+\alpha _f$$ for $$0\le \beta <1$$ , where $$\alpha _f$$ is the positive root of the equation $${(f+1)} \alpha ^{2}+(\beta +2) \alpha +\beta -f=0$$ and f is the number of incompatible job families which is known in advance.
PubDate: 2023-01-09

• Combinatorial approximation algorithms for the maximum bounded connected
bipartition problem

Abstract: Abstract In this paper, we study the maximum bounded connected bipartition problem: given a vertex-weighted connected graph $$G=(V,E;w)$$ and an upper bound B, the vertex set V is partitioned into two subsets $$(V_1,V_2)$$ such that the total weight of the two subgraphs induced by $$V_1$$ and $$V_2$$ is maximized, and these subgraphs are connected, where the weight of a subgraph is the minimum of B and the total weight of all vertices in the subgraph. In this paper, we prove that this problem is NP-hard even when G is a completed graph, a grid graph with only 3 rows or an interval graph, and we present an $$\frac{8}{7}$$ -approximation algorithm. In particular, we present a $$\frac{14}{13}$$ -approximation algorithm for the case of grid graphs, and we present a fully polynomial-time approximation scheme for the case of interval graphs.
PubDate: 2023-01-09

• On parameterized approximation algorithms for balanced clustering

Abstract: Abstract Balanced clustering is a frequently encountered problem in applications requiring balanced class distributions, which generalizes the standard clustering problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. It was known that both the problems of balanced k-means and k-median are W[2]-hard if parameterized by k, implying that the existences of FPT(k)-time exact algorithms for these problems are unlikely. In this paper, we give FPT(k)-time $$(9+\epsilon )$$ -approximation and $$(3+\epsilon )$$ -approximation algorithms for balanced k-means and k-median respectively, improving upon the previous best approximation ratios of $$86.9+\epsilon$$ and $$7.2+\epsilon$$ obtained in the same time. Our main technical contribution and the crucial step in getting the improved ratios is a different random sampling method for selecting opened facilities.
PubDate: 2023-01-08

• Modeling the relationship between fairness concern and customer loyalty in
dual distribution channel

Abstract: Abstract With the rapid growth of the online market, the e-tailer platform has accumulated loyal consumers, which has caused e-tailers to be more concerned about fairness, especially by paying more attention to manufacturers’ profits earned from the e-commerce platform. We build a dual-channel model and consider whether an e-tailer and manufacturer should be fair minded. We find that the platform will care about fairness only when the proportion of loyal customers is at a medium level. When the proportion of loyal customers is greater, whether e-tailers are fair minded will make no difference. Given that the e-tailer cares about fairness, the manufacturer will also be fair-minded when there is a moderate proportion of loyal customers. When the proportion of loyal customers is greater, the manufacturer will not be fair minded. When only the e-tailer is concerned about fairness, the loyal consumer will be worse off if there is a larger proportion of loyal consumers, and a case where both the e-tailer and manufacturer care about fairness shows the opposite trend. When only the e-tailer is concerned about fairness, the normal consumer will always be better off. When both supply chain members care about fairness, the normal consumer will be worse off if the proportion of loyal consumers is greater.
PubDate: 2023-01-07

• Injective edge coloring of sparse graphs with maximum degree 5

Abstract: Abstract A k-injective-edge coloring of a graph G is a mapping $$c:E(G)\rightarrow \{1,2,\cdots ,k\}$$ such that $$c(e_1)\ne c(e_3)$$ for any three consecutive edges $$e_1,e_2,e_3$$ of a path or a 3-cycle. $$\chi _{i}'(G)=\min \{k G$$ has a k-injective-edge coloring $$\}$$ is called the injective chromatic index of G. In this paper, we prove that for graphs G with $$\Delta (G)\le 5$$ , (1) $$\chi _{i}'(G)\le 8$$ if $$mad(G)<\frac{7}{3}$$ ; (2) $$\chi _{i}'(G)\le 9$$ if $$mad(G)<\frac{12}{5}$$ ; (3) $$\chi _{i}'(G)\le 10$$ if $$mad(G)<\frac{5}{2}$$ ; (4) $$\chi _{i}'(G)\le 11$$ if $$mad(G)<\frac{18}{7}$$ .
PubDate: 2023-01-07

• The r-dynamic chromatic number of planar graphs without 4-,5-cycles

Abstract: Abstract Let G be a graph and k, r be two positive integers. A (k, r)-dynamic coloring $$\varphi$$ of G is a proper k-coloring such that $$\mid \varphi (N_{G}(v))\mid \ge$$ $$\min \{d_{G}(v),r\}$$ for each $$v\in V(G)$$ . In this paper, we prove that the r-dynamic chromatic number of planar graphs without 4-,5-cycles, and intersecting 3-cycles is at most $$r+3$$ if $$r\ge 14$$ .
PubDate: 2023-01-07

• Polynomial time algorithm for k-vertex-edge dominating problem in interval
graphs

Abstract: Abstract Let G be a connected interval graph with n vertices and m edges. For any positive integer k and any subset S of E(G), we design an $$O(k S +m)$$ time algorithm to find a minimum k-vertex-edge dominating set of G with respect to S. This shows that the vertex-edge domination problem and the double vertex-edge domination problem can be solved in linear time. Furthermore, the k-vertex-edge domination problem can also be solved in O(km) time algorithm in interval graphs. Finally, we present a linear time algorithm to solve the independent vertex-edge domination problem for unit interval graphs.
PubDate: 2023-01-06

• A polyhedral approach to least cost influence maximization in social
networks

Abstract: Abstract The least cost influence maximization problem aims to determine minimum cost of partial (e.g., monetary) incentives initially given to the influential spreaders on a social network, so that these early adopters exert influence toward their neighbors and prompt influence propagation to reach a desired penetration rate by the end of cascading processes. We first conduct polyhedral analysis on a substructure that describes influence propagation assuming influence weights are unequal, linear and additively separable. Two classes of facet-defining inequalities based on a mixed 0–1 knapsack set contained in this substructure are proposed. We characterize another exponential class of valid and facet-defining inequalities utilizing the concept of minimum influencing subset. We show that these inequalities can be separated in polynomial time efficiently. Furthermore, a polynomial-time dynamic programming recursion is presented to solve this problem on a simple cycle graph. For arbitrary graphs, we propose a new exponential class of valid inequalities that dominates the cycle elimination constraints and an efficient separation algorithm for them. A compact convex hull description for a special case is presented. We illustrate the effectiveness of these inequalities via a delayed cut generation algorithm in the computational experiments.
PubDate: 2023-01-04

• Approximation algorithms for the lower bounded correlation clustering
problem

Abstract: Abstract Lower bounded correlation clustering problem (LBCorCP) is a new generalization of the correlation clustering problem (CorCP). In the LBCorCP, we are given an integer L and a complete labelled graph. Each edge in the graph is either positive or negative based on the similarity of its two endpoints. The goal is to find a clustering of the vertices, each cluster contains at least L vertices, so as to minimize the sum of the number of positive cut edges and negative uncut edges. In this paper, we first introduce the LBCorCP and give three algorithms for this problem. The first algorithm is a random algorithm, which is designed for the instances of the LBCorCP with fewer positive edges. The second one is that we let the set V itself as a cluster and prove that the algorithm works well on two specially instances with fewer negative edges. The last one is an LP-rounding based iterative algorithm, which is also provided for the instances with fewer negative edges. The above three algorithms can quickly solve some special instances in polynomial time and obtain a smaller approximation ratio. In addition, we conduct simulations to evaluate the performance of our algorithms.
PubDate: 2022-12-31

• An optimal streaming algorithm for non-submodular functions maximization
on the integer lattice

Abstract: Abstract Submodular optimization problem has been concerned in recent years. The problem of maximizing submodular and non-submodular functions on the integer lattice has received a lot of recent attention. In this paper, we study streaming algorithms for the problem of maximizing a monotone non-submodular functions with cardinality constraint on the integer lattice. For a monotone non-submodular function $$f:{\textbf {Z}}^{n}_{+}\rightarrow {\textbf {R}}_{+}$$ defined on the integer lattice with diminishing-return (DR) ratio $$\gamma$$ , we present a one pass streaming algorithm that gives a $$(1-\frac{1}{2^{\gamma }}-\epsilon )$$ -approximation, requires at most $$O(k\epsilon ^{-1}\log {k/\gamma })$$ space and $$O(\epsilon ^{-1}\log {k/\gamma }\cdot$$ $$\log {\Vert {\textbf {B}}\Vert _{\infty }})$$ update time per element. We then modify the algorithm and improve the memory complexity to $$O(\frac{k}{\gamma \epsilon })$$ . To the best of our knowledge, this is the first streaming algorithm on the integer lattice for this constrained maximization problem.
PubDate: 2022-12-29

• Envy-freeness and relaxed stability: hardness and approximation algorithms

Abstract: Abstract We consider the problem of computing matchings under two-sided preferences in the presence of lower as well as upper-quota requirements for the resources. In the presence of lower-quotas a feasible matching may not exist and hence we focus on critical matchings. Informally, a critical matching achieves the smallest deficiency. We first consider two well-studied notions of optimality with respect to preferences, namely stability and envy-freeness. There exist instances that do not admit a critical stable matching or a critical envy-free matching. When critical matching satisfying the optimality criteria does not exist, we focus on computing a minimum-deficiency matching among all stable or envy-free matchings. To ensure guaranteed existence of an optimal critical matching, we introduce and study a new notion of optimality, namely relaxed stability. We show that every instance admits a critical relaxed stable matching and it can be efficiently computed. We then investigate the computational complexity of computing maximum size optimal matchings with smallest deficiency. Our results show that computing a maximum size minimum-deficiency envy-free matching and a maximum size critical relaxed stable matching are both hard to approximate within $$\frac{21}{19}-\epsilon$$ , for any $$\epsilon > 0$$ unless P = NP. For envy-free matchings, we present an approximation algorithm for general instances and a polynomial time exact algorithm for a special case. For relaxed stable matchings, we present a constant factor approximation algorithm for general instances.
PubDate: 2022-12-27

• Proper orientation, proper biorientation and semi-proper orientation
numbers of graphs

Abstract: Abstract An orientation D of G is proper if for every $$xy\in E(G)$$ , we have $$d^-_D(x)\ne d^-_D(y)$$ . An orientation D is a p-orientation if the maximum in-degree of a vertex in D is at most p. The minimum integer p such that G has a proper p-orientation is called the proper orientation number pon(G) of G [introduced by Ahadi and Dehghan (Inf Process Lett 113:799–803, 2013)]. We introduce a proper biorientation of G, where an edge xy of G can be replaced by either arc xy or arc yx or both arcs xy and yx. Similarly to pon(G), we can define the proper biorientation number pbon(G) of G using biorientations instead of orientations. Clearly, $$\textrm{pbon}(G)\le \textrm{pon}(G)$$ for every graph G. We compare pbon(G) with pon(G) for various classes of graphs. We show that for trees T,  the tight bound $$\textrm{pon}(T)\le 4$$ extends to the tight bound $$\textrm{pbon}(T)\le 4$$ and for cacti G, the tight bound $$\textrm{pon}(G)\le 7$$ extends to the tight bound $$\textrm{pbon}(G)\le 7.$$ We also prove that there is an infinite number of trees T for which $$\textrm{pbon}(T)< \textrm{pon}(T).$$ Let (H, w) be a weighted digraph with a weight function $$w: A(H)\rightarrow {\mathbb {Z}}_+.$$ The in-weight $$w^-_H(v)$$ of a vertex v of H is the sum of the weights of arcs towards v. A semi-proper p-orientation (D, w) of an undirected graph G is an orientation D of G together with a weight function $$w: A(D)\rightarrow {\mathbb {Z}}_+$$ , such that the in-weight of any adjacent vertices are distinct and $$w^-_D(v)\le p$$ for every $$v\in V(D)$$ . The semi-proper orientation number spon(G) of a graph G (introduced by Dehghan and Havet in 2021) is the minimum p such that G has a semi-proper p-orientation (D, w) of G. We prove that $$\textrm{spon}(G)\le \textrm{pbon}(G)$$ and characterize graphs G for which $$\textrm{spon}(G)= \textrm{pbon}(G).$$
PubDate: 2022-12-27

• Computing densest k-subgraph with structural parameters

Abstract: Abstract Densest k-Subgraph is the problem to find a vertex subset S of size k such that the number of edges in the subgraph induced by S is maximized. In this paper, we show that Densest k-Subgraph is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distance-hereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a 2-approximation $$2^{{{\texttt{tc}}(G)}/2}n^{O(1)}$$ -time algorithm where $${{\texttt{tc}}(G)}$$ is the twin cover number of an input graph G.
PubDate: 2022-12-23

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762