Abstracts:In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines.

Abstracts:The yolk and the finagle point are two well-known solution concepts in spatial voting games without a core. No relationship between them has been rigorously established in the literature. We prove that every finagle point must be within 2.32472 yolk radii of every yolk center, in all dimensions. This result tightens and generalizes a claimed bound of 2.5 for two dimensions. The bound applies to all points with finagle radius less than the yolk radius. If the finagle radius is half the yolk radius, the bound decreases to 1.7607.

Abstracts:We consider the problem of finding a minimum-size hitting set in a range space F=(Q,R) defined by a measure on a family of subsets of an infinite set R. We observe that, under reasonably general assumptions, the infinite-dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any δ>0, a set of size O(αFzF⁎) that hits a (1−δ)-fraction of the ranges in R (with respect to the given measure) in time proportional to log⁡1δ, where zF⁎ is the value of the fractional optimal solution and αF is the integrality gap of the standard LP relaxation of the hitting set problem for the restriction of F on a set of points of size O(zF⁎log⁡1δ). Some applications of this result in Computational Geometry are given.

Abstracts:A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.

Abstracts:A measure for the flexibility of a Home-Away Pattern set (HAP-set) is the width. The width of a HAP-set equals the size of the largest set of schedules compatible with the HAP-set, for which no match is scheduled in the same round in any two schedules. We prove lower and upper bounds on the width, and identify HAP-sets with largest possible width when the number of teams is a power of 2.

Abstracts:We present a spectral algorithm based on the convex combination of two modified spectral coefficients for solving systems of nonlinear equations. The proposed algorithm does not require the exact or approximated directional derivative for its implementation. By employing a derivative-free line search, the global convergence of the sequence generated by the algorithm is supported. Numerical experiments are given to demonstrate the performance of the algorithm compared with a similar algorithm in the literature for solving nonlinear equations problems.

Abstracts:Recent research has shown that very large convex transportation problems can be solved efficiently with interior point methods by finding a good pre-conditioner for an iterative linear-equation solver. In this article, it is demonstrated that the specific structure of the constraints allows use of a direct method for solving those linear equations with the same order of worst-case time complexity.

Abstracts:We study the multiple Hamiltonian path problem (MHPP) defined on a complete undirected graph G with n vertices. The edge weights of G are non-negative and satisfy the triangle inequality. The MHPP seeks to find a collection of k paths with exactly one visit to each vertex of G with the minimum total edge weight, where endpoints of the paths are not prefixed. We present a 3/2-approximation algorithm for MHPP with time complexity O(n3) for arbitrary k≥1.

Abstracts:Given a set of n points in R3, the minimum-width cubic shell problem asks to find a thinnest cubic shell that encloses the input points, where a cubic shell refers to as a closed volume between two concentric axis-aligned cubes. In this paper, we improve the previous O(nlog2⁡n)-time algorithm presented in Bae (2019) [6] to O(nlog⁡n) worst-case time. This is the first optimal-time algorithm to the problem.

Abstracts:In Nurse Rostering problems the goal is to assign nurses to shifts, subject to a number of constraints. In this paper we consider the computational complexity of such problems. We review the major complexity results obtained so far and show that a problem with coverage constraints, day off requests, and forbidden sequences of shifts of length 2 is NP-hard in the strong sense, even if there are only three work shifts and a day off shift involved.