We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of e/(e-1) ≈ 1.582. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of 1.373. We complement our result by a lower bound of 1.25 on the best possible deterministic competitive ratio for incremental submodular maximization.

We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry.

Abstract We introduce a framework for incremental–decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized algorithm and a more sophisticated deterministic algorithm, both of which find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimal solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions and functions satisfying the gross substitutes property. Our results show that incremental–decremental maximization is substantially more difficult than incremental maximization.

We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(α,μ)$-approximation is possible, i.e., a solution that with budget $B+α$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $μ$-approximation compared to the optimum solution with budget $B$. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a $(χ,1)$-approximation, where $χ$ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is $(γ,2)$-competitive where $γ$ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a $(γ,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3χ,8)$-approximation and, more generally, a $\smash{\bigl((4\ell - 1)χ, \frac{2^{\ell + 2}}{2^{\ell}-1}\bigr)}$-approximation for every fixed $\ell \in \mathbb{N}$.

Abstract. We consider the problem of maximizing a fractionally subadditive function under an increasing knapsack constraint. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most [Formula: see text], under the assumption that the values of singleton sets are in the range [Formula: see text], and we give a lower bound of [Formula: see text] on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a lower bound of [Formula: see text] and an upper bound of [Formula: see text] for the incremental maximization of classical flows with capacities in [Formula: see text] which is tight for the unit capacity case.

The embedding is an essential step when calculating on the D-Wave machine. In this work, we show the hardness of the embedding problem for all types of currently existing hardware, represented by the Chimera and the derived Pegasus and Zephyr graphs, containing unavailable qubits. We construct certain broken Chimera graphs, where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem is a special case of the embedding problem, this proves the general complexity result for the Chimera graphs. By exploiting the subgraph relation between the Chimera and the derived graphs, the proof is then further extended to the Pegasus graphs and to the Zephyr graphs.

Abstract Developments in numerical simulation of flows and high-performance computing influence one another. More detailed simulation methods create a permanent need for more computational power, while new hardware developments often require changes to the software to exploit new hardware features. This dependency is very pronounced in the case of vector-units which are featured by all modern processors to increase their numerical throughput but require vectorization of the software to be used efficiently. We study the vectorization of a simulation method that exhibits an inherent level of vector-parallelism. This is of particular interest as SIMD operations will hopefully be available with std::simd in a future C++ standard. The simulation method considered here results in the simultaneous solution of multiple sparse linear systems of equations which only differ by their main diagonal and right-hand sides. Such structure arises in the simulation of unsteady flow in turbomachinery by means of a frequency domain approach called harmonic balance.