123 research outputs found
The structure of optimal solutions to the submodular function minimization problem
No full textIn this paper, we study the structure of optimal solutions to the submodular function minimization problem. We introduce prime sets and pseudo-prime sets as basic building block of minimizer sets, and investigate composition, decomposition, recognition, and certification of prime sets. We show how Schrijver's submodular function minimization algorithm can be modified to construct in polynomial time a prime or pseudoprime decomposition of the ground set V. We also show that the final vector x obtained by this algorithm is an extreme point of the polyhedron P:= { x <= 0 : x(A) <= f(A), for all subsets A of V }.Coullard, Collette. (2003). The structure of optimal solutions to the submodular function minimization problem. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/3932
Recognizing a class of bicircular matroids
No full textAbstractThis paper presents a polynomial-time algorithm for solving a restricted version of the recognition problem for bicircular matroids. Given a matroid M, the problem is to determine whether M is bicircular. Chandru, Coullard and Wagner showed that this problem is NP-hard in general. The main tool in the development of the algorithm as well as the main theoretical contribution of the paper is a set of necessary and sufficient conditions for a given matroid to be the bicircular matroid of a given graph. As a final result, the complexity result of Chandru is strenghtened
An inventory-location model: Formulation, solution algorithm and computational results
No full textWe introduce a distribution center (DC) location model that incorporates working inventory and safety stock inventory costs at the distribution centers. In addition, the model incorporates transport costs from the suppliers to the DCs that explicitly reflect economies of scale through the use of a fixed cost term. The model is formulated as a non-linear integer-programming problem. Model properties are outlined. A Lagrangian relaxation solution algorithm is proposed. By exploiting the structure of the problem we can find a low-order polynomial algorithm for the non-linear integer programming problem that must be solved in solving the Lagrangian relaxation subproblems. A number of heuristics are outlined for finding good feasible solutions. In addition, we describe two variable forcing rules that prove to be very effective at forcing candidate sites into and out of the solution. The algorithms are tested on problems with 88 and 150 retailers. Computition times are consistently below one minute and compare favorably with those of an earlier proposed set partitioning approach for this model (Shen, 2000; Shen, Coullard and Daskin, 2000). Finally, we discuss the sensitivity of the results to changes in key parameters including the fixed cost of placing orders. Significant reductions in these costs might be expected from e-commerce technologies. The model suggests that as these costs decrease it is optimal to locate additional facilities.link_to_subscribed_fulltex
Independence and port oracles for matroids, with an application to computational learning theory
No full textGiven a matroid M with distinguished element e, a port oracle with respect to e reports whether or not a given subset contains a circuit that contains e. The first main result of this paper is an algorithm for computing an e-based ear decomposition (that is, an ear decomposition every circuit of which contains element e) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case that M is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation for M. Thus, this algorithm solves a problem in computational learning theory; it learns the class of binary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroid M. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid
Extensions of Tutte's wheels-and-whirls theorem
No full textAbstractTutte's wheels-and-whirls theorem states that if M is a 3-connected matroid and, for every element e, both the deletion and the contraction of e destroy 3-connectivity, then M is a wheel or a whirl. We prove some extensions of this theorem, one of which states that if M is 3-connected and has both a wheel and a whirl minor, then either M has only seven elements or there is some element the deletion or contraction of which maintains 3-connectivity and leaves a matroid with both a wheel and a whirl minor
On cycle cones and polyhedra
No full textAbstractGiven an undirected graph G and a cost associated with each edge, the weighted girth problem is to find a simple cycle of G having minimum total cost. We consider several variants of the weighted girth problem, some of which are NP-hard and some of which are solvable in polynomial time. We also consider the polyhedra associated with each of these problems. Two of these polyhedra are the cycle cone of G, which is the cone generated by the incidence vectors of cycles of G, and the cycle polytope of G, which is the convex hull of the incidence vectors of cycles of G. First we give a short proof of Seymour's characterization of the cycle cone of G. Next we give a polyhedral composition result for the cycle polytope of G. In particular, we prove that if G decomposes via a 3-edge cut into graphs G1 and G2, say, then defining linear systems for the cycle polytopes of G1 and G2 can be combined in a certain way to obtain a defining linear system for the cycle polytope of G. We also describe a polynomial decomposition-based algorithm for the weighted girth problem on Halin graphs, and we give a complete linear description for the cycle polytope of G, in the case G is a Halin graph
Totally unimodular Leontief directed hypergraphs
No full textAbstractA Leontief directed hypergraph is a generalization of a directed graph, where arcs have multiple (or no) tails and at most one head. We define a class of Leontief directed hypergraphs via a forbidden structure called an odd pseudocycle. We show that the vertex-hyperarc incidence matrices of the hypergraphs in this class are totally unimodular. Indeed, we show that this is the largest class with that property. We define two natural subclasses of this class (one obtained by forbidding pseudocycles and the other obtained by forbidding pseudocycles and the so-called doublecycles), and we describe some structural properties of the bases and circuits of the members of these classes. We present examples of Leontief directed hypergraphs that are graphic, cographic, and neither graphic nor cographic
- …
