In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We present a new 2 ^K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2^N/6 bound, where N is the number of variables in an input formula, for a particular case of MAX-2-SAT, where each variable appears in at most three 2-clauses. This immediately implies a 2^N/6 bound, where N is the number of vertices in an input graph, for the independent set problem on 3-regular graphs. The key point of our improvement is a combined complexity measure for estimating the running time of an algorithm. By using a new complexity measure we are able to provide a much simpler proof of new upper bounds for MAX-2-SAT than proofs of previously known bounds.