A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

We give a $(2+?)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).     

Orienteering for electioneering

In this paper, we introduce a combinatorial optimization problem that models the investment decision a political candidate faces when treating his or her opponents’ campaign plans as given. Our formulation accounts for both the time cost of traveling between districts and the time expended while campaigning within districts. We describe a polynomial-time algorithm that computes a $(2+?)$-approximation to the optimal solution of a discrete version of our problem by reducing the problem to another combinatorial optimization problem known as Orienteering.     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

Further results on (v,4,1)-perfect difference families

In this paper, it is shown that an ASP$(2r+1,3)$ exists for $2\le r\le 100$ and $r\ne 4,5$. The existence of a $(v,4,1)$-PDF is investigated by taking advantage of the relationship between ASPs and perfect difference families (PDFs). It is proved that a $(12t+1,4,1)$-PDF exists for $t\le 100$ and $t\ne 2,3$. Several recursive constructions for ASPs and PDFs are also presented. As a consequence, the existence results of an optimal $(v,4,1)$-OOC is updated.     

Lower bounds for the Hilbert number of polynomial systems

Let $H(m)$ denote the maximal number of limit cycles of polynomial systems of degree m. It is called the Hilbert number. The main part of Hilbert?s 16th problem posed in 1900 is to find its value. The problem is still open even for $m=2$. However, there have been many interesting results on the lower bound of it for $m?2$. In this paper, we give some new lower bounds of this number. The results obtained in this paper improve all existing results for all $m?7$ based on some known results for $m=3,4,5,6$. In particular, we obtain that $H(m)$ grows at least as rapidly as $\frac{1}{2\ln 2}{(m+2)}^2\ln (m+2)$ for all large m.     

Tighter approximation bounds for LPT scheduling in two special cases

$Q||C_{\max }$ denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of $Q||C_{\max }$ are considered: case I, when $m?1$ machine speeds are equal, and there is only one faster machine; and case II, when machine speeds are all powers of 2 (2-divisible machines). Case I has been widely studied in the literature, while case II is significant in an approach to design so called monotone algorithms for the scheduling problem.We deal with the worst case approximation ratio of the classic list scheduling algorithm ‘Largest Processing Time (LPT)’. We provide an analysis of this ratio $\mathit{Lpt}/\mathit{Opt}$ for both special cases: For ‘one fast machine’, a tight bound of $(\sqrt{3}+1)/2\approx 1.3660$ is given. For 2-divisible machines, we show that in the worst case $1.3673<\mathit{Lpt}/\mathit{Opt}<1.4$. Besides, we prove another lower bound of $955/699>(\sqrt{3}+1)/2$ when LPT breaks ties arbitrarily.To our knowledge, the best previous lower and upper bounds were $(4/3,3/2?1/2m]$ in case I [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166], respectively $[4/3?1/3m,3/2]$ in case II [R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17 (1969) 416–429; A. Kovács, Fast monotone 3-approximation algorithm for scheduling related machines, in: Proc. 13th Europ. Symp. on Algs. (ESA), in: LNCS, vol. 3669, Springer, 2005, pp. 616–627]. Moreover, Gonzalez et al. conjectured the lower bound 4/3 to be tight in the ‘one fast machine’ case [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166].     

Improved degree conditions for Hamiltonian properties

In 1980, Bondy proved that for an integer $k\ge 2$ a $(k+s)$-connected graph of order $n\ge 3$ is traceable ($s=?1$) or Hamiltonian ($s=0$) or Hamiltonian-connected ($s=1$) if the degree sum of every set of $k+1$ pairwise nonadjacent vertices is at least $\frac{1}{2}((k+1)(n+s?1)+1)$. This generalizes the well-known sufficient conditions of Dirac ($k=0$) and Ore ($k=1$). The condition in Bondy’s Theorem is not tight for $k\ge 2$. We improve this sufficient degree condition and show the general tightness of this result.