Local ratio with negative weights

We present local ratio interpretations of known algorithms for minimums-tcut and the assignment problem. Our interpretations are the first application of local ratio with negative weights. These interpretations lead to primal-dual analyses that are based on new IP formulations.     

Constant factor approximation for ATSP with two edge weights

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held–Karp relaxation, which may be of independent interest.     

Minimum spanning trees in networks with varying edge weights

This paper considers the problem of determining minimum spanning trees in networks in which each edge weight can assume a finite number of distinct values. We use the algebraic structure of an underlying Hasse diagram to describe the relationship between different edge-weight realizations of the network, yielding new results on how MSTs change under multiple edge-weight perturbations. We investigate various implementation strategies for updating MSTs in this manner. Computational results are provided for some challenging test networks.     

The additivity criterion for finite metric spaces and minimal fillings

A new additivity criterion for finite metric spaces is obtained. The criterion is based on properties of minimal fillings in the sense of M. Gromov     

The functions that do not change types of minimal fillings

It is proved that a function changing distances in finite metric spaces and preserving the types of their minimal fillings has the form f (x) = kx + b. It is sufficient to assume that the types of fillings are preserved for spaces consisting of at most five points.     

Domination game and minimal edge cuts

In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if $C$ a minimum edge cut of a connected graph $G$, then ${\gamma }_g\left(G\right)\le {\gamma }_g(G?C)+2{\kappa }^{\prime }\left(G\right)$. Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved.     

Coincidence conditions in multifacility location problems with positive and negative weights

In minisum multifacility location problems one has to find locations for some new facilities, such that the weighted sum of distances between the new and a certain number of old facilities with known locations is minimized. In this kind of problem, the optimal locations of clusters of facilities frequently tend to coincide. By testing conditions for coincidence, one has the opportunity to collapse some or even all facilities coinciding at an optimal point into one. In this way, the dimension of the problem and the degree of nondifferentiability is reduced. Several conditions for coincidence have been published recently. In this paper, these conditions are extended and improved with respect to new sufficient coincidence conditions for location problems with attracting and repelling facilities. An example shows that these new conditions detect more coincidences than the conditions which are known so far, even if all facilities involved are attracting ones.     

Bifurcations of Steiner minimal trees and minimal fillings for non-convex four-point boundaries and Steiner subratio for the Euclidean plane

Bifurcation diagrams for topologies of Steiner minimal trees and minimal fillings for nonconvex four-point boundaries in the Euclidean plane are constructed. Using this result, the four-pointed Steiner subratio of the Euclidean plane is obtained. All configurations which it is attained at are found.     

Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

The NP-hard problem of finding two edge-disjoint Hamiltonian cycles of minimal total weight (also known as 2- PSP_min) in a complete (undirected) graph with edge weights 1 and 2 is considered. Polynomial time approximation algorithms are proposed with performance ratios 5/4 (in the case of one weight function) and 11/7 (in the case of two weight functions), respectively.     

Optimal algorithms for computing edge weights in planar split networks

In phylogenetics, biologists commonly compute split networks when trying to better understand evolutionary data. These graph-theoretical structures represent collections of weighted bipartitions or splits of a finite set, and provide a means to display conflicting evolutionary signals. The weights associated to the splits are used to scale the edges in the network and are often computed using some distance matrix associated with the data. In this paper we present optimal polynomial time algorithms for three basic problems that arise in this context when computing split weights for planar split-networks. These generalize algorithms that have been developed for special classes of split networks (namely, trees and outer-labeled planar networks). As part of our analysis, we also derive a Crofton formula for full flat split systems, structures that naturally arise when constructing planar split-networks.     

Polyhedral convexity cuts and negative edge extensions

This note shows that convexity cuts defined relative to polyhedral convex sets can utilize negative as well as positive edge extensions under appropriate circumstances, yielding stronger cuts than customarily available. We also show how to partially collapse the polyhedron to further improve these cuts.     

Stable minimal hypersurfaces in a Riemannian manifold with pinched negative sectional curvature

We give an estimate of the smallest spectral value of the Laplace operator on a complete noncompact stable minimal hypersurface M in a complete simply connected Riemannian manifold with pinched negative sectional curvature. In the same ambient space, we prove that if a complete minimal hypersurface M has sufficiently small total scalar curvature then M has only one end. We also obtain a vanishing theorem for L ² harmonic 1-forms on minimal hypersurfaces in a Riemannian manifold with sectional curvature bounded below by a negative constant. Moreover, we provide sufficient conditions for a minimal hypersurface in a Riemannian manifold with nonpositive sectional curvature to be stable.     

Efficient computation of 2-medians in a tree network with positive/negative weights

We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51-71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in O(n²) time and O(n³) time, respectively, with better performance for special trees such as paths and stars. We propose here an O(nlogn) algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper.     

The symmetric traveling salesman problem and edge exchanges in minimal 1-trees

In this article the effect of exchanging edges inside a minimal 1-tree with edges outside is analysed. In combination with an upper bound this analysis enables the elimination of variables in the symmetric traveling salesman problem. After discussion on a number of improvements for this analysis, the implementation is described in a traveling salesman algorithm based on the 1-tree relaxation. Computational results show the advantages of the edges exchanges for Euclidean problems (up to 120 cities) as well as for random table problems (up to 200 cities).     

Tight contact structures with no symplectic fillings

We exhibit tight contact structures on 3-manifolds that do not admit any symplectic fillings. Oblatum 7-XII-2000 & 14-XI-2001?Published online: 9 April 2002     

Exotic Stein fillings with arbitrary fundamental group

Let G be a finitely presentable group. We provide an infinite family of homeomorphic but pairwise non-diffeomorphic, symplectic but non-complex closed 4-manifolds with fundamental group G such that each member of the family admits a Lefschetz fibration of the same genus over the two-sphere. As a corollary, we also show the existence of a contact 3-manifold which admits infinitely many homeomorphic but pairwise non-diffeomorphic Stein fillings such that the fundamental group of each filling is isomorphic to G. Moreover, we observe that the contact 3-manifold above is contactomorphic to the link of some isolated complex surface singularity equipped with its canonical contact structure.     

Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2

The problem of finding two disjoint Hamiltonian cycles of minimum sum weight is considered in a complete undirected graph with arbitrarily chosen weights of the edges 1 and 2. The main result of the paper is the presentation of polynomial algorithms with the currently best guaranteed performance factors 26/21 and 6/5. These algorithms are based on finding the partial tours with a large number of edges in the graphs of a special type.     

Interpolation inequalities with weights

We use elementary methods to prove a sufficient and necessary condition for a Sobolev interpolation inequalities with weight [ILLM0001] where [ILLM0001] are real numbers, and [ILLM0001]