第20回 KIDS

日時　　２００４年１１月３０日（火）　13:30--16:50

場所　　京都大学 ベンチャービジネスラボラトリー　２階セミナー室

プログラム　

13:30--14:30	今村友和（岩間研）	Approximating Vertex Cover on Dense Graphs
14:40--15:40	永持　仁（情報学研究科）	弾性矩形詰め込みに対する一考察
15:50--16:50	藤戸敏弘（豊橋技術科学大学）	Submodular Integer Cover and its Application to Production Planning

---

概要

今村友和（岩間研）

題目

Approximating Vertex Cover on Dense Graphs


概要

Although many problems in MAX-SNP admit a PTAS for dense graphs,

that is not the case for Vertex Cover,

which is MAX-SNP hard even for dense graphs.

This paper presents a randomized approximation algorithm for Vertex Cover

on dense graphs,

i.e., graphs whose average degree $\avd$ is $\Omega(n)$.

(i)~Our algorithm improves the best-known bound for the approximation factor

by Karpinski and Zelikovsky.

For example, our bound is $\frac{2}{1+\frac{\avd}{2\Delta}}$ for dense graphs such that $|E|\le \Delta(n-\Delta)$

where $\Delta$ is the maximum degree.

The improvement is especially large when $\avd\approx \Delta$;

if $\avd \ge \frac{2}{3}\Delta$ for instance, our bound is at most 1.5

while the previous bound approaches to 2.0 as $\frac{n}{\Delta}$ increases.

(ii)~It achieves the same factor for a wider range of graphs, i.e.,

for the graphs whose $\Delta$ is $\Omega(n\frac{\log\log n}{\log n})$.

(iii)~It is probably optimal in the sense that

if we can achieve a better approximation factor by $\delta > 0$

for the above range of graphs, then we can achieve a factor of $2-\delta$ for general graphs.

永持　仁（情報学研究科）

題目

弾性矩形詰め込みに対する一考察

藤戸敏弘（豊橋技術科学大学）

題目

Submodular Integer Cover and its Application to Production Planning

概要

Suppose there are a set of suppliers $i$ and a set of consumers $j$ with

demands $b_j$,

and the amount of products that can be shipped from $i\mbox{ to

}j$ is at most $c_{ij}$.

The amount of products that a supplier $i$ can produce is an integer

multiple of its capacity $\kappa_i$, and every production of $\kappa_i$

products incurs the cost of $w_i$.

The {\em capacitated supply-demand (CSD)\/} problem

is to minimize the production cost of $\sum_{i}w_i x_i$ such

that all the demands (or the total demand requirement specified

separately) at consumers are satisfied by shipping products from

the suppliers to them.

To capture the core structural properties of CSD in a general framework,

we introduce the {\em submodular integer cover (SIC)\/} problem, which

extends the {\em submodular set cover (SSC)\/} problem by generalizing

submodular constraints on subsets to those on integer vectors.

Whereas it can be shown that CSD

is approximable within a factor of $O(\log (\max_{i}\kappa_i))$

by extending the greedy approach for SSC to CSD,

we first generalize the primal-dual approach for SSC to SIC

and evaluate its performance.

One of the approximation ratios obtained for CSD from such an approach

is the maximum number of suppliers

that can ship to a single consumer; therefore, the approximability

of CSD can be ensured to depend only on the network (incidence)

structure and not on any numerical values of input capacities

$\kappa_i,b_j,c_{ij}$.

The CSD problem also serves as a unifying framework for various types of

covering problems, and

any approximation bound for CSD holds for set cover

generalized {\em simultaneously\/} into various directions.

It will be seen, nevertheless, that our bound matches (or

nearly matches) the best result for each generalization

{\em individually}.

Meanwhile, this bound being nearly tight for standard set cover, any

further improvement, even if possible, is doomed to be a

marginal one.