Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

The minimum-cost transformation of graphs

Doklady Mathematics - A complete proof that algorithms proposed by the authors solve the problem of minimum-cost transformation of a graph into another graph is given. The problem is solved both by...     

A least-squares minimum-cost network flow algorithm

Node-arc incidence matrices in network flow problems exhibit several special least-squares properties. We show how these properties can be leveraged in a least-squares primal-dual algorithm for solving minimum-cost network flow problems quickly. Computational results show that the performance of an upper-bounded version of the least-squares minimum-cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum-cost network flow problems.     

Finding minimum-cost flows by double scaling

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.On leave from Indian Institute of Technology, Kanpur, India.Research partially supported by an NSF Presidential Young Investigator Award.Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467.     

Listing minimal edge-covers of intersecting families with applications to connectivity problems

Let G=(V,E) be a directed/undirected graph, let s,t∈V, and let F be an intersecting family on V (that is, X∩Y,X∪Y∈F for any intersecting X,Y∈F) so that s∈X and t∉X for every X∈F. An edge set I⊆E is an edge-cover of F if for every X∈F there is an edge in I from X to V−X. We show that minimal edge-covers of F can be listed with polynomial delay, provided that, for any I⊆E the minimal member of the residual family F_I of the sets in F not covered by I can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal k-connected and k-outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.     

A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

Mathematical Programming - Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (A refined Gomory–Chvátal closure for polytopes...     

Approximating Perpetuities

We propose and analyze an algorithm to approximate distribution functions and densities of perpetuities. Our algorithm refines an earlier approach based on iterating discretized versions of the fixed point equation that defines the perpetuity. We significantly reduce the complexity of the earlier algorithm. Also one particular perpetuity arising in the analysis of the selection algorithm Quickselect is studied in more detail. Our approach works well for distribution functions. For densities we have weaker error bounds although computer experiments indicate that densities can also be approximated well. Supported by an Emmy Noether Fellowship of the Deutsche Forschungsgemeinschaft.     

On the minimum-cost $$\lambda $$-edge-connected k-subgraph problem

In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost \(\lambda \)-edge-connected k-subgraph problem, or the \((k,\lambda )\)-subgraph problem, based on its graph properties. Special cases of this problem include the well-known k-minimum spanning tree problem (if \(\lambda =1\)), \(\lambda \)-edge-connected spanning subgraph problem (if \(k=|V|\)) and k-clique problem (if \(\lambda = k-1\) and there are exact k vertices in the subgraph). As a generalization of k-minimum spanning tree and a case of the \((k,\lambda )\)-subgraph problem, the (k, 2)-subgraph problem is studied, and some special graph properties are proved to find stronger and more compact IP formulations. Additionally, we study the valid inequalities for these IP formulations. Numerical experiments are performed to compare proposed IP formulations and inequalities.     

Approximating graph-constrained max-cut

An instance of the graph-constrained max-cut (\(\mathsf {GCMC}\)) problem consists of (i) an undirected graph \(G=(V,E)\) and (ii) edge-weights \(c:{V\atopwithdelims ()2} \rightarrow \mathbb {R}_+\) on a complete undirected graph. The objective is to find a subset \(S \subseteq V\) of vertices satisfying some graph-based constraint in G that maximizes the weight \(\sum _{u\in S, v\not \in S} c_{uv}\) of edges in the cut \((S,V{\setminus } S)\). The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded treewidth, where we obtain a \(\frac{1}{2}\)-approximation algorithm. Our algorithm uses an LP relaxation based on the Sherali–Adams hierarchy. It can handle any graph constraint for which there is a dynamic program of a specific form. Using known decomposition results, these imply essentially the same approximation ratio for \(\mathsf {GCMC}\) under constraints such as independent set, dominating set and connectivity on a planar graph G.     

Approximating Planar Rotations

We study the problem of approximating a rotation of the plane, α :R ² R ² , α (x,y)=(x cos θ + y sin θ , y cos θ - x sin θ ), by a bijection β :Z ² Z ² . We show by an explicit construction that β may be chosen so that , where r= tan ( θ /2). The scheme is based on those invented and patented by the second author in 1994. Received November 21, 1996, and in revised form February 20, 1997.     

Approximating exponential models

Approximation of parametric statistical models by exponential models is discussed, from the viewpoints of observed as well as of expected likelihood geometry. This extends a construction, in expected geometry, due to Amari. The approximations considered are parametrization invariant and local. Some of them relate to conditional models given exact or approximate ancillary statistics. Various examples are considered and the relation between the maximum likelihood estimators of the original model and the approximating models is studied.Research partly supported by the Danish Science Research Council.     

Approximating Directed Multicuts

The seminal paper of Leighton and Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are symmetric and therefore similar to undirected networks. This paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the max flow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.* Supported in part by NSERC research grant OGP0138432. Part of this work was done while visiting AT&T Labs–Research. Work at the Technion supported by Israel Science Foundation grant number 386/99, by BSF grants 96-00402 and 99-00217, by Ministry of Science contract number 9480198, by EU contract number 14084 (APPOL), by the CONSIST consortium (through the MAGNET program of the Ministry of Trade and Industry), and by the Fund for the Promotion of Research at the Technion.     

Hybrid approximation for minimum-cost target coverage in wireless sensor networks

This paper presents a hybrid approximation scheme for the Max-SNP-complete minimum-cost target coverage problem in wireless sensor networks. LP-rounding and set-cover selection are polynomial-time approximations for this problem. Our hybrid scheme combines these two methods using a crafted convex combination. We show that the hybrid scheme with appropriately chosen coefficients produces much better approximations than either of the two methods used alone. We show that, through a large number of numerical experiments, the hybrid scheme never exceeds an approximation ratio of 1.14, providing up to 14.86% improvement over the best approximations previously known.     

Approximating absolute Galois groups

In this paper we identify a class of profinite groups (totally torsion free groups) that includes all separable Galois groups of fields containing an algebraically closed subfield, and demonstrate that it can be realized as an inverse limit of torsion free virtually finitely generated abelian (tfvfga) profinite groups. We show by examples that the condition is quite restrictive. In particular, semidirect products of torsion free abelian groups are rarely totally torsion free. The result is of importance for K-theoretic applications, since descent problems for tfvfga groups are relatively manageable.     

Approximating Rough Stochastic PDEs

We study approximations to a class of vector‐valued equations of Burgers type driven by a multiplicative space‐time white noise. A solution theory for this class of equations has been developed recently in Probability Theory Related Fields by Hairer and Weber. The key idea was to use the theory of controlled rough paths to give definitions of weak/mild solutions and to set up a Picard iteration argument. In this article the limiting behavior of a rather large class of (spatial) approximations to these equations is studied. These approximations are shown to converge and convergence rates are given, but the limit may depend on the particular choice of approximation. This effect is a spatial analogue to the Itô‐Stratonovich correction in the theory of stochastic ordinary differential equations, where it is well known that different approximation schemes may converge to different solutions.© 2014 Wiley Periodicals, Inc.