A projection subgradient method for solving optimization with variational inequality constraints

In this paper, we propose a projection subgradient method for solving some classical variational inequality problem over the set of solutions of mixed variational inequalities. Under the conditions that $T$ is a $\Theta $ -pseudomonotone mapping and $A$ is a $\rho $ -strongly pseudomonotone mapping, we prove the convergence of the algorithm constructed by projection subgradient method. Our algorithm can be applied for instance to some mathematical programs with complementarity constraints.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

A ranking model for the greedy algorithm and discrete convexity

Generalizing the idea of the Lovász extension of a set function and the discrete Choquet integral, we introduce a combinatorial model that allows us to define and analyze matroid-type greedy algorithms. The model is based on a real-valued function v on a (finite) family of sets which yields the constraints of a combinatorial linear program. Moreover, v gives rise to a ranking and selection procedure for the elements of the ground set N and thus implies a greedy algorithm for the linear program. It is proved that the greedy algorithm is guaranteed to produce primal and dual optimal solutions if and only if an associated functional on ${\mathbb{R}^N}$ is concave. Previous matroid-type greedy models are shown to fit into the present general context. In particular, a general model for combinatorial optimization under supermodular constraints is presented which guarantees the greedy algorithm to work.     

Solving convex optimization with side constraints in a multi-class queue by adaptive c\mu rule

We study convex optimization problems with side constraints in a multi-class \(M/G/1\) queue with controllable service rates. In the simplest problem of optimizing linear costs with fixed service rate, the \(c\mu \) rule is known to be optimal. A natural question to ask is whether such simple policies exist for more complex control objectives. In this paper, combining the achievable region approach in queueing systems and the Lyapunov drift theory suitable to optimize renewal systems with time-average constraints, we show that convex optimization problems can be solved by variants of adaptive \(c\mu \) rules. These policies greedily re-prioritize job classes at the end of busy periods in response to past observed delays in each job class. Our method transforms the original problems into a new set of queue stability problems, and the adaptive \(c\mu \) rules are queue stable policies. An attractive feature of the adaptive \(c\mu \) rules is that they use limited statistics of the queue, where no statistics are required for the problem of satisfying average queueing delay in each job class.     

f-Vectors Implying Vertex Decomposability

We prove that if a pure simplicial complex $\Delta $ of dimension $d$ with $n$ facets has the least possible number of $(d-1)$ -dimensional faces among all complexes with $n$ faces of dimension $d$ , then it is vertex decomposable. This answers a question of J. Herzog and T. Hibi. In fact, we prove a generalization of their theorem using combinatorial methods.     

Supply chain scheduling to minimize holding costs with outsourcing

This paper addresses a scheduling problem in a flexible supply chain, in which the jobs can be either processed in house, or outsourced to a third-party supplier. The goal is to minimize the sum of holding and delivery costs. This problem is proved to be strongly \(\mathcal{NP}\) -hard. Consider two special cases, in which the jobs have identical processing times. For the problem with limited outsourcing budgets, a \(\mathcal{NP}\) -hardness proof, a pseudo-polynomial algorithm and a fully polynomial time approximation scheme are presented. For the problem with unlimited outsourcing budgets, the problem is shown to be equivalent to the shortest path problem, and therefore it is in class  \(\mathcal{P}\) . This shortest-path-problem solution approach is further shown to be applicable to a similar but more applicable problem, in which the number of deliveries is upper bounded.     

Efficiently Hex-Meshing Things with Topology

A topological quadrilateral mesh \(Q\) of a connected surface in \(\mathbb {R}^3\) can be extended to a topological hexahedral mesh of the interior domain \(\varOmega \) if and only if \(Q\) has an even number of quadrilaterals and no odd cycle in \(Q\) bounds a surface inside \(\varOmega \) . Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of \(\varOmega \) that respects \(Q\) . Finally, if \(Q\) is given as a polyhedron in \(\mathbb {R}^3\) with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.     

A note on complete rings of quotients and McCoy rings

If a (commutative unital) ring $A$ is reduced and coincides with its total quotient ring, then $A$ satisfies Property A (that is, $A$ is a McCoy ring) if and only if the inclusion of $A$ in its complete ring of quotients $C(A)$ is a survival extension. The ??if?? assertion fails if one deletes the hypothesis that $A$ is reduced. This is shown by using the idealization construction to construct a suitable ring $A$ and then identifying its complete ring of quotients (which turns out to be a related idealization). Related characterizations of von Neumann regular rings are also given with the aid of the going-down property GD of ring extensions. For instance, a ring $A$ is von Neumann regular if and only if $A$ is a reduced McCoy ring that coincides with its total quotient ring such that $A \subseteq C(A)$ satisfies GD.     

Differential variational inequality approach to dynamic games with shared constraints

The dynamic Nash equilibrium problem with shared constraints (NEPSC) involves a dynamic decision process with multiple players, where not only the players’ cost functionals but also their admissible control sets depend on the rivals’ decision variables through shared constraints. For a class of the dynamic NEPSC, we propose a differential variational inequality formulation. Using this formulation, we show the existence of solutions of the dynamic NEPSC, and develop a regularized smoothing method to find a solution of it. We prove that the regularized smoothing method converges to the least norm solution of the differential variational inequality, which is a solution of the dynamic NEPSC as the regularization parameter \(\lambda \) and smoothing parameter \(\mu \) go to zero with the order \(\mu =o(\lambda )\) . Numerical examples are given to illustrate the existence and convergence results.     

Smoothed performance guarantees for local search

We study popular local search and greedy algorithms for standard machine scheduling problems. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat contrived and it is questionable whether they arise in practical applications. To find out how robust these bounds are, we study the algorithms in the framework of smoothed analysis, in which instances are subject to some degree of random noise. While the lower bounds for all scheduling variants with restricted machines are rather robust, we find out that the bounds are fragile for unrestricted machines. In particular, we show that the smoothed performance guarantee of the jump and the lex-jump algorithm are (in contrast to the worst case) independent of the number of machines. They are  \(\Theta (\phi )\) and  \(\Theta (\log \phi )\) , respectively, where  \(1/\phi \) is a parameter measuring the magnitude of the perturbation. The latter immediately implies that also the smoothed price of anarchy is  \(\Theta (\log \phi )\) for routing games on parallel links. Additionally, we show that for unrestricted machines also the greedy list scheduling algorithm has an approximation guarantee of   \(\Theta (\log \phi )\) .     

Extended Formulations for Polygons

The extension complexity of a polytope?P is the smallest integer?k such that?P is the projection of a polytope?Q with?k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(logn), a result originating from work by Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 193?C205, 2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of $\sqrt{2n}$ on the extension complexity of generic n-gons. Finally, we prove that there exist n-gons whose vertices lie on an O(n)×O(n ²) integer grid with extension complexity $\varOmega (\sqrt{n}/\sqrt{\log n})$ .     

On convex relaxations for quadratically constrained quadratic programming

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let $\mathcal{F }$ denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on $\mathcal{F }$ is dominated by an alternative methodology based on convexifying the range of the quadratic form $\genfrac(){0.0pt}{}{1}{x}\genfrac(){0.0pt}{}{1}{x}^T$ for $x\in \mathcal{F }$ . We next show that the use of ?? $\alpha $ BB?? underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. (??difference of convex??) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.     

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

In this paper, we study the problem of moving $n$ n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^2\log n)$ O ( n 2 log n ) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ O ( n 2 ) time. We present an $O(n\log n)$ O ( n log n ) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ O ( n ) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ O ( n ) time, improving the previously best $O(n^2)$ O ( n 2 ) time solution.     

Nonconventional large deviations theorems

We obtain large deviations theorems for both discrete time expressions of the form $\sum _{n=1}^NF\big (X(q_1(n)),\ldots ,X(q_\ell (n))\big )$ and similar expressions of the form $\int _0^TF\big ( X(q_1(t)),\ldots , X(q_\ell (t))\big )dt$ in continuous time. Here $X(n),n\ge 0$ or $X(t), t\ge 0$ is a Markov process satisfying Doeblin’s condition, $F$ is a bounded continuous function and $q_i(n)=in$ for $i\le k$ while for $i>k$ they are positive functions taking on integer values on integers with some growth conditions which are satisfied, for instance, when $q_i$ ’s are polynomials of increasing degrees. Applications to some types of dynamical systems such as mixing subshifts of finite type and hyperbolic and expanding transformations will be obtained, as well.     

Norm-Constrained Determinantal Representations of Multivariable Polynomials

For every multivariable polynomial $p$ , with $p(0)=1$ , we construct a determinantal representation, $ p=\det (I - K Z )$ , where $Z$ is a diagonal matrix with coordinate variables on the diagonal and $K$ is a complex square matrix. Such a representation is equivalent to the existence of $K$ whose principal minors satisfy certain linear relations. When norm constraints on $K$ are imposed, we give connections to the multivariable von Neumann inequality, Agler denominators, and stability. We show that if a multivariable polynomial $q$ , $q(0)=0,$ satisfies the von Neumann inequality, then $1-q$ admits a determinantal representation with $K$ a contraction. On the other hand, every determinantal representation with a contractive $K$ gives rise to a rational inner function in the Schur–Agler class.     

Boundaries of Disk-Like Self-affine Tiles

Let $T:= T(A, \mathcal{D })$ T : = T ( A , D ) be a disk-like self-affine tile generated by an integral expanding matrix $A$ A and a consecutive collinear digit set $\mathcal{D }$ D , and let $f(x)=x^{2}+px+q$ f ( x ) = x 2 + px + q be the characteristic polynomial of $A$ A . In the paper, we identify the boundary $\partial T$ ? T with a sofic system by constructing a neighbor graph and derive equivalent conditions for the pair $(A,\mathcal{D })$ ( A , D ) to be a number system. Moreover, by using the graph-directed construction and a device of pseudo-norm $\omega $ ω , we find the generalized Hausdorff dimension $\dim _H^{\omega } (\partial T)=2\log \rho (M)/\log |q|$ dim H ω ( ? T ) = 2 log ρ ( M ) / log | q | where $\rho (M)$ ρ ( M ) is the spectral radius of certain contact matrix $M$ M . Especially, when $A$ A is a similarity, we obtain the standard Hausdorff dimension $\dim _H (\partial T)=2\log \rho /\log |q|$ dim H ( ? T ) = 2 log ρ / log | q | where $\rho $ ρ is the largest positive zero of the cubic polynomial $x^{3}-(|p|-1)x^{2}-(|q|-|p|)x-|q|$ x 3 ? ( | p | ? 1 ) x 2 ? ( | q | ? | p | ) x ? | q | , which is simpler than the known result.     

Computing modular Galois representations

We compute modular Galois representations associated with a newform $f$ , and study the related problem of computing the coefficients of $f$ modulo a small prime $\ell $ . To this end, we design a practical variant of the complex approximations method presented in Edixhoven and Couveignes (Ann. of Math. Stud., vol. 176, Princeton University Press, Princeton, 2011). Its efficiency stems from several new ingredients. For instance, we use fast exponentiation in the modular jacobian instead of analytic continuation, which greatly reduces the need to compute abelian integrals, since most of the computation handles divisors. Also, we introduce an efficient way to compute arithmetically well-behaved functions on jacobians, a method to expand cuspforms in quasi-linear time, and a trick making the computation of the image of a Frobenius element by a modular Galois representation more effective. We illustrate our method on the newforms $\Delta $ and $E_4 \cdot \Delta $ , and manage to compute for the first time the associated faithful representations modulo $\ell $ and the values modulo $\ell $ of Ramanujan’s $\tau $ function at huge primes for $\ell \in \{ 11,13,17,19,29\}$ . In particular, we get rid of the sign ambiguity stemming from the use of a projective representation as in Bosman (On the computation of Galois representations associated to level one modular forms. arxiv.org/abs/0710.1237, 2007). As a consequence, we can compute the values of $\tau (p)~\mathrm{mod}~2^{11} \times 3^6 \times 5^3 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 691 \approx 2.8 \times 10^{19}$ for huge primes $p$ . The representations we computed lie in the jacobian of modular curves of genus up to $22$ .     

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.     

Über pseudoaffine Räume

For pseudoaffine spaces (P, \(\mathfrak{G}\) ) of order 3 the following questions are answered: 1) Let τ be a “translation” of (P, \(\mathfrak{G}\) ) which fixes all lines parallel to a given line A. Are lines X,Y ∥ A parallel? 2) Are there pseudoaffine euclidean spaces which are not affine? 3) How are pseudoaffine spaces characterized which are derivated from groups of exponent 3?