A multiple criteria sorting method where each category is characterized by several reference actions: The Electre Tri-nC method

This paper presents Electre Tri-nC, a new sorting method which takes into account several reference actions for characterizing each category. This new method gives a particular freedom to the decision maker in the co-construction decision aiding process with the analyst to characterize the set of categories, while there is no constraint for introducing only one reference action as typical of each category like in Electre Tri-C (Almeida-Dias et al., 2010). As in such a sorting method, this new sorting method is composed of two joint rules. Electre Tri-nC also fulfills a certain number of natural requirements. Additional results on the behavior of the new method are also provided in this paper, namely the ones with respect to the addition or removal of the reference actions used for characterizing a certain category. A numerical example illustrates the manner in which Electre Tri-nC can be used by a decision maker. A comparison with some related sorting procedures is presented and it allows to conclude that the new method is appropriate to deal with sorting problems.     

The final NETLIB-LP results

With standard linear programming solvers there is always some uncertainty about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the exact optimal objective values for all NETLIB problems.     

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F={K₂}. In this paper we provide new approximation algorithms and hardness results for the K_r-packing problem where K_r={K₂,K₃,…,K_r}.We show that already for r=3 the K_r-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r=3,4,5 we obtain better approximations. For r=3 we obtain a simple3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For r=4, we obtain a (3/2+?)-approximation, and for r=5 we obtain a (25/14+?)-approximation.     

On the complexity of scheduling unit-time jobs with OR-precedence constraints

We present various complexity results for scheduling unit-time jobs subject to OR-precedence constraints. We prove that minimizing the total weighted completion time is strongly NP-hard, even on a single machine. In contrast, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines.     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, max independent set and min vertex cover.     

The d-precoloring problem for k-degenerate graphs

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted to the class of partial k-trees (without any size restriction on S). We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.     

Eigenfunctions of the Laplace operators for a building of type[(A)\tilde]2\tilde A_2

Let Δ be a thick affine building of type and of order q. We prove that each eigenfunction of the Laplace operators of Δ is the Poisson transform of a suitable finitely additive measure on the maximal boundary Ω.     

A note on plurisubharmonic defining functions in \mathbbCn{\mathbb{C}^{n}}

Let , n ≥ 3, be a smoothly bounded domain. Suppose that Ω admits a smooth defining function which is plurisubharmonic on the boundary of Ω. Then a Diederich–Forn?ss exponent can be chosen arbitrarily close to 1, and the closure of Ω admits a Stein neighborhood basis. Research of J. E. Forn?ss was partially supported by an NSF grant. Research of A.-K. Herbig was supported by FWF grant P19147.     

clever or smart: Strategies for the online target date assignment problem

In this paper, we consider the Online Target Date Assignment Problem (OnlineTDAP) for general downstream problems, where the downstream cost are nonnegative, additive and satisfy the triangle inequality.We analyze algorithm smart, which was introduced by Angelelli et al. [3] and give its exact competitive ratio depending on the number of requests. Since the obtained competitive ratio is at most we answer the question posed in Angelelli et al. [4] if smart has a competitive ratio strictly less than 2.Moreover, we introduce a new algorithm called clever and show that this strategy has a competitive ratio of 3/2. We show that this is asymptotically optimal by proving that no online algorithm can perform better than 3/2−ε.     

Hard coloring problems in low degree planar bipartite graphs

In this paper we prove that the PRECOLORING EXTENSION problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4.The restricted version of LIST COLORING, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.     

On an obstacle problem for degenerate elliptic operators involving the critical Sobolev exponent

We establish the existence of a solution to the variational inequality (the obstacle problem) (1.1) which involves the critical Sobolev exponent. This result is also extended to an obstacle problem with a lower order perturbation. Dedicated to Professor F. Browder on the occasion of his 80-th birthday     

Repetition-free longest common subsequence

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard.     

Approximation results for the weighted partition problem

We present several new standard and differential approximation results for the P₄-partition problem using the Hassin and Rubinstein algorithm [Information Processing Letters 63 (1997) 63–67]. Those results concern both minimization and maximization versions of the problem. However, the main point of this paper lies in the establishment of the robustness of this algorithm, in the sense that it provides good quality solutions for a variety of versions of the problem, under both standard and differential approximation ratios.     

On the number of singularities for the obstacle problem in two dimensions

We study the obstacle problem in two dimensions. On the one hand we improve a result of L.A. Caffarelli and N.M. Rivière: we state that every connected component of the interior of the coincidence set has at most N ₀ singular points, where N ₀ is only dependent on some geometric constants. Moreover, if the component is small enough, then this component has at most two singular points. On the other hand, we prove in a simple case a conjecture of D.G. Schaeffer on the generic regularity of the free boundary: for a family of obstacle problems in two dimensions continuously indexed by a parameter λ, the free boundary of the solution u_λ is analytic for almost every λ. Finally we present a new monotonicity formula for singular points. Dedicated to Henri Berestycki and Alexis Bonnet.     

The mixed problem in <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> for some two-dimensional Lipschitz domains

We consider the mixed problem,

The Cauchy problem in Sobolev spaces for Dirac operators

In this paper we consider the Cauchy problem as a typical example of ill-posed boundary-value problems. We obtain the necessary and (separately) sufficient conditions for the solvability of the Cauchy problem for a Dirac operator A in Sobolev spaces in a bounded domain D ? ? ⁿ with a piecewise smooth boundary. Namely, we reduce the Cauchy problem for the Dirac operator to the problem of harmonic extension from a smaller domain to a larger one. Moreover, along with the solvability conditions for the problem, using bases with double orthogonality, we construct a Carleman formula for recovering a function u in a Sobolev space H ^s (D), s ∈ ?, from its values on Γ and values Au in D, where Γ is an open connected subset of the boundary ?D. It is worth pointing out that we impose no assumptions about geometric properties of the domain D, except for its connectedness.     

The large-time behavior of solutions of the Cauchy-Dirichlet problem for Hamilton-Jacobi equations

We investigate the large-time behavior of viscosity solutions of the Cauchy-Dirichlet problem (CD) for Hamilton-Jacobi equations on bounded domains. We establish general convergence results for viscosity solutions of (CD) by using the Aubry-Mather theory.