Frontiers in Algorithmics and Algorithmic Aspects in Information and Management

A

floorplan

is a rectangle subdivided into smaller rectangular

blocks

by horizontal and vertical line segments. Two floorplans are considered equivalent if and only if there is a bijection between the blocks in the two floorplans such that the corresponding blocks have the same horizontal and vertical boundaries.

Mosaic floorplans

use the same objects as floorplans but use an alternative definition of equivalence. Two mosaic floorplans are considered equivalent if and only if they can be converted into equivalent floorplans by sliding the line segments that divide the blocks. The

Quarter-State Sequence

method of representing mosaic floorplans uses 4

n

bits, where

n

is the number of blocks. This paper introduces a method of representing an

n

-block mosaic floorplan with a (3

n

 − 3)-bit binary string. It has been proven that the shortest possible binary string representation of a mosaic floorplan has a length of (3

n

 − 

o

(

n

)) bits. Therefore, the representation presented in this paper is asymptotically optimal.

Baxter permutations

are a set of permutations defined by prohibited subsequences. There exists a bijection between mosaic floorplans and Baxter permutations. As a result, the methods introduced in this paper also create an optimal binary string representation of Baxter permutations.

Geometric routing by using virtual locations is an elegant way for solving network routing problems. Greedy routing, where a message is simply forwarded to a neighbor that is closer to the destination, is a simple form of geometric routing. Papadimitriou and Ratajczak conjectured that every 3-connected plane graph has a greedy drawing in the

$\mathcal R^2$

plane [10]. Leighton and Moitra settled this conjecture positively in [9]. However, their drawings have two major drawbacks: (1) their drawings are not necessarily planar; and (2) Ω(

n

log

n

) bits are needed to represent the coordinates of their drawings, which is too large for routing algorithms for wireless networks. Recently, He and Zhang [8] showed that every triangulated plane graph has a succinct (using

O

(log

n

) bit coordinates) greedy drawing in

$\mathcal R^2$

plane with respect to a metric function derived from Schnyder realizer. However, their method fails for 3-connected plane graphs. In this paper, we show that every 3-connected plane graph has drawing in the

$\mathcal R^2$

plane, that is succinct, planar, strictly convex, and is greedy with respect to a metric function based on parameters derived from Schnyder wood.

An inverse optimization problem is defined as follows: Let

S

denote the set of feasible solutions of an optimization problem

P

, let

c

be a specified cost (capacity) vector , and

x

0

 ∈ 

S

. We want to perturb the cost (capacity) vector

c

to

d

such that

x

0

becomes an optimal solution of

P

with respect to the cost (capacity) vector

d

, and to minimize some objective functions. In this paper, we consider the weighted inverse minimum cut problem under the sum-type Hamming distance. First, we show the general case is NP-hard. Second we present a combinatorial algorithm that run in strongly polynomial time to solve a special case.

In a normal Voronoi diagram, each site is able to see all the points in the plane. In this paper, we study the case such that each site is only able to see a visually restricted region in the plane and construct the so-called Visual Restriction Voronoi Diagram (VRVD). We show that the visual restriction Voronoi cell of each site is not necessary convex and it could consist of many disjoint regions. We prove that the combinatorial complexity of the VRVD on

n

sites is Θ(

n

2

). Then we give an

O

(

n

2

log

n

) time and

O

(

n

2

) space algorithm to construct VRVD.

The

two-guard

problem asks whether two guards can walk to detect an unpredictable, moving target in a polygonal region

P

, no matter how fast the target moves, and if so, construct a walk schedule of the guards. For safety, two guards are required to always be mutually visible, and thus, they move on the polygon boundary. Specially, a

straight walk

requires both guards to monotonically move on the boundary of

P

from beginning to end, one clockwise and the other counterclockwise.

The objective of this paper is to find an optimum straight walk such that the

maximum

distance between the two guards is minimized. We present an

O

(

n

2

log

n

) time algorithm for optimizing this metric, where

n

is the number of vertices of the polygon

P

. Our result is obtained by investigating a number of new properties of the

min-max

walks and converting the problem of finding an optimum walk in the min-max metric into that of finding a shortest path between two nodes in a graph. This answers an open question posed by Icking and Klein.

We point out mistakes in several previous FPT algorithms for

k

-Link Covering Tour

and its variants in ℝ

2

, and show that the previous NP-hardness proofs for

Minimum-Link Rectilinear Covering Tour

and

Minimum-Link Rectilinear Spanning Path

in ℝ

3

are incorrect. We then present new NP-hardness proofs for the two problems in ℝ

10

.

In a centralized combinatorial market, the market maker has a number of items for sale to potential consumers, who wish to purchase their preferred items. Different solution concepts (allocations of items to players) capture different perspectives in the market. Our focus is to balance three properties: revenue maximization from the market maker’s perspective, fairness from consumers’ perspective, and efficiency from the market’s global perspective.

Most well-known solution concepts capture only one or two properties, e.g., Walrasian equilibrium requires fairness for consumers and uses market clearance to guarantee efficiency but ignores revenue for the market maker. Revenue maximizing envy-free pricing balances market maker’s revenue and consumer’s fairness, but ignores efficiency.

In this paper, we study a solution concept, envy-free Pareto efficient pricing, that lies between Walrasian equilibrium and envy-free pricing. It requires fairness for consumers and balances efficiency and revenue. We study envy-free Pareto efficient pricing in two domains, unit-demand and single-minded consumers, and analyze its existence, computation, and economic properties.

In this paper, we study the problem of online pricing for bundles of items. Given a seller with

k

types of items,

m

of each, a sequence of users {

u

1

,

u

2

, ...} arrives one by one. Each user is single-minded, i.e., each user is interested only in a particular bundle of items. The seller must set the price and assign some amount of bundles to each user upon his/her arrival. Bundles can be sold fractionally. Each

u

i

has his/her value function

v

i

(·) such that

v

i

(

x

) is the highest unit price

u

i

is willing to pay for

x

bundles. The objective is to maximize the revenue of the seller by setting the price and amount of bundles for each user. In this paper, we first show that the lower bound of the competitive ratio for this problem is Ω(log

h

 + log

k

), where

h

is the highest unit price to be paid among all users. We then give a deterministic online algorithm, Pricing, whose competitive ratio is

$O(\sqrt{k}\cdot\log h\log k)$

. When

k

 = 1 the lower and upper bounds asymptotically match the optimal result

O

(log

h

).

In previous study on comparing the makespan of the schedule allowed to be preempted at most

i

times and that of the optimal schedule with unlimited number of preemptions, the worst case ratio was usually obtained by analyzing the structures of the optimal schedules. For

m

identical machines case, the worst case ratio was shown to be 2

m

/(

m

 + 

i

 + 1) for any 0 ≤ 

i

 ≤ 

m

 − 1[1], and they showed that

LPT

algorithm is an exact algorithm which can guarantee the worst case ratio for

i

 = 0. In this paper, we propose a simpler method which is based on the design and analysis of the algorithm and finding an instance in the worst case. It can obtain the worst case ratio as well as the algorithm which can guarantee this ratio for any 0 ≤ 

i

 ≤ 

m

 − 1, and thus we generalize the previous results. We also make a discussion on the trade-off between the objective value and the number of preemptions. In addition, we consider the

i

-preemptive scheduling on two uniform machines. For both

i

 = 0 and

i

 = 1, we present the algorithms and give the worst-case ratios with respect to

s

, i.e., the ratio of the speeds of two machines.

We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of

n

vertices and

m

edges, we present an

O

(

n

log

n

) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm for this problem takes

O

(

m

 + 

n

log

n

) time. Since

m

 = Θ(

n

2

) in the worst case, our result improves the previous solution for large

m

.

Let

G

be a simple graph in which each vertex

v

has a positive integer weight

b

(

v

) and each edge (

v

,

w

) has a nonnegative integer weight

b

(

v

,

w

). A bandwidth consecutive multicoloring of

G

assigns each vertex

v

a specified number

b

(

v

) of consecutive positive integers so that, for each edge (

v

,

w

), all integers assigned to vertex

v

differ from all integers assigned to vertex

w

by more than

b

(

v

,

w

). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given series-parallel graph with the minimum span. We finally extend the results to the case where a given graph

G

is a partial

k

-tree, that is,

G

has a bounded tree-width.

An independent dominating set in a graph is a subset of vertices, such that every vertex outside this subset has a neighbor in this subset (dominating), and the induced subgraph of this subset contains no edge (independent). It was known that finding the minimum independent dominating set (Independent Domination) is

$\cal{NP}$

-complete on bipartite graphs, but tractable on convex bipartite graphs. A bipartite graph is called tree convex, if there is a tree defined on one part of the vertices, such that for every vertex in another part, the neighborhood of this vertex is a connected subtree. A convex bipartite graph is just a tree convex one where the tree is a path. We find that the sum of larger-than-two degrees of the tree is a key quantity to classify the computational complexity of independent domination on tree convex bipartite graphs. That is, when the sum is bounded by a constant, the problem is tractable, but when the sum is unbounded, and even when the maximum degree of the tree is bounded, the problem is

$\cal{NP}$

-complete.

We consider the on-line scheduling of parallel jobs in heterogeneous multiple clusters, in which a set of clusters is given and the parallel jobs arrive one by one, and the goal is to schedule all the jobs while minimizing the makespan. A cluster consists of many identical processors. A parallel job may require several processors in one cluster to execute it simultaneously. In this paper, we investigate two variants of the heterogeneous clusters. First, for the clusters of different widths (number of processors) but identical processor speeds, we provide an on-line algorithm with a competitive ratio at most of 14.2915. Second, for the clusters of different speeds but identical widths, we provide an on-line algorithm with a competitive ratio at most of 18.2788.

We study temperature-aware scheduling problems under the model introduced by Chrobak et al. in [9], where unit-length jobs of given heat contributions are to be scheduled on a set of parallel identical processors. We consider three optimization criteria: makespan, maximum temperature and (weighted) average temperature. On the positive side, we present polynomial time approximation algorithms for the minimization of the makespan and the maximum temperature, as well as, optimal polynomial time algorithms for minimizing the average temperature and the weighted average temperature. On the negative side, we prove that there is no

$(\frac{4}{3}-\epsilon)$

-approximation algorithm for the problem of minimizing the makespan for any

ε

 > 0, unless

${\cal P}={\cal NP}$

.

In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results, which improve on work from FOCS 2008: i) for

m

identical machines, we give a 1.5-competitive online algorithm with a buffer of size 1.5

m

, which is better than the previous best result : 1.5-competitive algorithm with a buffer of size 1.6197

m

; ii) for three identical machines, to give an optimal online algorithm we reduce the size of the buffer from nine to six; iii) for

m

uniform machines, using a buffer of size

m

, we improve the competitive ratio from 2 + 

ε

to 2 − 1/

m

 + 

ε

, where

ε

 > 0 is sufficiently small.

The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes

a

1

,…,

a

n

in (0,1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized

$O({n(\log\log n)\over \sum_{i=1}^n a_i}+({1\over \epsilon})^{O({1\over\epsilon})})$

time (1 + 

ε

)-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs

$\Omega({n\over \sum_{i=1}^n a_i})$

time to give an (1 + 

ε

)-approximation. For each function

s

(

n

):

N

 → 

N

, define ∑ (

s

(

n

)) to be the set of all bin packing problems with the sum of item sizes equal to

s

(

n

). We show that ∑ (

n

b

) is NP-hard for every

b

 ∈ (0,1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1 + 

ε

)-approximation in

$({1\over \epsilon})^{O({1\over\epsilon})}$

time. Let

S

(

δ

)-bin packing be the class of bin packing problems with each input item of size at least

δ

. This research also gives a natural example of NP-hard problem (

S

(

δ

)-bin packing) that has a constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where

δ

is a positive constant.

We investigate the complexity of approximate integration and differentiation for multivariate polynomials in the standard computation model. For a functor

F

(·) that maps a multivariate polynomial to a real number, we say that an approximation

A

(·) is a

factor

$\alpha\colon N \to N^+$

approximation

iff for every multivariate polynomial

f

with

A

(

f

) ≥ 0,

$\frac{F(f)}{\alpha(n)} \le A(f) \le \alpha(n)F(f)$

, and for every multivariate polynomial

f

with

F

(

f

) < 0,

$\alpha(n) F(f) \le A(f) \le \frac{F(f)}{\alpha(n)}$

, where

n

is the length of

f

,

$\textit{len}(f)$

.

For integration over the unit hypercube, [0,1]

d

, we represent a multivariate polynomial as a product of sums of quadratic monomials:

f

(

x

1

,…,

x

d

) = ∏ 

1 ≤ 

i

 ≤ 

k

p

i

(

x

1

,…,

x

d

), where

p

i

(

x

1

,…,

x

d

) = ∑ 

1 ≤ 

j

 ≤ 

d

q

i

,

j

(

x

j

), and each

q

i

,

j

(

x

j

) is a single variable polynomial of degree at most two and constant coefficients. We show that unless P = NP there is no

$\alpha\colon N\to N^+$

and

A

(·) that is a factor

α

polynomial-time approximation for the integral

$I_d(f) = \int_{[0,1]^d} f(x_1,\ldots , x_d)d\,x_1,\ldots,d\,x_d$

.

For differentiation, we represent a multivariate polynomial as a product quadratics with 0,1 coefficients. We also show that unless P = NP there is no

$\alpha\colon N\to N^+$

and

A

(·) that is a factor

α

polynomial-time approximation for the derivative

$\frac{\partial f(x_1,\ldots , x_d)}{\partial x_1,\ldots,\partial x_d}$

at the origin (

x

1

, …,

x

d

) = (0, …, 0). We also give some tractable cases of high dimensional integration and differentiation.

Compressibility of a formula regards reducing the length of the input, or some other parameter, while preserving the solution. Any 3-

SAT

instance on

N

variables can be represented by

O

(

N

3

) bits; [4] proved that the instance length in general cannot be compressed to

O

(

N

3 − 

ε

) bits under the assumption

$\mathbf{NP}\not\subseteq\mathbf{coNP}$

/poly

, which implies that the polynomial hierarchy does not collapse. This note initiates research on compressibility of

SAT

instances parameterized by width parameters, such as tree-width or path-width. Let

SAT

tw

(

w

(

n

)) be the satisfiability instances of length

n

that are given together with a tree-decomposition of width

O

(

w

(

n

)), and similarly let

SAT

pw

(

w

(

n

)) be instances with a path-decomposition of width

O

(

w

(

n

)). Applying simple techniques and observations, we prove conditional incompressibility for both instance length and width parameters: (i) under the exponential time hypothesis, given an instance

φ

of

SAT

tw

(

w

(

n

)) it is impossible to find within polynomial time a

φ

′ that is satisfiable if and only if

φ

is satisfiable and tree-width of

φ

′ is half of

φ

; and (ii) assuming a scaled version of

$\mathbf{NP}\not\subseteq\mathbf{coNP}$

/poly

, any 3-

SAT

pw

(

w

(

n

)) instance of

N

variables cannot be compressed to

O

(

N

1 − 

ε

) bits.

We show how the notion of combinatorial duality, related to the well-known notion of duality from linear programming, may be used for translating kernel results obtained for packing problems into kernel results for covering problems. We exemplify this approach by having a closer look at the problems of packing a graph with vertex-disjoint trees with

r

edges. We also improve on the best known kernel size for packing graphs with trees containing two edges, which has been well studied.

The rigorous theoretical analyses of algorithms for exact 3-satisfiability (X3SAT) have been proposed in the literature. As we know, previous algorithms for solving X3SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving X3SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i.e. the number of clauses. In this paper, we present algorithms for solving X3SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds

O

(1.15855

m

), where

m

is the number of clauses.

Let

I

be an instance of binary boolean CSP. Consider the problem of deciding whether one can remove at most

k

constraints of

I

such that the remaining constraints are satisfiable. We call it the

Almost CSP

problem. This problem is

NP

-complete and we study it from the point of view of parameterized complexity where

k

is the parameter. Two special cases have been studied: when the constraints are inequality relations (Guo et al., WADS 2005) and when the constraints are

OR

type relations (Razgon and O’Sullivan, ICALP 2008). Both cases are shown to be fixed-parameter tractable (FPT). In this paper, we define a class of

decisive

relations and show that when all the relations are in this class, the problem is also fixed-parameter tractable. Note that the inequality relation is decisive, thus our result generalizes the result of the parameterized edge-bipartization problem (Guo et al., WADS 2005). Moreover as a simple corollary, if the set of relations contains no

OR

type relations, then the problem remains fixed-parameter tractable. However, it is still open whether

OR

type relations and other relations can be combined together while the fixed-parameter tractability still holds.

In this paper, we introduce and study three graph modification problems:

2-Club Cluster Vertex Deletion

,

2-Club Cluster Edge Deletion

, and

2-Club Cluster Editing

. In

2-Club Cluster Vertex Deletion

(

2-Club Cluster Edge Deletion

, and

2-Club Cluster Editing

), one is given an undirected graph

G

and an integer

k

 ≥ 0, and needs to decide whether it is possible to transform

G

into a 2-club cluster graph by deleting at most

k

vertices (by deleting at most

k

edges, and by deleting and adding totally at most

k

edges). Here, a 2-club cluster graph is a graph in which every connected component is of diameter 2. We first prove that all these three problems are NP-complete. Then, we present for

2-Club Cluster Vertex Deletion

a fixed parameter algorithm with running time

O

 ∗ 

(3.31

k

), and for

2-Club Cluster Edge Deletion

a fixed parameter algorithm with running time

O

 ∗ 

(2.74

k

).

In a classical constrained optimization problem, the logical relationship among the constraints is normally the logical conjunction. However, in many real applications, the relationship among the constraints might be more complex. This paper investigates a generalized class of optimization problems whose constraints are connected by various kinds of logical operators in addition to conjunction. Such optimization problems have been rarely studied in literature in contrast to the classical ones. A framework which integrates classical optimization procedures into the DPLL(T) architecture for solving Satisfiability Modulo Theories (SMT) problems is proposed. Two novel techniques for improving the solving efficiency w.r.t. linear arithmetic theory are also presented. Experiments show that the proposed techniques are quite effective.

In this paper, we propose an OBDD-based algorithm called greedy clique decomposition, which is a new variable grouping heuristic method, to solve difficult SAT problems. We implement our algorithm and compare it with several state-of-art SAT solvers including Minisat, Ebddres and TTS. We show that with this new heuristic method, our implementation of an OBDD-based satisfiability solver can perform better for selected difficult SAT problems, whose conflict graphs possess a clique-like structure.

As an analogous concept of a nowhere-zero flow for directed graphs, we consider zero-sum flows for undirected graphs in this article. For an undirected graph

G

, a

zero-sum flow

is an assignment of non-zero integers to the edges such that the sum of the values of all edges incident with each vertex is zero, and we call it a

zero-sum

k

-flow

if the values of edges are less than

k

. We define the

zero-sum flow number

of

G

as the least integer

k

for which

G

admitting a zero-sum

k

-flow. In this paper, among others we calculate the zero-sum flow numbers for regular graphs and also the zero-sum flow numbers for Cartesian products of regular graphs with paths.

We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts

n

integers in { 0, 1, 2, ...,

n

1/2

} in

O

((log

n

)

3/2

/loglog

n

) time and

O

(

n

(log

n

/loglog

n

)

1/2

) operations. It also sorts

n

integers in {0, 1, 2,...,

n

 − 1} in

O

((log

n

)

3/2

/loglog

n

) time and

O

(

n

(log

n

/loglog

n

)

1/2

logloglog

n

) operations. Previous best algorithm [13] on both cases has time complexity

O

(log

n

) but operation complexity

O

(

n

(log

n

)

1/2

).

Recent advances in biotechnology and web technology are generating huge collections of similar strings. People now face the problem of storing them compactly while supporting fast pattern searching. One compression scheme called

relative Lempel-Ziv compression

uses textual substitutions from a reference text as follows: Given a (large) set

S

of strings, represent each string in

S

as a concatenation of substrings from a reference string

R

. This basic scheme gives a good compression ratio when every string in

S

is similar to

R

, but does not provide any pattern searching functionality. Here, we describe a new data structure that supports fast pattern searching.

Since the introduction of competitive analysis, a number of alternative measures for the quality of online algorithms have been proposed, but, with a few exceptions, these have generally been applied only to the online problem for which they were developed. Recently, a systematic study of performance measures for online algorithms was initiated [Boyar, Irani, Larsen: WADS 2009], first focusing on a simple server problem. We continue this work by studying a fundamentally different online problem, online search, and the Reservation Price Policies in particular. The purpose of this line of work is to learn more about the applicability of various performance measures in different situations and the properties that the different measures emphasize. We investigate the following analysis techniques: Competitive, Relative Worst Order, Bijective, Average, Relative Interval, and Random Order. In addition, we have established the first optimality proof for Relative Interval Analysis.

This paper considers an online exploration problem in a simple polygon where starting from a point in the interior of a simple polygon, the searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the

intersection graphs

of axis-parallel rectangles and disks in 2D. We first propose

O

(

n

2

log

n

) time in-place algorithms for finding the maximum clique of the intersection graphs of a set of axis-parallel rectangles of arbitrary sizes. For the rectangle intersection graph of fixed height rectangles, the time complexity can be slightly improved to

O

(

n

log

n

 + 

nK

), where

K

is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is

O

(

n

2

log

n

), and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is

O

(

n

2

 + 

mK

4

);

m

is the number of edges in the unit disk intersection graph, and

K

is the size of the largest clique in that graph. It uses

O

(

n

4

) time in-place computation of maximum matching in a bipartite graph, which is of independent interest. All these algorithms need

O

(1) work space in addition to the input array

$\cal R$

.

Given a graph

G

and integers

b

and

w

. The black-and-white coloring problem asks if there exist disjoint sets of vertices

B

and

W

with

|B|=b

and

|W|=w

such that no vertex in

B

is adjacent to any vertex in

W

. In this paper we show that the problem is polynomial when restricted to cographs, distance-hereditary graphs, interval graphs and strongly chordal graphs. We show that the problem is NP-complete on splitgraphs.

The general Bandpass-

B

problem is NP-hard and can be approximated by a reduction into the

B

-set packing problem, with a worst case performance ratio of

O

(

B

2

). When

B

 = 2, a maximum weight matching gives a 2-approximation to the problem. The Bandpass-2 problem, or simply the Bandpass problem, can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present in this paper a

$\frac{36}{19}$

-approximation algorithm for the Bandpass problem, which is the first improvement over the simple maximum weight matching based 2-approximation algorithm.

In [1], whether a target binary string

s

can be represented from a boolean formula with operands chosen from a set of binary strings

W

was studied. In this paper, we first examine selecting a maximum subset

X

from

W

, so that for any string

t

in

X

,

t

is not representable by

X

 ∖ {

t

}. We rephrase this problem as graph, and surprisingly find it give rise to a broad model of edge packing problem, which itself falls into the model of forbidden subgraph problem. Specifically, given a graph

G

(

V

,

E

) and a constant

c

, the problem asks to choose as many as edges to form a subgraph

G

′. So that in

G

′, for each edge, at least one of its endpoints has degree no more than

c

. We call such

G

′ partial

c

degree bounded. This edge packing problem model also has a direct interpretation in resource allocation. There are

n

types of resources and

m

jobs. Each job needs two types of resources. A job can be accomplished if either one of its necessary resources is shared by no more than

c

other jobs. The problem then asks to finish as many jobs as possible. For edge packing problem, when

c

 = 1, it turns out to be the complement of dominating set and able to be 2-approximated. When

c

 = 2, it can be 32/11-approximated. We also prove it is

NP

-complete for any constant

c

on graphs and is

O

(|

V

|

2

) solvable on trees. We believe this partial bounded graph problem is intrinsic and merits more attention.

The paper “The Approximability of the Exemplar Breakpoint Distance Problem” [1],, which appeared in AAIM 2006, contained several negative results and one positive result — a claimed

O

(log

n

)-factor greedy approximation for the One-sided Exemplar Breakpoint Distance Problem. Here, we show that the analysis was incorrect and the approximation factor of the greedy algorithm could be Θ(

n

), where

n

is the size of the alphabet.