Search

This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting.

Today’s quantum computers are limited in their capabilities, e.g., the size of executable quantum circuits. The Quantum Approximate Optimization Algorithm (QAOA) addresses these limitations and is, therefore, a promising candidate for achieving a near-term quantum advantage. Warm-starting can further improve QAOA by utilizing classically pre-computed approximations to achieve better solutions at a small circuit depth. However, warm-starting requirements often depend on the quantum algorithm and problem at hand. Warm-started QAOA (WS-QAOA) requires developers to understand how to select approach-specific hyperparameter values that tune the embedding of classically pre-computed approximations. In this paper, we address the problem of hyperparameter selection in WS-QAOA for the maximum cut problem using the classical Goemans–Williamson algorithm for pre-computations. The contributions of this work are as follows: We implement and run a set of experiments to determine how different hyperparameter settings influence the solution quality. In particular, we (i) analyze how the regularization parameter that tunes the bias of the warm-started quantum algorithm towards the pre-computed solution can be selected and optimized, (ii) compare three distinct optimization strategies, and (iii) evaluate five objective functions for the classical optimization, two of which we introduce specifically for our scenario. The experimental results provide insights on efficient selection of the regularization parameter, optimization strategy, and objective function and, thus, support developers in setting up one of the central algorithms of contemporary and near-term quantum computing.

A promising approach for efficiently solving NP-hard optimization problems is based on mapping the problems onto Ising machines. Oscillator-based Ising machines can be implemented by utilizing sub-harmonic injection locking, which enables binary phase shifts between the oscillators and leads to an improved reliability of Ising machines. Based on a modified Kuramoto model with sub-harmonic injection locking, we synthesize an ideal electrical circuit displaying the phase dynamics of an Ising machine. The ideal circuit can be utilized to specifically take non-ideal effects into account, serving as a starting point for designing Ising machines with increased performance when considering existing electrical components. We furthermore derive a corresponding wave digital model, which is utilized for emulating the synthesized electrical circuit. The emulation results show that the synthesized circuit indeed models the phase dynamics of an Ising machine capable of solving Max-Cut problems with an accuracy of 88% for a 5-node problem and weights between 0 and 31.

In VLSI physical design, many algorithms require the solution of difficult combinatorial optimization problems such as max/min-cut, max-flow problems etc. Due to the vast number of elements typically found in this problem domain, these problems are computationally intractable leading to the use of approximate solutions. In this work, we explore the Ising spin glass model as a solution methodology for hard combinatorial optimization problems using the general purpose GPU (GPGPU). The Ising model is a mathematical model of ferromagnetism in statistical mechanics. Ising computing finds a minimum energy state for the Ising model which essentially corresponds to the expected optimal solution of the original problem. Many combinatorial optimization problems can be mapped into the Ising model. In our work, we focus on the max-cut problem as it is relevant to many VLSI design automation problems. Our method is inspired by the observation that Ising annealing process is very amenable to fine-grain massive parallel GPU computing. We will illustrate how the natural randomness of GPU thread scheduling can be exploited during the annealing process to create random update patterns and allow better GPU resource utilization. Furthermore, the proposed GPU-based Ising computing can handle any general Ising graph with arbitrary connections, which was shown to be difficult for existing FPGA and other hardware based implementation methods. Numerical results show that the proposed GPU Ising max-cut solver can deliver more than 2000X speedup over the CPU version of the algorithm on some large examples, which shows huge performance improvement for addressing many hard optimization algorithms for solving practical VLSI design automation problems.

The subspace selection problem seeks a subspace that maximizes an objective function under some constraint. This problem includes several important machine learning problems such as the principal component analysis and sparse dictionary selection problem. Often, these problems can be (exactly or approximately) solved using greedy algorithms. Here, we are interested in why these problems can be solved by greedy algorithms, and what classes of objective functions and constraints admit this property.In this study, we focus on the fact that the set of subspaces forms a lattice, then formulate the problems as optimization problems on lattices. Then, we introduce a new class of functions on lattices, directional DR-submodular functions, to characterize the approximability of problems. We prove that the principal component analysis, sparse dictionary selection problem, and these generalizations are monotone directional DRsubmodularity functions. We also prove the “quantum version” of the cut function is a non-monotone directional DR submodular function. Using these results, we propose new solvable feature selection problems (generalized principal component analysis and quantum maximum cut problem), and improve the approximation ratio of the sparse dictionary selection problem in certain instances.We show that, under several constraints, the directional DRsubmodular function maximization problem can be solved efficiently with provable approximation factors.

International audience; Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fractional weight is computed for each cut such that, for each edge, the sum of the weights of all cuts containing it is no less than 1, while the sum of all weights is minimized. The fractional cover is computed for different graph classes among which are the weakly bipartite graphs. Efficient algorithms are described to compute lower and upper bounds with worst-case performance guarantees. A general randomized approach is also presented giving new insights into Goemans and Williamson's algorithm for the maximum cut problem. Some numerical experiments are included to assess the quality of bounds

Every connected graph on n vertices has a cut of size at least n − 1. We call this bound the spanning tree bound. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n − 1 + k. We show that Max-Cut-AST admits an algorithm that runs in time $\mathcal {O}(8^{k}n^{\mathcal {O}(1)})$, and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size $\mathcal {O}(k^{5})$.

The max-cut problem is one of well-known NP-complete problems and has applications in various fields such as the design process for VLSI (Very-Large-Scale Integration) chips and spin glass theory in statistical physics. In this paper, a harmony search algorithm for the max-cut problem is proposed. Compared to genetic algorithm, harmony search algorithm has advantages of generating a new vector after considering all of the existing vectors and requiring only a few number of parameters to be determined before the run of the algorithm. For 31 benchmark graphs of various types, the proposed harmony search algorithm is compared with a newly developed genetic algorithm and another genetic algorithm taken from the recent literature are presented. The proposed harmony search algorithm produced significantly better results than the two genetic algorithms.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. Alon et al. [‘Maximum cuts and judicious partitions in graphs without short cycles’, J. Combin. Theory Ser. B 88 (2003), 329–346] conjectured that, for any fixed graph $H$, there exists an $\unicode[STIX]{x1D716}(H)>0$ such that $f(m,H)\geq m/2+\unicode[STIX]{x1D6FA}(m^{3/4+\unicode[STIX]{x1D716}})$. We show that, for any wheel graph $W_{2k}$ of $2k$ spokes, there exists $c(k)>0$ such that $f(m,W_{2k})\geq m/2+c(k)m^{(2k-1)/(3k-1)}\log m$. In particular, we confirm the conjecture asymptotically for $W_{4}$ and give general lower bounds for $W_{2k+1}$.

We perform a theoretical and computational study of the classical linearisation techniques (LT) and we propose a new LT for binary quadratic problems (BQPs). We discuss the relations between the linear programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the maximum cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance, we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the knapsack and stable set problems.

Frontiers in artificial intelligence 3, 580607 (2021). doi:10.3389/frai.2020.580607, Published by Frontiers Media, Lausanne

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

The max-cut problem addresses the problem of finding a cut for a graph that splits the graph into two subsets of vertices so that the number of edges between these two subsets is as large as possible. However, this problem is NP-Hard, which may be solved by suboptimal algorithms. In this paper, we propose a fast and accurate Riemannian optimization algorithm for solving the max-cut problem. To do so, we develop a gradient descent algorithm and prove its convergence. Our simulation results show that the proposed method is extremely efficient on some already-investigated graphs. Specifically, our method is on average 50 times faster than the best well-known techniques with slightly losing the performance, which is on average 0.9729 of the max-cut value of the others.

Quantum annealers have been designed to propose near-optimal solutions to NP-hard optimization problems. However, the accuracy of current annealers such as the ones of D-Wave Systems, Inc., is limited by environmental noise and hardware biases. One way to deal with these imperfections and to improve the quality of the annealing results is to apply a variety of pre-processing techniques such as spin reversal (SR), anneal offsets (AO), or chain weights (CW). Maximizing the effectiveness of these techniques involves performing optimizations over a large number of parameters, which would be too costly if needed to be done for each new problem instance. In this work, we show that the aforementioned parameter optimization can be done for an entire class of problems, given each instance uses a previously chosen fixed embedding. Specifically, in the training phase, we fix an embedding E of a complete graph onto the hardware of the annealer, and then run an optimization algorithm to tune the following set of parameter values: the set of bits to be flipped for SR, the specific qubit offsets for AO, and the distribution of chain weights, optimized over a set of training graphs randomly chosen from that class, where the graphs are embedded onto the hardware using E. In the testing phase, we estimate how well the parameters computed during the training phase work on a random selection of other graphs from that class. We investigate graph instances of varying densities for the Maximum Clique, Maximum Cut, and Graph Partitioning problems. Our results indicate that, compared to their default behavior, substantial improvements of the annealing results can be achieved by using the optimized parameters for SR, AO, and CW.

Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs., 21 pages, to be published in LATIN 2020 proceedings, Updated version is rewritten to include additional results along with corrections to original arguments

The Quantum Approximate Optimization Algorithm (QAOA) was proposed as a way of finding good, approximate solutions to hard combinatorial optimization problems. QAOA uses a hybrid approach. A parametrized quantum state is repeatedly prepared and measured on a quantum computer to estimate its average energy. Then, a classical optimizer, running in a classical computer, uses such information to decide on the new parameters that are then provided to the quantum computer. This process is iterated until some convergence criteria are met. Theoretically, almost all classical minimizers can be used in the hybrid scheme. However, their behaviour can vary greatly in both the quality of the final solution and the time they take to find it. In this work, we study the performance of twelve different classical optimizers when used with QAOA to solve the maximum cut problem in graphs. We conduct a thorough set of tests on a quantum simulator both, with and without noise, and present results that show that some optimizers can be hundreds of times more efficient than others in some cases.

An independent set S in a graph G is k-swap optimal if there is no independent set \(S'\) such that \(|S'|>|S|\) and \(|(S'\setminus S)\cup (S\setminus S')|\le k\). Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap optimal independent set or in all k-swap optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are \(\mathrm {\Sigma ^{\text {P}}_{2}} \)-hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in \(f(\varDelta +k)\cdot n^{\mathcal {O}(1)}\) time whether it is in some k-optimal path.

We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete., LIPIcs, Vol. 189, 37th International Symposium on Computational Geometry (SoCG 2021), pages 7:1-7:11

In this work, we discuss a strengthening of a result of Furedi that every n-vertex \(K_{r+1}\)-free graph can be made r-partite by removing at most \(T(n,r) - e(G)\) edges, where \(T(n,r)=\frac{r-1}{2r}n^2\) denotes the number of edges of the n-vertex r-partite Turan graph. As a corollary, we answer a problem of Sudakov and prove that every \(K_6\)-free graph can be made bipartite by removing at most \(4n^2/25\) edges. The main tool we use is the flag algebra method applied to locally definied vertex-partitions.

We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of randomized classical algorithms. 1) We prove that every (quantum or classical) one-local algorithm (where the value of a vertex only depends on its and its neighbors' state) achieves on D-regular graphs of girth > 5 a maximum cut of at most 1/2 + C/���D for C = 1/���2 ��� 0.7071. This is the first such result showing that one-local algorithms achieve a value that is bounded away from the true optimum for random graphs, which is 1/2 + P_*/���D + o(1/���D) for P_* ��� 0.7632 [Dembo et al., 2017]. 2) We show that there is a classical k-local algorithm that achieves a value of 1/2 + C/���D - O(1/���k) for D-regular graphs of girth > 2k+1, where C = 2/�� ��� 0.6366. This is an algorithmic version of the existential bound of [Lyons, 2017] and is related to the algorithm of [Aizenman et al., 1987] (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs [M. B. Hastings, 2019; Marwaha, 2021]. 3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random D-regular graphs, as well as other natural instances, including graphs that do have short cycles. While our theoretical bounds require the locality and girth assumptions, our experimental work suggests that it could be possible to extend them beyond these constraints. This points at the tantalizing possibility that O(1)-local quantum maximum-cut algorithms might be pointwise dominated by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality on every possible instance. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 14:1-14:21

The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80’s, being one of the problems proposed by Johnson on his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still not known. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4., LIPIcs, Vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pages 38:1-38:15

This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality. In particular, our paper presents and evaluates the effectiveness of the local-bound (LocB) and rough upper-bound pruning (RUB). LocB is a new and effective rule that leverages the approximate MDD structure to avoid the exploration of non-interesting nodes. RUB is a rule to reduce the search space during the development of bounded-width-MDDs. The experimental study we conducted on the Maximum Independent Set Problem (MISP), Maximum Cut Problem (MCP), Maximum 2 Satisfiability (MAX2SAT) and the Traveling Salesman Problem with Time Windows (TSPTW) shows evidence indicating that rough-upper-bound and local-bound pruning have a high impact on optimization solvers based on branch-and-bound with MDDs. In particular, it shows that RUB delivers excellent results but requires some effort when defining the model. Also, it shows that LocB provides a significant improvement automatically; without necessitating any user-supplied information. Finally, it also shows that rough-upper-bound and local-bound pruning are not mutually exclusive, and their combined benefit supersedes the individual benefit of using each technique.

The paper deals with the max-cut problem for random hypergraphs. We consider a binomial model of a random k-uniform hypergraph H(n, k, p) for some fixed \(k \ge 3\), growing n and \(p=p(n)\). For given natural number q, the max-q-cut for a hypergraph is the maximal possible number of edges that can be properly colored with q colors under the same coloring. Generalizing the known results for graphs we show that in the sparse case (when \(p = cn/\left( {\begin{array}{c}n\\ k\end{array}}\right) \) for some fixed \(c > 0\) not depending on n) there exists a limit constant \(\gamma (c, k, q)\) such that $$ {\text {max-q-cut}(H(n, k,p)) \over n} \overset{\mathsf {P}}{\longrightarrow } \gamma (c, k, q) $$ as \(n \rightarrow +\infty \). We also prove some estimates for \(\gamma (c, k, q)\) of the form \(A_{k, q} \cdot c + B_{k, q} \cdot \sqrt{c} + o(\sqrt{c})\).

The ASPIRE program, which is based on the Landau singularities and the method of power geometry to unveil the regions required for the evaluation of a given Feynman diagram asymptotically in a given limit, also allows for the evaluation of scaling coming from the top facets. In this work, we relate the scaling having equal components of the top facets of the Newton polytope to the maximal cut of given Feynman integrals. We have therefore connected two independent approaches to the analysis of Feynman diagrams., Comment: 34 pages latex, 7 figures and 2 tables, ancillary Mathematica files provided, substantially extended and improved, added new sections(sub-section-2.5, section-3,4,appendix-B), References added, version accepted for publication in EPJC

International audience; We consider the Max-Cut problem on an undirected graph G = (V, E) with |V | = n nodes and |E| = m edges. We investigate a linear size MIP formulation, referred to as (MIP-MaxCut), which can easily be derived via a standard linearization technique. However, the efficiency of the Branchand-Bound procedure applied to this formulation does not seem to have been investigated so far in the literature. Branch-and-bound based approaches for Max-Cut usually use the semi-metric polytope which has either an exponential size formulation consisting of the cycle inequalities or a compact size formulation consisting of O(mn) triangle inequalities [2], [16]. However, optimizing over the semi-metric polytope can be computationally demanding due to the slow convergence of cutting-plane algorithms and the high degeneracy of formulations based on the triangle inequalities. In this paper, we exhibit new structural properties of (MIP-MaxCut) that link the binary variables with the cycle inequalities. In particular, we show that fixing a binary variable at 0 or 1 in (MIP-MaxCut) can result in imposing the integrity of several original variables and the satisfaction of a possibly exponential number of cycle inequalities in the semi-metric formulation. Numerical results show that for sparse instances of Max-Cut, our approach exploiting this capability outperforms the branch-and-cut algorithms based on semi-metric polytope when implemented on the same framework; and even without any extra sophistication, the approach is capable of solving hard instances of Max-Cut within acceptable CPU times. The work is supported by the Programme Gaspard Monge pour Optimisation (PGMO).

The precision of Stage IV cosmic shear surveys will enable us to probe smaller physical scales than ever before, however, model uncertainties from baryonic physics and non-linear structure formation will become a significant concern. The $k$-cut method---applying a redshift-dependent $\ensuremath{\ell}$-cut after making the Bernardeau-Nishimichi-Taruya transform---can reduce sensitivity to baryonic physics; allowing Stage IV surveys to include information from increasingly higher $\ensuremath{\ell}$-modes. Here we address the question of whether it can also mitigate the impact of making the reduced shear approximation; which is also important in the high-$\ensuremath{\kappa}$, small-scale regime. The standard procedure for relaxing this approximation requires the repeated evaluation of the convergence bispectrum, and consequently can be prohibitively computationally expensive when included in Monte Carlo analyses. We find that the $k$-cut cosmic shear procedure suppresses the ${w}_{0}{w}_{a}$ CDM cosmological parameter biases expected from the reduced shear approximation for Stage IV experiments, when $\ensuremath{\ell}$-modes up to 5000 are probed. The maximum cut required for biases from the reduced shear approximation to be below the threshold of significance is at $k=5.37\text{ }\text{ }h\text{ }{\mathrm{Mpc}}^{\ensuremath{-}1}$. With this cut, the predicted $1\ensuremath{\sigma}$ constraints increase, relative to the case where the correction is directly computed, by less than 10% for all parameters. This represents a significant improvement in constraints compared to the more conservative case where only $\ensuremath{\ell}$-modes up to 1500 are probed [A. Blanchard et al., (Euclid Collaboration), arXiv:1910.09273], and no $k$-cut is used. We also repeat this analysis for a hypothetical, comparable kinematic weak lensing survey. The key parts of code used for this analysis are made publicly available.

Advances in quantum annealing technology make it possible to obtain high quality approximate solutions of important NP-hard problems. With the newer generations of the D-Wave annealer, more advanced features are available which allow the user to have greater control of the anneal process. In this contribution, we study how such features can help in improving the quality of the solutions returned by the annealer. Specifically, we focus on two of these features: reverse annealing and h-gain. Reverse annealing (RA) was designed to allow refining a known solution by backward annealing from a classical state representing the solution to a mid-anneal point where a transverse field is present, followed by an ordinary forward anneal, which is hoped to improve on the previous solution. The h-gain (HG) feature stands for time-dependent gain in Hamiltonian linear ($h$) biases and was originally developed to help study freezeout times and phase transitions in spin glasses. Here we apply HG to bias the quantum state in the beginning of the annealing process towards the known solution as in the RA case, but using a different apparatus. We also investigate a hybrid reverse annealing/h-gain schedule, which has a backward phase resembling an RA step and whose forward phase uses the HG idea. To optimize the parameters of the schedules, we employ a Bayesian optimization framework. We test all techniques on a variety of input problems including the weighted Maximum Cut problem and the weighted Maximum Clique problem. Our results show that each technique may dominate the others depending on the input instance, and that the HG technique is a viable alternative to RA for some problems.

Within the scope of this ex vivo study, the cut efficiency was investigated with eight diode laser wavelengths in the range from 400 to 1500 nm. Incisions on porcine gingiva samples were generated in CW-mode at a power range of 0.5–4 W using a bare fiber (∅ = 320 μm) in contact and non-contact mode at a cut speed of 2 mm/s. Cut depths, cut widths, and thermal damages were recorded based on histological sections and were evaluated via measurement masks. Moreover, with respect to the controllability of a therapeutic measure, an efficiency factor was defined. At powers above 2 W, for 445 nm, the maximum cut depth was 820 μm and 344 μm for 810 nm, respectively. At all wavelength and power ranges, the cut width averaged 125 μm. At minimum output power (0.5 W), the spatial expansion of the thermal damage in the tissue surface layer corresponds in the blue/green wavelength range from the very beginning of the laser impact to the fiber core diameter. It could be shown that increases in the diode laser power output do not correlate to the same extent with the incision depth nor with thermal damage to tissue.

The D-Wave quantum annealers make it possible to obtain high quality solutions of NP-hard problems by mapping a problem in a QUBO (quadratic unconstrained binary optimization) or Ising form to the physical qubit connectivity structure on the D-Wave chip. However, the latter is restricted in that only a fraction of all pairwise couplers between physical qubits exists. Modeling the connectivity structure of a given problem instance thus necessitates the computation of a minor embedding of the variables in the problem specification onto the logical qubits, which consist of several physical qubits "chained" together to act as a logical one. After annealing, it is however not guaranteed that all chained qubits get the same value (-1 or +1 for an Ising model, and 0 or 1 for a QUBO), and several approaches exist to assign a final value to each logical qubit (a process called "unembedding"). In this work, we present tailored unembedding techniques for four important NP-hard problems: the Maximum Clique, Maximum Cut, Minimum Vertex Cover, and Graph Partitioning problems. Our techniques are simple and yet make use of structural properties of the problem being solved. Using Erd\H{o}s-R\'enyi random graphs as inputs, we compare our unembedding techniques to three popular ones (majority vote, random weighting, and minimize energy). We demonstrate that our proposed algorithms outperform the currently available ones in that they yield solutions of better quality, while being computationally equally efficient.

Let V be a set of n vertices, M a set of m labels, and let ���� be an m �� n matrix of independent Bernoulli random variables with probability of success p; columns of ���� are incidence vectors of label sets assigned to vertices. A random instance G(V, E, ����^T ����) of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely [����^T ����]_{v,u}) between any two vertices u, v for which this weight is strictly larger than 0. In this paper we study the average case analysis of Weighted Max Cut, assuming the input is a weighted random intersection graph, i.e. given G(V, E, ����^T ����) we wish to find a partition of V into two sets so that the total weight of the edges having exactly one endpoint in each set is maximized. In particular, we initially prove that the weight of a maximum cut of G(V, E, ����^T ����) is concentrated around its expected value, and then show that, when the number of labels is much smaller than the number of vertices (in particular, m = n^��, �� < 1), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case n = m and constant average degree (i.e. p = ��(1)/n), we show that with high probability, a majority type randomized algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we formally prove a connection between the computational problem of finding a (weighted) maximum cut in G(V, E, ����^T ����) and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system �� with incidence matrix ���� (i.e. minimum imbalance over all sets in ��). We exploit this connection by proposing a (weak) bipartization algorithm for the case m = n, p = ��(1)/n that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in a set system with incidence matrix ����. In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in G(V, E, ����^T ����). Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when p = c/n, c < 1., LIPIcs, Vol. 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pages 28:1-28:16

The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most $\smash{\phi n^{O(\sqrt{\log n})}}$, where $n$ is the number of nodes in the graph and $\phi$ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of $\phi n^{O(\log n)}$ by Etscheid and R\"{o}glin. Our result is based on an analysis of long sequences of flips, which shows~that~it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.

Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an ( α , β , δ ) -clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most δ labels, a) every label consists of at most β sets of twin vertices, and b) all the labels together induce a graph with independence number at most α. We show that for every two constants α , δ > 0 the problem is FPT when parameterized by β plus the smallest width of an ( α , β , δ ) -clique-width decomposition.

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach., arXiv admin note: substantial text overlap with arXiv:1902.05345

NP-hard combinatorial optimization problems (COPs) are very expensive to solve with traditional computers. COPs can be mapped to a coupled spin network where the ground state of the system is the solution. We propose a scalable truly coupled CMOS oscillator-based integrated system mimicking a spin network to solve COPs in hardware. Our simple latch-based coupling design finds solutions of max-cut problems with 85%–100% accuracy 104-106 times faster than commercial software running on a CPU.

The Max-cut problem is a well-known combinatorial optimization problem, which has many real-world applications. However, the problem has been proven to be non-deterministic polynomial-hard (NP-hard), which means that exact solution algorithms are not suitable for large-scale situations, as it is too time-consuming to obtain a solution. Therefore, designing heuristic algorithms is a promising but challenging direction to effectively solve large-scale Max-cut problems. For this reason, we propose a unique method which combines a pointer network and two deep learning strategies (supervised learning and reinforcement learning) in this paper, in order to address this challenge. A pointer network is a sequence-to-sequence deep neural network, which can extract data features in a purely data-driven way to discover the hidden laws behind data. Combining the characteristics of the Max-cut problem, we designed the input and output mechanisms of the pointer network model, and we used supervised learning and reinforcement learning to train the model to evaluate the model performance. Through experiments, we illustrated that our model can be well applied to solve large-scale Max-cut problems. Our experimental results also revealed that the new method will further encourage broader exploration of deep neural network for large-scale combinatorial optimization problems.

For a graph G, let f(G) denote the size of the maximum cut in G. The problem of estimating f(G) as a function of the number of vertices and edges of G has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on f(G). We use this approach to find large cuts in graphs with few triangles and in \(K_r\)-free graphs.

In the paper, we present the maximum cut problem as maximization of a non-smooth convex function over polytope which is the convex hull of bases of the polymatroid associated with a submodular function defined on the subsets of node set of a given graph. We also formulate other new models for this problem and give necessary and enough conditions on an optimal solution in terms of network flow.

Decision trees are a widely used method for classification, both by themselves and as the building blocks of multiple different ensemble learning methods. The Max-Cut decision tree involves novel modifications to a standard, baseline model of classification decision tree construction, precisely CART Gini. One modification involves an alternative splitting metric, maximum cut, based on maximizing the distance between all pairs of observations belonging to separate classes and separate sides of the threshold value. The other modification is to select the decision feature from a linear combination of the input features constructed using Principal Component Analysis (PCA) locally at each node. Our experiments show that this node-based localized PCA with the novel splitting modification can dramatically improve classification, while also significantly decreasing computational time compared to the baseline decision tree. Moreover, our results are most significant when evaluated on data sets with higher dimensions, or more classes; which, for the example data set CIFAR-100, enable a 49% improvement in accuracy while reducing CPU time by 94%. These introduced modifications dramatically advance the capabilities of decision trees for difficult classification tasks., 12 pages, 8 figures, 5 tables

Consider the following gap cycle counting problem in the streaming model: The edges of a $2$-regular $n$-vertex graph $G$ are arriving one-by-one in a stream and we are promised that $G$ is a disjoint union of either $k$-cycles or $2k$-cycles for some small $k$; the goal is to distinguish between these two cases. Verbin and Yu [SODA 2011] introduced this problem and showed that any single-pass streaming algorithm solving it requires $n^{1-\Omega(\frac{1}{k})}$ space. This result and the technique behind it -- the Boolean Hidden Hypermatching communication problem -- has since been used extensively for proving streaming lower bounds for various problems. Despite its significance and broad range of applications, the lower bound technique of Verbin and Yu comes with a key weakness that is inherited by all subsequent results: the Boolean Hidden Hypermatching problem is hard only if there is exactly one round of communication and can be solved with logarithmic communication in two rounds. Therefore, all streaming lower bounds derived from this problem only hold for single-pass algorithms. We prove the first multi-pass lower bound for the gap cycle counting problem: Any $p$-pass streaming algorithm that can distinguish between disjoint union of $k$-cycles vs $2k$-cycles -- or even $k$-cycles vs one Hamiltonian cycle -- requires $n^{1-\frac{1}{k^{\Omega(1/p)}}}$ space. As a corollary of this result, we can extend many of previous lower bounds to multi-pass algorithms. For instance, we can now prove that any streaming algorithm that $(1+\epsilon)$-approximates the value of MAX-CUT, maximum matching size, or rank of an $n$-by-$n$ matrix, requires either $n^{\Omega(1)}$ space or $\Omega(\log{(\frac{1}{\epsilon})})$ passes. For all these problems, prior work left open the possibility of even an $O(\log{n})$ space algorithm in only two passes., Comment: Fixed a mistake in one of the technical lemmas, see Section 1.4

In Marketing, the goal is to understand the psychology of the customer in order to maximize sales. A common approach is to combine web semantic, sniffing, historical information of the customer, and machine learning techniques.