Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 15 of 15 for “"polymatroid"”.
-
Dissecting an integer polymatroid
One way to define an integer polymatroid ρ is via its independent set polytope, whose faces are parallel translates of the independent set polytopes of the minors of ρ. To better understand the interior of this polytope, we endow a structure on this polytope which relates to the polymatroid …
-
On Matroid and Polymatroid Connectivity
… k in a vector space, one gets an example of a k-polymatroid. Connectivity is a pivotal topic of study in the endeavor to understand the structure of matroids and polymatroids. In this dissertation, we study the notion of connectivity from several angles. It is a well-known result of Tutte that, …
-
Lattice minors and Eulerian posets
… associate a generator-enriched lattice to any polymatroid, a far reaching generalization of graphs, and we show that conversely, any generator-enriched lattice has an associated polymatroid. The generator-enriched lattice encodes the simple information of the closure operator of the polymatroid …
-
Exact Approaches for a Class of Nonlinear Discrete Facility Location and Network Design Problems
… model. We present nine conic reformulations and polymatroid inequalities for them. Extensive computations are conducted to assess the efficacy of reformulations and determine the characteristics of a strong conic formulation. The focus of the second paper is on the bandwidth packing problem (BPP) …
-
SUBMODULAR FUNCTIONS, GRAPHS AND INTEGER POLYHEDRA
… a application of the results of Chapter 4 to the polymatroid aspects of matroid theory. We characterize the vertices and the facets of the intersection of two matroid polyhedra. We use the characterization of the facets of this intersection to derive a graph theoretic description of the facets of …
-
q-Polymatroids and their application to rank-metric codes.
… codes. This relation was then generalized to q-polymatroids and linear matrix rank metric codes. This dissertation aims at developing the theory of q-(poly)matroid and its relation to the theory of rank metric codes. In a first part, we recall and establish preliminary results for both …
-
The complexity of graph polynomials
… The rank generating function S of a graphic 2-polymatroid was introduced by Oxley and Whittle (1993). It has many similarities to the Tutte polynomial and we prove the following results. </p><p> Theorem 2. Evaluating S at a fixed point (u,v) is #P-hard unless uv=1 when there is a polynomial …
-
Resource allocation problems in MIMO-OFDM systems
… fairness constraints on the powers result in a polymatroid. As a result, optimal power allocation is performed via a Greedy Algorithm that attains the solution in O(nlogn) computations, where n is the number of fairness power constraints. Next, the problem is extended to consider antenna …
-
Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)
… are considered, including the finite polymatroid networks of Lawler.
-
Connectivity of Matroids and Polymatroids
… is a collection of work on matroid and polymatroid connectivity. Connectivity is a useful property of matroids that allows a matroid to be decomposed naturally into its connected components, which are like blocks in a graph. The Cunningham-Edmonds tree decomposition further gives a way …
-
Communication over MIMO Multi-User Systems: Signalling and Fairness
… which includes the sum-capacity facets, forms a polymatroid structure. The main purpose is to find a point on the sum-capacity facet which satisfies a notion of fairness among active users. This problem is addressed in the cases where the complexity of achieving interior points is not feasible, …
-
Feasibility optimality of periodwise static priority policies for a quality of service model in wireless networks and convergence analysis for an online recommendation system
… by the timely-throughput constraints is a polymatroid, from which the optimality within the class of periodwise static priority poli- cies follows. The second part of the thesis analyzes the convergence of an algorithm for the problem of learning with expert advice. At the present time, …
-
On the Fundamental Limits and Symmetric Designs for Distributed Information Systems
… entropic vectors and representability of integer polymatroids, construction of such vector has been discussed. Specifically, It is shown that representability of the particularly constructed matroid is a sufficient condition for integer polymatroids to be linearly representable over real numbers. …
-
Performance bounds for greedy strategies in submodular optimization problems
To view the abstract, please see the full text of the document.