Extension problems with degree bounds

We have proved in an earlier paper that the complexity of the list homomorphism problem, to a fixed graph H, does not change when the input graphs are restricted to have bounded degrees (except in the trivial case when the bound is two). By way of contrast, we show in this paper that the extension problem, again to a fixed graph H, can, in some cases, become easier for graphs with bounded degrees.     

On three Krein extension problems and some generalizations

Three basic extension problems which were initiated by M. G. Krein are discussed and further developed. Connections with interpolation problems in the Carathéodory class are explained. Some tangential and bitangential versions are considered. Full characterizations of the classes of resolvent matrices for these problems are given and formulas for the resolvent matrices of left tangential problems are obtained using reproducing kernel Hilbert space methods.Dedicated to the memory of M. G. Krein, a beacon for us both.The authors wish to acknowledge the partial support of the Israel-Ukraine Exchange Program. D. Z. Arov also wishes to thank the Weizmann Institute of Science for partial support and hospitality; H. Dym wishes to thank Renee and Jay Weiss for endowing the chair which supports his research.     

Spanning trees with variable degree bounds

In this paper, we introduce and study a generalization of the degree constrained minimum spanning tree problem where we may install one of several available transmission systems (each with a different cost value) in each edge. The degree of the endnodes of each edge depends on the system installed on the edge. We also discuss a particular case that arises in the design of wireless mesh networks (in this variant the degree of the endnodes of each edge depend on the transmission system installed on it as well as on the length of the edge). We propose three classes of models using different sets of variables and compare from a theoretical perspective as well as from a computational point of view, the models and the corresponding linear programming relaxations. The computational results show that some of the proposed models are able to solve to optimality instances with 100 nodes and different scenarios.     

On error bounds of polynomial complementarity problems with structured tensors

The recently introduced polynomial complementarity problem (PCP) is an interesting generalization of the tensor complementarity problem (TCP) studied extensively in the literature. In this paper, we make a contribution to analysing the error bounds of PCPs with structured tensors. Specifically, we first show that the solution set of PCPs with a leading ER-tensor is nonempty and compact. Then, we analyse lower bounds of solutions of PCPs under the strict semicopositiveness, thereby gainfully establishing error bounds of PCPs, which, to the best of our knowledge, are not studied in the current PCPs and TCPs literature. Moreover, it is noteworthy that, due to the special structure of PCPs, our error bounds are better than the direct results obtained by applying the theory of non-linear complementarity problems to PCPs.     

Welch bounds for cross correlation of subspaces and generalizations

Lower bounds on the maximal cross correlation between vectors in a set were first given by Welch and then studied by several others. In this work, this is extended to obtaining lower bounds on the maximal cross correlation between subspaces of a given Hilbert space. Two different notions of cross correlation among spaces have been considered. The study of such bounds is done in terms of fusion frames, including generalized fusion frames. In addition, results on the expectation of the cross correlation among random vectors have been obtained.     

On isoperimetric gradient bounds for poisson problems and problems of torsional creep

Summary Gradient bounds of Payne and Philippin are derived in an elementary way and some generalizations are indicated.

---

Zusammenfassung Es wird ein einfacher Weg vorgeschlagen, um einige Gradientenabschätzungen von Payne und Philippin zu gewinnen und zu verallgemeinern.

     

Improved bounds on equilibria solutions in the network design game

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most \(H_n\), the n-th harmonic number. This bound is tight for directed graphs.For undirected graphs, it has only recently been shown that the price of stability is at most \(H_n \left( 1-\frac{1}{\Theta (n^4)} \right) \), while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most \(H_{n/2} + \varepsilon \) for any \(\varepsilon \) starting from some suitable \(n \ge n(\varepsilon )\).We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of \(\frac{4}{3}\) and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of \(\frac{4}{3}\), and provide an upper bound of \(\frac{26}{19}\). To the end, we conjecture and argue that the right answer is \(\frac{4}{3}\).     

On upper bounds of sequential stochastic production planning problems

In this paper we consider a class of problems that determine production, inventory and work force levels for a firm in order to meet fluctuating demand requirements. A production planning problem arises because of the need to match, at the firm level, supply and demand efficiently. In practice, the two common approaches to counter demand uncertainties are (i) carrying a constant safety stock from period to period, and (ii) planning with a rolling horizon. Under the rolling horizon (or sequential) strategy the planning model is repeatedly solved, usually at the end of every time period, as new information becomes available and is used to update the model parameters. The costs associated with a rolling horizon strategy are hard to compute a priori because the solution of the model in any intermediate time period depends on the actual demands of the previous periods.In this paper we derive two a priori upper bounds on the costs for a class of production planning problems under the rolling horizon strategy. These upper bounds are derived by establishing correspondences between the rolling horizon problems and related deterministic programs. One of the upper bounds is obtained through Lagrangian relaxation of the service level constraint. We propose refinements to the non-Lagrangian bounds and present limited computational results. Extensions of the main results to the multiple item problems are also discussed. The results of this paper are intended to support production managers in estimating the production costs and value of demand information under a rolling horizon strategy.     

The non-approximability of bicriteria network design problems

Let G be an undirected graph with two edge costs (c-cost and d-cost). We want to minimize the diameter of a spanning subgraph S (under d-cost) subject to the constraint that the total cost of the edges in S (with respect to c) does not exceed a given budget. We prove that this problem is non-approximable, even in some special cases. Similar results are proved if the stretch factor or the root stretch factor is considered instead of the diameter.     

On lower bounds for the chromatic number in terms of vertex degree

In this paper we discuss the existence of lower bounds for the chromatic number of graphs in terms of the average degree or the coloring number of graphs. We obtain a lower bound for the chromatic number of K_1,t-free graphs in terms of the maximum degree and show that the bound is tight. For any tree T, we obtain a lower bound for the chromatic number of any K_2,t-free and T-free graph in terms of its average degree. This answers affirmatively a modified version of Problem 4.3 in [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995]. More generally, we discuss δ-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a δ-bounded family in terms of its induced bipartite Turán number. Our last bound is in terms of forbidden induced even cycles in graphs; it extends a result in [S.E. Markossian, G.S. Gasparian, B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1996) 1–11].     

General network design: A unified view of combined location and network design problems

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.     

Equilibrium problems with lower and upper bounds

In this paper, we obtain some existence results of equilibrium problems with lower and upper bounds by employing a fixed-point theorem due to Ansari and Yao [1] and Ky Fan Lemma [2], respectively. Our results give answers to the open problem raised by Isac, Sehgal and Singh [3].     

Biclique completion problems for multicast network design

This paper considers the problem of aggregating several multicast sessions. A multicast session is defined as a subset of clients requiring the same information. Besides, each client can require several multicast sessions. A telecommunication network cannot manage many multicast sessions at the same time. It is hence necessary to group the sessions into a limited number of clusters. The problem then consists in aggregating the sessions into clusters to limit the number of unnecessary information sent to clients. The strong relationship of the problems with biclique problems in bipartite graph is established. We then model the problems using integer quadratic and linear programming formulations. We investigate some properties to strengthen the models. Several algorithms are provided and compared with a series of numerical experiments.     

Capacitated facility location/network design problems

We introduce a combined facility location/network design problem in which facilities have constraining capacities on the amount of demand they can serve. This model has a number of applications in regional planning, distribution, telecommunications, energy management, and other areas. Our model includes the classical capacitated facility location problem (CFLP) on a network as a special case. We present a mixed integer programming formulation of the problem, and several classes of valid inequalities are derived to strengthen its LP relaxation. Computational experience with problems with up to 40 nodes and 160 candidate links is reported, and a sensitivity analysis provides insight into the behavior of the model in response to changes in key problem parameters.