Search

One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to $\frac43$. For 40 years, the best known upper bound was 1.5, due to Wolsey (1980). Recently, Karlin, Klein, and Oveis Gharan (2022) showed that the max entropy algorithm for the TSP gives an improved bound of $1.5 - 10^{-36}$. In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.

This paper revisits the 2-approximation algorithm for $k$-MST presented by Garg in light of a recent paper of Paul et al.. In the $k$-MST problem, the goal is to return a tree spanning $k$ vertices of minimum total edge cost. Paul et al. extend Garg's primal-dual subroutine to improve the approximation ratios for the budgeted prize-collecting traveling salesman and minimum spanning tree problems. We follow their algorithm and analysis to provide a cleaner version of Garg's result. Additionally, we introduce the novel concept of a kernel which allows an easier visualization of the stages of the algorithm and a clearer understanding of the pruning phase. Other notable updates include presenting a linear programming formulation of the $k$-MST problem, including pseudocode, replacing the coloring scheme used by Garg with the simpler concept of neutral sets, and providing an explicit potential function., Comment: Proceedings of SIAM Symposium on Simplicity in Algorithms (SOSA) 2023

A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite significant efforts, the conjecture remains open. We consider the half-integral case, in which the LP has solution values in $\{0, 1/2, 1\}$. Such instances have been conjectured to be the most difficult instances for the overall four-thirds conjecture. Karlin, Klein, and Oveis Gharan, in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993. This result led to the first significant progress on the overall conjecture in decades; the same authors showed the integrality gap is at most $1.5- 10^{-36}$ in the non-half-integral case. For the half-integral case, the current best-known ratio is 1.4983, a result by Gupta et al. With the improvements on the 3/2 bound remaining very incremental even in the half-integral case, we turn the question around and look for a large class of half-integral instances for which we can prove that the 4/3 conjecture is correct. The previous works on the half-integral case perform induction on a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to "cycle cuts" and the others to "degree cuts". We show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the half-integral LP solution; sampling from the distribution gives us a randomized 4/3-approximation algorithm. We note that the known bad cases for the integrality gap have a gap of 4/3 and have a half-integral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight., Comment: Comments, questions, and suggestions are welcome!

The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many algorithms courses. While the Simplex algorithm relies on intuitive geometric ideas, the computationally-involved mechanics of the algorithm can obfuscate a geometric understanding. In this paper, we present gilp, an easy-to-use Simplex algorithm visualization tool designed to explicitly connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library with example visualizations, and our tool allows an instructor to quickly produce custom interactive HTML files for students to experiment with the algorithm (without requiring students to install anything!). The tool can also be used for interactive assignments in Jupyter notebooks, and has been incorporated into a forthcoming Data Science and Decision Making interactive textbook. In this paper, we first describe how the tool fits into the existing literature on algorithm visualizations: how it was designed to facilitate student engagement and instructor adoption, and how it substantially extends existing algorithm visualization tools for Simplex. We then describe the development and usage of the tool, and report feedback from its use in a course with roughly 100 students. Student feedback was overwhelmingly positive, with students finding the tool easy to use: it effectively helped them link the algebraic and geometrical views of the Simplex algorithm and understand its nuances. Finally, gilp is open-source, includes an extension to visualizing linear programming-based branch and bound, and is readily amenable to further extensions., Comment: ACM SIGCSE 2023 Manuscript, 12 pages, 6 figures

The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of the input, remarkably little is known about the symmetric circulant TSP, and the complexity of the problem has been an often-cited open question. Considerable effort has been made to understand the case in which only edges of two lengths are allowed to have finite cost: the two-stripe symmetric circulant TSP. In this paper, we resolve the complexity of the two-stripe symmetric circulant TSP. To do so, we reduce two-stripe symmetric circulant TSP to the problem of finding certain minimum-cost Hamiltonian paths on cylindrical graphs. We then solve this Hamiltonian path problem. Our results show that the two-stripe symmetric circulant TSP is in P. Note that a two-stripe symmetric circulant TSP instance consists of a constant number of inputs (including $n$, the number of cities), so that a polynomial-time algorithm for the decision problem must run in time polylogarithmic in $n$, and a polynomial-time algorithm for the optimization problem cannot output the tour. We address this latter difficulty by showing that the optimal tour must fall into one of two parameterized classes of tours, and that we can output the class and the parameters in polynomial time. Thus we make a substantial contribution to the set of polynomial-time solvable special cases of the TSP, and take an important step towards resolving the complexity of the general symmetric circulant TSP., Comment: 72 pages, 26 figures. A preliminary version appeared in IPCO 2022

This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan \cite{KMS98} give a vector program for which a coloring of the graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has sufficiently high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have sufficiently high rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a $k$-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if the graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank. We then modify the semidefinite program to have an objective function with costs, and explore when we can create a cost function whose optimal dual solution has sufficiently high rank. We show that it is always possible to construct such a cost function given the graph coloring. The construction of the cost function gives rise to a heuristic for graph coloring which we show works well in the case of planar graphs. Our research was motivated by the Colin de Verdi\`ere graph invariant \cite{CDV90}(and a corresponding conjecture of Colin de Verdi\`ere), in which matrices that have some similarities to the dual feasible matrices must have high rank in the case that graphs are of a certain type. We explore the connection between the conjecture and the rank of the dual solutions., Comment: 21 pages, 4 figures

We produce the first set of radiation hydrodynamics simulations of binary AGNs at parsec-scale separation in scale-model simulations. We use SPH for hydrodynamics, and raytracing to calculate optical depths and radiation pressure from the two AGNs. We confirm that, without radiation pressure, the sign of gravitational torque is sensitive to the binary parameters, although in one of our two orbital configurations the binary should coalesce in a time-scale of $<10^9$ yr. However, radiation pressure quickly destroys the 'minitori' around each SMBH, drastically reducing gravitational torques and accretion, and greatly increasing the coalescence time-scale. Our simulations suggest a new 'minitorus' duty cycle with a time-scale of ~10 binary periods (~$10^6$ yr when scaling our models to a total binary mass of $2\times10^7\,M_\odot$). The growth and blow-out phases of the 'minitori' are of similar time-scales, and thus we expect about half of observed binary SMBHs to be active, in at least one component. The 'minitorus' structure provides asymmetries that could be observed by infrared interferometry., Comment: 12 pages, 8 Figures, 3 Tables; Accepted for publication in MNRAS

We study the problem of finding flows in undirected graphs so as to minimize the weighted $p$-norm of the flow for any $p > 1$. When $p=2$, the problem is that of finding an electrical flow, and its dual is equivalent to solving a Laplacian linear system. The case $p = \infty$ corresponds to finding a min-congestion flow, which is equivalent to max-flows. A typical algorithmic construction for such problems considers vertex potentials corresponding to the flow conservation constraints, and has two simple types of update steps: cycle toggling, which modifies the flow along a cycle, and cut toggling, which modifies all potentials on one side of a cut. Both types of steps are typically performed relative to a spanning tree $T$; then the cycle is a fundamental cycle of $T$, and the cut is a fundamental cut of $T$. In this paper, we show that these simple steps can be used to give a novel efficient implementation for the $p = 2$ case and to find near-optimal $p$-norm flows in a low number of iterations for all values of $p > 1$. Compared to known faster algorithms for these problems, our algorithms are simpler, more combinatorial, and also expose several underlying connections between these algorithms and dynamic graph data structures that have not been formalized previously., Comment: arXiv admin note: text overlap with arXiv:2010.16316

Photoactivated localization microscopy (PALM) is a powerful imaging technique for characterization of protein organization in biological cells. Due to the stochastic blinking of fluorescent probes, and camera discretization effects, each protein gives rise to a cluster of artificial observations. These blinking artifacts are an obstacle for quantitative analysis of PALM data, and tools for their correction are in high demand. We develop the Independent Blinking Cluster point process (IBCpp) family of models, which is suited for modeling of data from single-molecule localization microscopy modalities, and we present results on the mark correlation function. We then construct the PALM-IBCpp - a semiparametric IBCpp tailored for PALM data, and we describe a procedure for estimation of parameters, which can be used without parametric assumptions on the spatial organization of proteins. Our model is validated on nuclear pore complex reference data, where the ground truth was accurately recovered, and we demonstrate how the estimated blinking parameters can be used to perform a blinking corrected test for protein clustering in a cell expressing the adaptor protein LAT. Finally, we consider simulations with varying degrees of blinking and protein clustering to shed light on the expected performance in a range of realistic settings., Comment: 36 pages, 8 figures

Facet-defining inequalities of the symmetric Traveling Salesman Problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the \emph{circlet inequalities}. These inequalities were first conjectured in Gutekunst and Williamson \cite{Gut19b} when studying Circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture due to Marco Buratti in 2017. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans \cite{Goe95b}; they achieve the same worst-case strength as the similarly circulant crown inequalities of Naddef and Rinaldi \cite{Nad92}, but are generally stronger.

We present a series of chemodynamical simulations of Magellanic-like systems consisting of two interacting, equal-mass dwarf galaxies orbiting a massive host galaxy, including feedback and star formation, tides, and ram pressure. We study the star formation and chemical enrichment history of the dwarfs, and the production of a Magellanic Stream analogue. The dwarfs interact with each other through tidal forces, distorting their morphologies and triggering star formation. A stream is naturally produced as outflows, induced by feedback and interactions, are stretched by tidal forces. Counter to some recent simulations, we find that the leading arm persists even in the presence of ram pressure from the host galaxy. Interactions between the dwarfs and the host galaxies produce multiple kinematic components in the stream, as observed. A combination of ongoing star-formation and entrained low-metallicity gas causes the stream to have a complex chemical structure, with an average metallicity that is generally lower than that of the dwarfs., Comment: Accepted to ApJ

Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems whose coefficient matrix is the Laplacian matrix of a weighted graph. The solution of the linear system can be interpreted as the potentials of an electrical flow. Kelner, Orrechia, Sidford, and Zhu (STOC 2013) give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem, which has been conjectured to be difficult for dynamic algorithms by Henzinger, Krinninger, Nanongkai, and Saranurak (STOC 2015). The conjecture implies that a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an $\tilde{O}(m^{1.5})$ time cut-toggling algorithm for solving Laplacian systems. Furthermore, if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, the running time can be reduced to $O(m^{1+\epsilon})$ for any $\epsilon > 0$. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart., Comment: A preliminary version appeared in ITCS 2023

In this note, we revisit the recursive random contraction algorithm of Karger and Stein for finding a minimum cut in a graph. Our revisit is occasioned by a paper of Fox, Panigrahi, and Zhang which gives an extension of the Karger-Stein algorithm to minimum cuts and minimum $k$-cuts in hypergraphs. When specialized to the case of graphs, the algorithm is somewhat different than the original Karger-Stein algorithm. We show that the analysis becomes particularly clean in this case: we can prove that the probability that a fixed minimum cut in an $n$ node graph is returned by the algorithm is bounded below by $1/(2H_n-2)$, where $H_n$ is the $n$th harmonic number. We also consider other similar variants of the algorithm, and show that no such algorithm can achieve an asymptotically better probability of finding a fixed minimum cut., Comment: To appear in the Symposium on Simplicity in Algorithms 2021 (SOSA 2021)

The detection of dusty winds dominating the infrared emission of AGN on parsec scales has revealed the limitations of traditional radiative transfer models based on a toroidal distribution of dusty gas. A new, more complex, dynamical structure is emerging and the physical origin of such dusty winds has to be critically assessed. We present a semi-analytical model to test the hypothesis of radiatively accelerated dusty winds launched by the AGN and by the heated dust itself. The model consists of an AGN and an infrared radiating dusty disk, the latter being the primary mass reservoir for the outflow. We calculate the trajectories of dusty gas clumps in this environment, accounting for both gravity and the AGN radiation as well as the re-radiation by the hot dusty gas clouds themselves. We find that the morphology consists of a disk of material that orbits with sub-Keplerian velocities and a hyperboloid polar wind launched at the inner edge of the dusty disk. This is consistent with high-angular resolution infrared and sub-mm observations of some local Seyfert AGN. The strength of the wind and its orientation depend on the Eddington ratio and the column density of the dusty clumps, which is in agreement with proposed radiation regulated obscuration models developed for the X-ray obscuring material around AGN.

In this paper, we consider the online vertex-weighted bipartite matching problem in the random arrival model. We consider the generalization of the RANKING algorithm for this problem introduced by Huang, Tang, Wu, and Zhang (TALG 2019), who show that their algorithm has a competitive ratio of 0.6534. We show that assumptions in their analysis can be weakened, allowing us to replace their derivation of a crucial function $g$ on the unit square with a linear program that computes the values of a best possible $g$ under these assumptions on a discretized unit square. We show that the discretization does not incur much error, and show computationally that we can obtain a competitive ratio of 0.6629. To compute the bound over our discretized unit square we use parallelization, and still needed two days of computing on a 64-core machine. Furthermore, by modifying our linear program somewhat, we can show computationally an upper bound on our approach of 0.6688; any further progress beyond this bound will require either further weakening in the assumptions of $g$ or a stronger analysis than that of Huang et al., Comment: 23 pages, 7 figures

Combinatorial optimization algorithms for graph problems are usually designed afresh for each new problem with careful attention by an expert to the problem structure. In this work, we develop a new framework to solve any combinatorial optimization problem over graphs that can be formulated as a single player game defined by states, actions, and rewards, including minimum spanning tree, shortest paths, traveling salesman problem, and vehicle routing problem, without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. The trained network then outputs approximate solutions to new graph instances in linear running time. In contrast, previous approximation algorithms or heuristics tailored to NP-hard problems on graphs generally have at least quadratic running time. We demonstrate the applicability of our approach on both polynomial and NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well: (i) from training on small graphs to testing on large graphs; (ii) from training on random graphs of one type to testing on random graphs of another type; and (iii) from training on random graphs to running on real world graphs.

We produce radiation hydrodynamics models of an AGN 'torus' plus outflow on 1-100 pc scales. This large scale permits direct comparison with observations, provides justification for configurations used in radiation transfer models, and tests the sensitivity of results of smaller scale dynamical models. We find that anisotropic radiation from an AGN accretion disk can cause an outflow to evolve to become more polar, agreeing with the ubiquity of polar extended mid-IR emission, and the general geometry predicted by radiative transfer models. We also find the velocity maps can reproduce many features of observations, including apparent 'counter-rotation'., Comment: 25 pages, 17 figures, accepted to ApJ

In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic program finds the optimal solution when the demands are polynomially bounded. When demands are not polynomially bounded, we give a fully polynomial-time approximation scheme by adapting an algorithm and analysis of Van Hoesel and Wagelmans.

Infrared interferometry of local AGN has revealed a warm (~300K-400K) polar dust structure that cannot be trivially explained by the putative dust torus of the unified model. This led to the development of the disk+wind scenario which comprises of a hot (~1000K) compact equatorial dust disk and a polar dust wind. This wind is assumed to be driven by radiation pressure and, therefore, we would expect that long term variation in radiation pressure would influence the dust distribution. In this paper we attempt to quantify if and how the dust distribution changes with radiation pressure. We analyse so far unpublished VLTI/MIDI data on 8 AGN and use previous results on 25 more to create a sample of 33 AGN. This sample comprises all AGN successfully observed with VLTI/MIDI. For each AGN, we calculate the Eddington ratio, using the intrinsic 2-10keV X-ray luminosity and black hole mass, and compare this to the resolved dust emission fraction as seen by MIDI. We tentatively conclude that there is more dust in the wind at higher Eddington ratios, at least in type 2 AGN where such an effect is expected to be more easily visible., Comment: 13 pages, Accepted in ApJ

De Klerk, Pasechnik, and Sotirov give a semidefinite programming constraint for the Traveling Salesman Problem (TSP) based on the matrix-tree Theorem. This constraint says that the aggregate weight of all spanning trees in a solution to a TSP relaxation is at least that of a cycle graph. In this note, we show that the semidefinite constraint holds for any weighted 2-edge-connected graph and, in particular, is implied by the subtour elimination constraints of the subtour elimination linear program. Hence, this semidefinite constraint is implied by a finite set of linear inequality constraints.

The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, e.g., algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [9] present an SDP based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program, but generally dominates it on small instances. We provide a family of \emph{simplicial TSP instances} that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in Section 2 of Sotirov [24]. In contrast, the subtour LP performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.

The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an $n$-vertex spanning tree $T$ and an additional set $L$ of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links $F$ such that every terminal pair that has arrived so far is $2$-edge-connected in $T \cup F$. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic $O(\log^2 n)$-competitive algorithm and showed an $\Omega(\log n)$ lower bound on the competitive ratio of randomized algorithms. The case when $T$ is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic $O(\log n)$-competitive algorithm for online WTAP, which is tight up to constant factors., Comment: Preliminary version in ICALP19

We consider the integrality gap of the subtour LP relaxation of the Traveling Salesman Problem restricted to circulant instances. De Klerk and Dobre conjectured that the value of the optimal solution to the subtour LP on these instances is equal to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then use it to show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few non-trivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas in a distinctly non-metric set of instances.

We have developed a new dynamical model of the torus region in active galactic nucleus (AGN), using a three-dimensional radiation hydrodynamics algorithm. These new simulations have the specific aim to explore the role of radiatively-driven outflows, which is hotly debated in current literature as a possible explanation for the observed infrared emission from the polar regions of AGN. In this first paper, we only consider radiative effects induced by the primary radiation from the AGN. The simulations generate a disk & outflow structure that qualitatively agrees with observations, although the outflow is radial rather than polar, likely due to the lack of radiation pressure from hot dust. We find cut-offs between the wind and disk at gas temperatures of 1000 K and dust temperatures of 100 K, producing kinematic signatures that can be used for interpretation of high resolution infrared observations. We also produce line emission maps to aid in the interpretation of recent ALMA observations and future JWST observations. We investigate a number of simulation parameters, and find that the anisotropy of the radiation field is equally important to the Eddington factor, despite the anisotropy often being assumed to have a single sometimes arbitrary form in many previous works. We also find that supernovae can have a small but significant impact, but only at extremely high star formation rates., Comment: 2nd revision, Accepted in ApJ