We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position.

A gap - [ k ] - vertex-labelling of a graph G is a pair ( π , c π ) , where π : V ( G ) → [ k ] and c π : V ( G ) → { 0 , 1 , … , k } is a proper colouring of G such that, for v ∈ V ( G ) , c π ( v ) = max u ∈ N ( v ) { π ( u ) } − min u ∈ N ( v ) { π ( u ) } , if d ( v ) ≥ 2 , and c π ( v ) = π ( u ) u ∈ N ( v ) , otherwise. In this paper, we present an upper bound of O ( n 2 ) for the vertex-gap number of arbitrary graphs, which is the least number k such that G admits a gap- [ k ] -vertex-labelling. We prove that, for n ≥ 4 , K n does not admit any gap-vertex-labelling, regardless of the number of labels. We also characterize the powers of cycles and paths that admit gap-vertex-labellings. Furthermore, we introduce a novel parameter, the gap-strength of a graph, denoted by str gap ( G ) , which is the least number of edges that must be removed from a graph, so it will have a gap-vertex-labelling, and prove that str gap ( K n ) ∈ Ω ( n 6 / 5 ) and str gap ( K n ) ∈ O ( n 3 / 2 ) .

In the classical Travelling Salesman Problem (TSP), one wants to find a route that visits a set of n cities, such that the total travelled distance is minimum. An often considered generalization is the Travelling Car Renter Problem (CaRS), in which the route is travelled by renting a set of cars and the cost to travel between two given cities depends on the car that is used. The car renter may choose to swap vehicles at any city, but must pay a fee to return the car to its pickup location. This problem appears in logistics and urban transportation when the vehicles can be provided by multiple companies, such as in the tourism sector. In this paper, we consider the case in which the return fee is some fixed number g >= 0, which we call the Uniform CaRS (UCaRS). We show that, already for this version, there is no o(log n)-approximation algorithm unless P = NP. The main contribution is an O(log n)-approximation algorithm for the problem, which is based on the randomized rounding of an exponentially large LP-relaxation.

A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S,V\S] of G such that G[S] and G[V\S] are both connected. Given s,t in V(G), an st-bond of G is a bond whose removal disconnects s and t. Contrasting with the large number of studies related to maximum cuts, there are very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond and the largest st-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that Largest Bond remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless P = NP. We also show that Largest Bond and Largest st-Bond on graphs of clique-width w cannot be solved in time f(w) x n^{o(w)} unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) x n^{O(w)}. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP subseteq coNP/poly.

Wireless sensor networks consist of hundreds or thousands of nodes with limited energy resources. Due to the high density of nodes in this kind of network, redundant data will be detected by nearby nodes. Since the network lifetime is a key issue in wireless sensor networks, in-network data aggregation can be exploited in order to reduce the number of messages exchanged and consequently reduce the energy consumption. Although there are many data aggregation solutions in wireless sensor networks, most of them leads to low quality routing trees and does not address the load balancing problem, since the same tree is used throughout the network life. To tackle these challenges we propose a Continuous Enhancement Routing Solution named as CER, an approach for computing increasingly better routing trees. CER was extensively compared to three other known solutions: the Shortest Path Tree (SPT), Data Aggregation Aware Routing Protocol (DAARP) and Dynamic Data Aggregation Aware Routing Protocol (DDAARP). The obtained results show that CER outperforms these solutions in all evaluations performed.