Algorithmic Aspects in Information and Management

We introduce a new technique on partition, called double partition. With this new type of partition, we obtain a polynomial time (6 + 

ε

)-approximation (

ε

> 0) for the minimum weight dominating set problem in unit disk graphs, which improves a recent result of a 72-approximation given by Ambühl et al. for solving a long-standing open problem. As a corollary, we obtain a (9.875 + 

ε

)-approximation for the minimum weight connected dominating set problem in unit disk graphs.

In his seminal 1950 paper, John Nash defined the bargaining problem; the ensuing theory of bargaining lies today at the heart of game theory. In this work, we initiate an algorithmic study of Nash bargaining problems.

We consider a class of Nash bargaining problems whose solution can be stated as a convex program. For these problems, we show that there corresponds a market whose equilibrium allocations yield the solution to the convex program and hence the bargaining problem. For several of these markets, we give combinatorial, polynomial time algorithms, using the primal-dual paradigm.

Unlike the traditional Fisher market model, in which buyers spend a fixed amount of money, in these markets, each buyer declares a lower bound on the amount of utility she wishes to derive. The amount of money she actually spends is a specific function of this bound and the announced prices of goods.

Over the years, a fascinating theory has started forming around a convex program given by Eisenberg and Gale in 1959. Besides market equilibria, this theory touches on such disparate topics as TCP congestion control and efficient solvability of nonlinear programs by combinatorial means. Our work shows that the Nash bargaining problem fits harmoniously in this collage of ideas.

We consider a natural generalization of the classical

minimum hitting set

problem, the

minimum hitting set of bundles

problem (

mhsb

) which is defined as follows. We are given a set

$\mathcal{E}=\{e_1, e_2 , \ldots , e_n\}$

of

n

elements. Each element

e

i

(

i

 = 1, ...,

n

) has a non negative cost

c

i

. A

bundle

b

is a subset of

$\mathcal{E}$

. We are also given a collection

$\mathcal{S}=\{S_1, S_2 , \ldots , S_m\}$

of

m

sets of bundles. More precisely, each set

S

j

(

j

 = 1, ...,

m

) is composed of

g

(

j

) distinct bundles

$b_j^1, b_j^2, \ldots , b_j^{g(j)}$

. A solution to

mhsb

is a subset

$\mathcal{E}' \subseteq \mathcal{E}$

such that for every

$S_j \in \mathcal{S}$

at least one bundle is covered, i.e.

$b_j^l \subseteq \mathcal{E}'$

for some

l

 ∈ {1,2, ⋯ ,

g

(

j

)}. The

total cost

of the solution, denoted by

$C(\mathcal{E'})$

, is

$\sum_{\{i \mid e_i \in \mathcal{E'}\}} c_i$

. The goal is to find a solution with

minimum

total cost.

We give a deterministic

$N(1-(1-\frac{1}{N})^M)$

-approximation algorithm, where

N

is the maximum number of bundles per set and

M

is the maximum number of sets an element can appear in. This is roughly speaking the best approximation ratio that we can obtain since, by reducing

mhsb

to the vertex cover problem, it implies that

mhsb

cannot be approximated within 1.36 when

N

 = 2 and

N

 − 1 − 

ε

when

N

 ≥ 3. It has to be noticed that the application of our algorithm in the case of the

min

k

 −

sat

problem matches the best known approximation ratio.

We consider the speed scaling problem of scheduling a collection of tasks with release times, deadlines, and sizes so as to minimize the energy recharge rate. This is the first theoretical investigation of speed scaling for devices with a regenerative energy source. We show that the problem can be expressed as a polynomial sized convex program. We that using the KKT conditions, one can obtain an efficient algorithm to verify the optimality of a schedule. We show that the energy optimal YDS schedule, is 2-approximate with respect to the recharge rate. We show that the online algorithm BKP is

O

(1)-competitive with respect to recharge rate.

We consider a generalization of the shortest-path problem: given an alphabet

Σ

, a graph

G

whose edges are weighted and

Σ

-labeled, and a regular language

L

 ⊆ 

Σ

*

, the

L-constrained shortest-path problem

consists of finding a shortest path

p

in

G

such that the concatenated labels along

p

form a word of

L

. This definition allows to model, e. g., many traffic-planning problems. We present extensions of well-known speed-up techniques for the standard shortest-path problem, and conduct an extensive experimental study of their performance with various networks and language constraints. Our results show that depending on the network type, both goal-directed and bidirectional search speed up the search considerably, while combinations of these do not.

We consider continuous tree edge-partition problem on a edge-weighted tree network. A continuous

p

-edge-partition of a tree is to divide it into

p

subtrees by selecting

p

 − 1 cut points along the edges of the underlying tree. The objective is to maximize (minimize) the minimum (maximum) length of the subtrees. We present an

O

(

n

log

2

n

)-time algorithm for the max-min problem which is based on parametric search technique [7] and an efficient solution to the ratio search problem. Similar algorithmic technique, when applied to the min-max problem, results in an

O

(

nh

T

log

n

)-time algorithm where

h

T

is the height of the underlying tree network. The previous results for both max-min and min-max problems are

O

(

n

2

) [5].

We consider the problem of determining suitable meeting times and locations for a group of participants wishing to schedule a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant must be able to reach the new meeting location, attend for the entire duration, and reach the next meeting location on time. In particular, we give a solution to the problem instance where each participant has two scheduled meetings separated by a free time interval. In [2], we presented an

O

(

n

log

n

) algorithm for

n

participants obtained by purely geometrical arguments. Our new approach uses the concept of LP-type problems and leads to a randomized algorithm with expected running time

O

(

n

).

The

Kemeny Score

problem is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permutation” that is “closest” to the given set of permutations. Computing an optimal consensus permutation is NP-hard. We provide first, encouraging fixed-parameter tractability results for computing optimal scores (that is, the overall distance of an optimal consensus permutation). Our fixed-parameter algorithms employ the parameters “score of the consensus”, “maximum distance between two input permutations”, and “number of candidates”. We extend our results to votes with ties and incomplete votes, thus, in both cases having no longer permutations as input.

We address the problem of data gathering in a wireless network using multihop communication; our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performance of distributed algorithms, which do not use any form of local coordination, and we focus on the objective of minimizing average flow times of data packets. We prove a lower bound of

Ω

(log

m

) on the competitive ratio of any distributed algorithm minimizing the maximum flow time, where

m

is the number of packets. Next, we consider a distributed algorithm which sends packets over shortest paths, and we use resource augmentation to analyze its performance when the objective is to minimize the average flow time. If interferences are modeled as in Bar-Yehuda et al. (J. of Computer and Systems Science, 1992) we prove that the algorithm is (1 + 

ε

)-competitive, when the algorithm sends packets a factor

O

(log(

δ

/

ε

) log

Δ

) faster than the optimal offline solution; here

δ

is the diameter of the network and

Δ

the maximum degree. We finally extend this result to a more complex interference model.

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of

$\frac{24}{29}=0.827586\ldots$

. This improves on the previous best ratio of

$\frac{468}{575}=0.813913\ldots$

.

This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm and claimed that it achieves an expected ratio of

$\frac{89}{169}(1 - \epsilon)$

for any constant

ε

> 0. However, their analysis was flawed. We present a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio very close to their claimed expected ratio.

In this paper, we present approximation algorithms for the

line facility location problem in weighted regions

: Given

l

fixed points in a 2-dimensional weighted subdivision of the plane, with

n

vertices, find a line

L

such that the sum of the weighted distances from the fixed points to

L

is minimized. The weighted region setup is a more realistic model for many facility location problems that arise in practical applications. Our algorithms exploit an interesting property of the problem, that could possibly be used for solving other problems in weighted regions.

We study scheduling problems motivated by recently developed techniques for microprocessor thermal management at the operating systems level. The general scenario can be described as follows. The microprocessor temperature is controlled by the hardware thermal management system that continuously senses the chip temperature and automatically reduces the processor’s speed as soon as the thermal threshold is exceeded. Some tasks are more CPU-intensive than other and thus generate more heat during execution. The cooling system operates non-stop, reducing (at an exponential rate) the deviation of the processor’s temperature from the ambient temperature. As a result, the processor’s temperature, and thus the performance as well, depends on the order of the task execution. Given a variety of possible underlying architectures, models for cooling and for hardware thermal management, as well as types of tasks, this gives rise to a plethora of interesting and never studied scheduling problems.

We focus on scheduling real-time jobs in a simplified model for cooling and thermal management. A collection of unit-length jobs is given, each job specified by its release time, deadline and heat contribution. If, at some time step, the temperature of the system is

t

and the processor executes a job with heat contribution

h

, then the temperature at the next step is (

t

 + 

h

)/2. The temperature cannot exceed the given thermal threshold

τ

. The objective is to maximize the throughput, that is, the number of tasks that meet their deadlines. We prove that in the offline case computing the optimum schedule is NP-hard, even if all jobs are released at the same time. In the online case, we show a 2-competitive deterministic algorithm and a matching lower bound.

A promising approach to compare two graph clusterings is based on using measurements for calculating the distance between them. Existing measures either use the structure of clusterings or quality-based aspects with respect to some index evaluating both clusterings. Each approach suffers from conceptional drawbacks. We introduce a new approach combining both aspects and leading to better results for comparing graph clusterings. An experimental evaluation of existing and new measures shows that the significant drawbacks of existing techniques are not only theoretical in nature but manifest frequently on different types of graphs. The evaluation also proves that the results of our new measures are highly coherent with intuition, while avoiding the former weaknesses.

Edge searching is a graph problem that corresponds to cleaning a contaminated graph using the minimum number of searchers. We define

fast searching

as a variant of this widely studied problem. Fast searching corresponds to an internal monotone search in which every edge is traversed exactly once and searchers are not allowed to jump. We present a linear time algorithm to compute the fast search number of trees. We investigate the fast search number of bipartite graphs. We also propose a general cost function for evaluating search strategies that utilizes both edge searching and fast searching.

We give a randomized protocol for the classic cake cutting problem that guarantees approximate proportional fairness, and with high probability uses a linear number of cuts.

Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Faliszewski et al. [9] proved that Llull voting (which is here denoted by Copeland

1

) and a variant (here denoted by Copeland

0

) of Copeland voting are computationally resistant to many, yet not all, types of constructive control and that they also provide broad resistance to bribery. We study a parameterized version of Copeland voting, denoted by Copeland

α

, where the parameter

α

is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates in Copeland elections. For each rational

α

, 0 < 

α

< 1, and each previously studied control scenario, we either prove that Copeland

α

is computationally vulnerable to control in that scenario (i.e., we give a P-time algorithm that determines whether control is possible, and if so, determines exactly how to exert the control) or we prove that Copeland

α

is computationally resistant to control in that scenario (i.e., we prove that control problem to be NP-hard). In particular, we prove that Copeland

0.5

, the system commonly referred to as “Copeland voting,” provides full resistance to constructive control. Among systems with a polynomial-time winner problem, this is the first natural election system proven to have full resistance to constructive control. Looking at rational

α

, 0 < 

α

< 1, we give a broad set of results on bribery and on the fixed-parameter tractability of bounded-case control for Copeland

α

(previously only Copeland

0

and Copeland

1

had been studied), and we introduce and obtain fixed-parameter tractability results even in a new, more flexible model of control (that we dub “extended control”).

We study the complexity of the following problem: Given two weighted voting games

G

′ and

G

′′ that each contain a player

p

, in which of these games is

p

’s power index value higher? We study this problem with respect to both the Shapley-Shubik power index [16] and the Banzhaf power index [3,6]. Our main result is that for both of these power indices the problem is complete for probabilistic polynomial time (i.e., is PP-complete). We apply our results to partially resolve some recently proposed problems regarding the complexity of weighted voting games. We also show that, unlike the Banzhaf power index, the Shapley-Shubik power index is not #P-parsimonious-complete. This finding sets a hard limit on the possible strengthenings of a result of Deng and Papadimitriou [5], who showed that the Shapley-Shubik power index is #P-metric-complete.

Facility Location can be seen as a whole family of problems which have many obvious applications in economics. They have been widely explored in the Operations Research community, from the viewpoints of approximation, heuristics, linear programming, etc. We add a new facet by initiating the study of some of these problems from a parametric point of view. Moreover, we exhibit some less obvious applications of these algorithms in the processing of semistructured documents and in computational biology.

We consider shortest path queries in a polygonal domain

P

having

n

vertices and

h

holes. A skeleton graph is a subgraph of a Voronoi diagram of

P

. Our novel algorithm utilizes a reduced skeleton graph of

P

to compute a tessellation of

P

. It builds a data structure of size

O

(

n

2

) in

O

(

n

2

log

n

) time to support distance queries for any pair of query points in

P

in

O

(

h

log

n

) time.

Given a set

T

of

n

points in ℝ

2

, a Manhattan Network

G

is a network with all its edges horizontal or vertical segments, such that for all

p

,

q

 ∈ 

T

, in

G

there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between

p

and

q

. The Minimum Manhattan Network (MMN) problem is to find a Manhattan network of the minimum length,

i.e.

, the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity

O

(

n

2

), which improves the 2-approximation algorithm with time complexity

Ω

(

n

8

), proposed by Chepoi, Nouioua

et al.

. To the best of our knowledge, this is the best result on this problem.

For digraphs

D

and

H

, a mapping

f

:

V

(

D

) →

V

(

H

) is a homomorphism of

D

to

H

if

uv

 ∈ 

A

(

D

) implies

f

(

u

)

f

(

v

) ∈ 

A

(

H

). If, moreover, each vertex

u

 ∈ 

V

(

D

) is associated with costs

c

i

(

u

),

i

 ∈ 

V

(

H

), then the cost of the homomorphism

f

is ∑ 

u

 ∈ 

V

(

D

)

c

f

(

u

)

(

u

). For each fixed digraph

H

, we have the

minimum cost homomorphism problem for

H

(abbreviated MinHOM(

H

)). In this discrete optimization problem, we are to decide, for an input graph

D

with costs

c

i

(

u

),

u

 ∈ 

V

(

D

),

i

 ∈ 

V

(

H

), whether there exists a homomorphism of

D

to

H

and, if one exists, to find one of minimum cost. We obtain a dichotomy classification for the time complexity of MinHOM(

H

) when

H

is an oriented cycle. We conjecture a dichotomy classification for all digraphs with possible loops.

Given a digraph

D

, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in

D

an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parametrization is as follows: given a digraph

D

of order

n

and a positive integral parameter

k

, check whether

D

contains an out-branching with at most

n

 − 

k

leaves (and find such an out-branching if it exists). We find a problem kernel of order

O

(

k

·2

k

) and construct an algorithm of running time

O

(2

O

(

k

log

k

)

 + 

n

3

), which is an ‘additive’ FPT algorithm.

The quest for optimal/stable paths in graphs concerns a few practical or theoretical areas. Taking part in the quest, this paper adopts an abstract, general, equilibrium-oriented approach: it uses (quasi-arbitrary) arc-labelled digraphs, and assumes little about the structure of the sought paths and the definition of equilibrium,

i.e.

optimality/stability. The paper gives both a sufficient condition and a necessary condition for equilibrium existence for every “graph”, pinpoints the difference between these conditions, and shows coincidence when optimality relates to a total order. These results are applied to network routing.

Motivated by a question raised by Pór and Wood in connection with compact embeddings of graphs in

${\mathbb Z}^d$

, we investigate generalizations of the no-three-in-line-problem. For several pairs (

k

,

l

) we give algorithmic lower, and upper bounds on the largest sizes of subsets

S

of grid-points from the

d

-dimensional

T

× ⋯ ×

T

-grid, where no

l

distinct grid-points of

S

are contained in a

k

-dimensional affine or linear subspace.

Consider a digraph where the vertices represent people and an arc (

i

,

j

) represents the possibility of

i

giving a gift to

j

. The basic question we pose is whether there is an anonymity-preserving “gift assignment” such that each person makes and receives exactly one gift, and such that no person

i

can infer the remaining gift assignments from the fact that

i

is assigned to give a gift to

j

. We formalize this problem as a graph property involving vertex disjoint circuit covers, give a polynomial algorithm to decide this property for any given graph and provide a computational validation of the algorithm.

We study the combinatorial properties of optimal refueling policies, which specify the transportation paths and the refueling operations along the paths to minimize the total transportation costs between vertices. The insight into the structure of optimal refueling policies leads to an elegant reduction of the problem of finding optimal refueling policies into the classical shortest path problem, which ends in simple and more efficient algorithms for finding optimal refueling policies.

Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose a natural and simple random model for generating scale free interval graphs. The model generates a set of intervals randomly, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of the generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from the most of the other models for which we need to approximate the processes by certain differential equations. We indeed show that the distribution of degrees follows power law, and it achieves large cluster coefficient.

In this paper, we introduce Vertex-face contact representation (VFCR for short) for 2-connected plane multigraphs. We present a simple linear time algorithm for constructing a VFCR for 2-connected plane graphs. Our algorithm only uses an

st

-orientation for

G

and its corresponding

st

-orientation for the dual graph of

G

. We also show that one kind of vertex-vertex contact representation (VVCR) for 2-connected bipartite planar graphs introduced by Fraysseix et al. [2,3] can be easily obtained by applying our algorithm. In general, our algorithm produces a more compact representation than their algorithm.

Then we investigate

st

-orientations for 3-connected planar graphs. We prove that a 3-connected planar graph

G

with

n

vertices and

f

faces, has an

st

-orientation with the length of its longest directed path

$\leq \frac{2n}{3}+2\lceil\sqrt{n/3}\rceil+5$

. This implies that such a graph

G

admits a VFCR in a grid with non-trivial size bound. This non-trivial size bound also applies to the vertex-vertex contact representation [2,3] for a large class of 2-connected bipartite planar graphs.

One of the basic and fundamental problems in scheduling is to minimize the machine completion time vector in the ℓ

p

norm (a direct extension of the

l

 ∞ 

norm: the makespan) on uniform parallel machines. We concentrate on the on-line and preemptive version of this problem where jobs arrive one by one over a list and are allowed to be preempted. We present a best possible deterministic on-line scheduling algorithm along with a matching lower bound when there are two machines, generalizing existing results for the identical machines scheduling problem in the literature. The main difficulty in the design of the algorithm and the analysis of the resultant competitive ratio as well as the proof of the lower bound is that the competitive ratio is only known to be the root of some equation systems, which admits no analytic solution—a distinct feature from most existing literature on competitive analysis. As a consequence, we develop some new ideas to tackle this difficulty. Specifically we need to exploit the properties of the equations system that defines the competitive ratio.

This paper will study an online non-uniform length order scheduling problem. For the case where online strategies have the knowledge of

Δ

beforehand, which is the ratio between the longest and shortest length of order, Ting [3] proved an upper bound of

$(\frac{6\Delta}{\log\Delta}+O(\Delta^{5/6}))$

and Zheng et al. [2] proved a matching lower bound. This work will consider the scenario where online strategies do not have the knowledge of

Δ

at the beginning. Our main work is a

$(\frac{6\Delta}{\log\Delta}+O(\Delta^{5/6}))$

-competitive optimal strategy, extending the result of Ting [3] to a more general scenery.

Many recommendation systems suggest items to users by utilizing the techniques of

collaborative filtering

(CF) based on historical records of items that the users have viewed, purchased, or rated. Two major problems that most CF approaches have to contend with are scalability and sparseness of the user profiles. To tackle these issues, in this paper, we describe a CF algorithm

alternating-least-squares with weighted-λ

-regularization

(ALS-WR), which is implemented on a parallel Matlab platform. We show empirically that the performance of ALS-WR (in terms of

root mean squared error

(RMSE)) monotonically improves with both the number of features and the number of ALS iterations. We applied the ALS-WR algorithm on a large-scale CF problem, the Netflix Challenge, with 1000 hidden features and obtained a RMSE score of 0.8985, which is one of the best results based on a pure method. In addition, combining with the parallel version of other known methods, we achieved a performance improvement of 5.91% over Netflix’s own CineMatch recommendation system. Our method is simple and scales well to very large datasets.