Approximation of circular arcs by parametric polynomial curves

In this paper the approximation of circular arcs by parametric polynomial curves is studied. If the angular length of the circular arc is h, a parametric polynomial curve of arbitrary degree \(n \in {\mathbb{N}}\) , which interpolates given arc at a particular point, can be constructed with radial distance bounded by h ²ⁿ . This is a generalization of the result obtained by Lyche and Mørken for odd n.     

A quadratic network optimization model for equilibrium single commodity trade flows

When supply and demand curves for a single commodity are approximately linear in each ofN regions and interregional transportation costs are linear, then equilibrium trade flows can be computed by solving a quadratic program of special structure. An equilibrium trade flow exists in which the routes carrying positive flow form a forest, and this solution can be efficiently computed by a tree growing algorithm.     

Approximating earliest arrival flows with flow-dependent transit times

For the earliest arrival flow problem one is given a network G=(V,A) with capacities u(a) and transit times τ(a) on its arcs a∈A, together with a source and a sink vertex s,t∈V. The objective is to send flow from s to t that moves through the network over time, such that for each time θ∈[0,T) the maximum possible amount of flow up to this time reaches t. If, for each θ∈[0,T), this flow is a maximum flow for time horizon θ, then it is called earliest arrival flow. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time θ depends on the flow on this particular arc at that time θ.For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define a relaxed version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each θ∈[0,T), need only α-times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on α; furthermore, we present a constant factor approximation algorithm for this problem.     

Metric properties of the nearest extended parametric fuzzy number and applications

We propose the notion of extended parametric fuzzy number, which generalizes the extended trapezoidal fuzzy number and parametric fuzzy number, discussed in some recent papers. The metric properties of the nearest extended parametric fuzzy number of a fuzzy number, proved in the present article, help us to obtain the property of continuity for the parametric approximation operator and to simplify the solving of the problems of parametric approximations under conditions.     

Real-valued flows in a network with fuzzy arc capacities

The problem of the maximal (minimal) flow in a network with fuzzy capacity constraints is considered. A theorem being a natural direct generalization of the Ford-Fulkerson theorem relating the flow value with cut capacities in the network is proved. A simple algorithm, based on the mentioned theorem, for the determination of optimal real-valued flows is developed.     

A survey of some mathematical programming models in transportation

Transportation problems constitute a fertile domain for the application of mathematical programming models and nonlinear optimization techniques, distribution problems, entropy models, traffic assigment problems and many others are good examples of this assertion. This paper provides a summary overview of the main modeling approaches in transportation and the related optimization models, symmetric and asymmetric, and an overview on the state-of-the-art of the origindestination adjustment problems and the related bilevel optimization methods.     

Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh

For two classes of network flow problems a worst-case analysis is given depending on the number of vertices of a pathological graph of Zadeh. Firstly, an exponential number of breakpoints in the optimal value function of the maximal flow problem in generalized networks with parametric capacities is demonstrated. Secondly, it is shown that the bicriterial min-cost flow has, in the worst case. an exponential number of efficient extreme point solutions in the objective space.

---

Zusammenfassung Für zwei Klassen von Netzwerkflußproblemen wird eine worst-case Analyse in Abhängigkeit von der Anzahl der Knoten eines pathologischen Graphen von Zadeh vorgenommen. Demnach besitzt das Maximalflußproblem in verallgemeinerten Netzwerken mit parametrischen Kapazitätsbeschränkungen eine exponentielle Anzahl von Knickstellen in der Optimalwertfunktion. und kostenminimale Flüsse haben bereits für zwei Kriterien eine exponentielle Zahl von effizienten Eckpunkten im Bildbereich.

     

Algorithms for fair k-clustering with multiple protected attributes

We study fair center based clustering problems. In an influential paper, Chierichetti, Kumar, Lattanzi and Vassilvitskii (NIPS 2017) consider the problem of finding a good clustering, say of women and men, such that every cluster contains an equal number of women and men. They were able to obtain a constant factor approximation for this problem for most center based k-clustering objectives such as k-median, k-means, and k-center. Despite considerable interest in extending this problem for multiple protected attributes (e.g. women and men, with or without citizenship), so far constant factor approximations for these problems have remained elusive except in special cases. We settle this question in the affirmative by giving the first constant factor approximation for a wide range of center based k-clustering objectives.     

The max-flow problem with parametric capacities

In this paper we present a comprehensive analysis of the max-flow problem with n parametric capacities, and give the basis for an algorithm to solve it. In particular we give a method for finding the max-flow value as a function of the parameters, and max-flows for all parameter points, in terms of max-flow values to problems at certain key parameter points. In the problem with nonzero lower bounds on the arc flows, we derive a set of linear constraints whose solution set is identical to the set of all feasible parameter points.The intrinsic difficulty of the problem is compared with that of the general multiparametric linear programming problem, and thus light is shed on the difficulty of the latter problem, whose complexity is currently unknown.     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

Dimension spectra for flows: Future and past

We establish a conditional variational principle for the dimension spectrum obtained from almost additive families for a flow on a conformal locally maximal hyperbolic set, simultaneously into the future and into the past.     

Algorithms for parametric nonconvex programming

In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter . This family of problems is called a parametric nonconvex program (PNP). Solving (PNP) means finding an optimal solution for every program in the family. A prototype branch-and-bound algorithm is presented for solving (PNP). By modifying a prototype algorithm for solving a single nonconvex program, this algorithm solves (PNP) in one branch-and-bound search. To implement the algorithm, certain compact partitions and underestimating functions must be formed in an appropriate manner. We present an algorithm for solving a particular (PNP) which implements the prototype algorithm by forming compact partitions and underestimating functions based upon rules given by Falk and Soland. The programs in this (PNP) have the same concave objective function, but their feasibility regions are described by linear constraints with differing right-hand sides. Computational experience with this algorithm is reported for various problems.The author would like to thank Professors R. M. Soland, T. L. Morin, and P. L. Yu for their helpful comments. Thanks also go to two anonymous reviewers for their useful comments concerning an earlier version of this paper.     

Critical sets in parametric optimization

We deal with one-parameter families of optimization problems in finite dimensions. The constraints are both of equality and inequality type. The concept of a generalized critical point (g.c. point) is introduced. In particular, every local minimum, Kuhn-Tucker point, and point of Fritz John type is a g.c. point. Under fairly weak (even generic) conditions we study the set consisting of all g.c. points. Due to the parameter, the set is pieced together from one-dimensional manifolds. The points of can be divided into five (characteristic) types. The subset of nondegenerate critical points (first type) is open and dense in (nondegenerate means: strict complementarity, nondegeneracy of the corresponding quadratic form and linear independence of the gradients of binding constraints). A nondegenerate critical point is completely characterized by means of four indices. The change of these indices along is presented. Finally, the Kuhn-Tucker subset of is studied in more detail, in particular in connection with the (failure of the) Mangasarian-Fromowitz constraint qualification.     

Computational aspects of two-segment separable programming

Recursive separable programming algorithms based on local, two-segment approximations are described for the solution of separable convex programs. Details are also given for the computation of lower bounds on the optimal value by both a primal and a dual approach, and these approaches are compared. Computational comparisons of the methods are provided for a variety of test problems, including a water supply application (with more than 600 constraints and more than 900 variables) and an econometric modelling problem (with more than 200 variables). Research supported by National Science Foundation Grants MCS74-20584 A02 and MCS-7901066.     

Strongly polynomial-time approximation for a class of bicriteria problems

Consider the following problem: given a ground set and two minimization objectives of the same type find a subset from a given subset-class that minimizes the first objective subject to a budget constraint on the second objective. Using Megiddo's parametric method we improve an earlier weakly polynomial time algorithm.     

Algorithms for flows over time with scheduling costs

Mathematical Programming - Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated...     

On equivalent representations of certain multicommodity networks as single commodity flow problems

Several classes of multicommodity networks have been shown to have the property that they can be transformed to equivalent uncapacitated single commodity flow problems. We show that many of these networks can be further reduced to smaller, semi-capacitated flow problems using the inverse of a result of Ford and Fulkerson. This appears to be a useful computationally-oriented tool for developing practically efficient algorithms. These concepts are also used to establish a generalization of a previous result concerning multicommodity transportation problems.     

Homoclinic and heteroclinic flows in global attractor for Davey-stewartson II equation

By the variable transformation and generalized Hirota method, exact homoclinic and heteroclinic solutions for Davey-Stewartson II （DSII） equation are obtained. For perturbed DSII equation, the existence of a global attractor is proved. The persistence of homoclinic and heteroclinic flows is investigated, and the special homoclinic and heteroclinic structure in attractors is shown.