Quality as Vector, Focus for Strengthening and Agreement

In algorithms we are concerned with the quality of solutions that we can achieve for a given computational problem translating instances into solutions. We use the quality function to measure the quality of a solution. In earlier homeworks, the quality was one number (e.g., the depth of a decision tree in the HSR problem). In later homeworks, we used an expression to represent the quality (e.g., the running-time expression for an algorithm).

In the network flow playground we started to use a vector of numbers to represent the quality. We had the first element q1 represent the value of the max flow and the second element q2 represents the resource consumption (JVM instruction count). We are going to formalize what Serge and Victor did: You can strengthen or agree only for a subvector of the quality vector. We call the subvector the "focus". When you agree or strengthen you must declare your focus.

We need to define what refutation and strengthening and agreement mean in the presence of quality vectors.

Focus and Strengthening and Agreement 

If the quality vector is q =(q1,q2), we have the following
cases:
(q1,q2) is the quality claimed by proposer
(q1',q2') is the quality achieved by opposing/agreeing scholar

	q1	q2
up      q1'	q2'
better quality for q1 and q2 means a larger number.

if focus (q1,q2): strengthen = ((q1'>q1) and (q2'>=q2)) or 
                           ((q1'>=q1) and (q2'>q2))
              agree = (q1'=q1) and (q2'=q2)

if focus (q1): strengthen = (q1'>q1)
           agree = (q1'=q1)

if focus (q2): strengthen = (q2'>q2)
           agree = (q2'=q2)
Next we consider the case when for the first compenent better quality means a greater number and for the second component a smaller number. 
	q1	q2
up      q1'	
down		q2'
better quality for q1 means a larger number
and better quality for q2 means a smaller number.

if focus (q1,q2): strengthen = ((q1'>q1) and (q2'<=q2)) or 
                           ((q1'>=q1) and (q2' < q2))

if focus (q1): strengthen = (q1'>q1)
           agree = (q1'=q1)

if focus (q2): strengthen = (q2' < q2)
           agree = (q2'=q2)
etc. The above rules easily generalize to multiple components.

Example for Triple

For homework 10 we have three components in the quality vector: q1=vFlowBefore,q2=vFlowAfter,q3=vJVMcount. q1: up is better, q2: down is better, q3: down is better. Examples of strengthening are: Focus q1: opposer has a greater flow q1'. Focus q1,q2: opposer has an equal flow for q1 but a smaller max flow for q2. Focus q1,q2,q3: opposer has an equal flow for q1 and q2 but a lower resource consumption for q3.

Refutation for Quality Vectors

The focus is on all components of the quality vector. The proposer cannot provide a solution that is equal to or better than the claimed quality for all components.