Tags: alg, optimization, LP

This is my note on low-dimension linear programming & color refinement algorithms.

1 the problem & failed attempts

In September I’m working on the following small problem,

Problem1Minimizing the Sum of Piecewise Linear Convex Functions

Given \(n\) piecewise linear convex functions \(f_1,...,f_n:\R \to \R\) of total \(m\) breakpoints, and \(n\) linear functions \(a_i\cdot x-b_i:\R^d\to \R\), find \(\min_x \sum_i f_i(a_i\cdot x-b_i)\).

which is highly related to algorithms for linear programming in low dimensions.

This can be solve in \(O(2^{2^d}(m+n))\) through Megiddo’s algorithm for multidimensional search problem. (see my slides)

I want to show that for general piecewise linear convex functions in \(\R^d\), my problem can be formulated as a LP-type problem with low combinatorial dimension.

A failed attempt is trying to write \(F=\sum_i f_i\). However, there may be too many breakpoints on \(F\). (see a previous post). Another possible way is using some dimension reduction techniques [1].

I do not have high expectation on this method, since I need to show that color refinement indeed reduce the dimension from \(n+d\) to \(d\) and that the reduction can be done in linear time.

Given a initial coloring of vertices in a directed graph \(G=(V,A)\), we want to compute the coarsest regular congruent coloring.

Colorings can be considered as equivalence relations on the vertices. An equivalence relation \(R\) on \(V\) is congruent if for all \(u,v,w\in V\), [\((u,v)\in R\) and \((v,w)\in A\)] implies that [\(\exists v'\in V\) such that \((v,v')\in A\) and \((v',w)\in R\)]. Note that this coincides with the general definition of congruence relation in algebraic structures.(We can copy each vertex #outdegree times to make \(A\) an unary operation.)

A coloring is regular if for any two vertices \(u,v\), the number of successors in each color are the same. Consider two colorings \(C_1,C_2\). \(C_1\) is a refinement of \(C_2\)(or \(C_2\) is coarser than \(C_1\)) if for any two vertices having the same color in \(C_1\), they have the same color in \(C_2\).

Basic Lemma 1 in [2] shows that the problem above is equivalent to the description in this wiki page.

The first quasilinear time algorithm for the color refinement problem on graphs is given in [2], and later in [3]. It is shown in [4] that \(O((m+n)\log n)\) is the best possible running time. It is also shown in [5] that for any number of vertices there exists a graph which requires at least \(n-2\) iterations to reach a stable coloring(note that the upperbound is \(n-1\)). See this for a nice survey on applications.

2.1 connections

Now we add edge weights on the directed graph. Suppose all arcs have weight 1. One can see that a congruent and regular coloring requires that two vertices have the same color iff for each color the total weight of arcs going to vertices in that color are the same. Slightly generalize this configuraton, we can consider arbitrary arc weights.

Now color refinement on matrices are almost the same as doing color refinement on the incidence matrix of a weighted digraph. However, not every matrix is square. For any matrix \(A\in \R^{v\times w}\), we consider it as a bitartite graph \(G=(V\sqcup W,A)\), where \(|V|=v\) and \(|W|=w\). Then \(A_{ij}=w(i, j)\) if \((i, j)\) is an arc in \(G\) and 0 otherwise.

This part is not intuitive and complicated. I think the ESA 14 paper [1] is very concise (compared to the arxiv version), however still takes four and a half pages to explain this part. So I will just briefly explain the idea.

This connection is based on an important theorem, stating that the color refinement of a matrix \(A\) has strong relation with the fractional automorphism of \(A\). To do the reduction, we first compute a color refinement of \(A\). Based on the partitions of columns and rows of \(A\) in the color refinement(partition matrices), we can conpute the factor matrix of \(A\), denoted by \([A]\), which is small than \(A\). Then finally, the authors proved a reduction lemma, which shows that the optimal solution to factor matrix of the entire LP(I don’t know the exact name, just the matrix one uses in the simplex method) is a linear mapping of the optimal solution of the original LP.

2.2 is it useful?

The reduction looks clever and has a wide application. However, as far as I know, it does nothing on my problem. I don’t think the matrix in my problem is special enough to allow color refinement algorithms run in linear time on it. Also color refinement does not necessarily partition all \(f_i\) columns in one part. ¯\_(⊙︿⊙)_/¯

2.3 reflection

Multidimensional search is harder than LP-type problems, this question is no exception. Now there are three kinds of problems I am interested in.

Minimax parametric optimization
Multidimensional search problems
LP-type problems

What’s the connections among them?…

Definition2Minimax parametric optimization problem

Given a combinatorial maximization problem with a parameter. Find the parameter value minimizing the weight of a solution to the combinatorial maximization problem.

Definition3Multidimensional search problem

Given a set of hyperplanes \(\mathcal H\) in \(\R^d\), and an oracle which answers the relative position of one hyperplane and a unknown fixed point \(x^*\in \R^d\). Compute the relative position of every hyperplane in \(\mathcal H\) and \(x^*\) with as small number of oracle calls as possible.

Definition4LP-type problem

Given a set \(S\) and a function \(f\) from \(S\) to a totally ordered set. \(f\) has to satisfy two properties,

monotonicity: \(\forall A\subseteq B\subseteq S, f(A)\leq f(B)\leq f(S)\),
locality: \(\forall A\subset B\subset S\), consider any element \(x\in S\), if \(f(A)=f(B)=f(A+x)\), then \(f(A)=f(B+x)\).

Now there are some important concrete problem in the intersections.

2.3.1 Euclidean one-centre problem

Problem5Euclidean one-centre problem

Given \(n\) points \(V=\{v_1,\dots, v_n\}\) in \(\R^d\), with weights \(w_1,\dots,w_n\), find a point in \(\R^d\) which has the minimal of the maximum weighted distance to all points in \(V\), that is, compute \(\min_x \max_{i} w_i^2(v_i-x)^2\).

Dyer showed that this problem can be considered as a multidimensional search problem (in \(\R^{d+1}\)) in [6]. The conversion is not easy and not intuitive. Das et al. claimed that this problem is a LP-type problem with some additional constraints in [7]. It is still unknown whether it is possible to formulate the weighted Euclidean one-centre problem in \(\R^d\) as a LP-type problem with combinatorial dimension \(O(d)\) (which is quite surprising…)

2.3.2 Minimizing the sum of some pwl convex functions(my problem)

see above for the definition.

Clearly this is a minimax parametric optimization problem. Zemel also showed this is a multidimensional search problem with dimension \(d\). We want to know that if this is a LP-type problem with combinatorial dimension \(O(d)\)…

It seems that recognizing LP-type is hard. A lecture on LP-type problems by David Eppstein.

Here are some materials for Low dimension LP:

chapter 20 of Geometric Approximation Algorithms by Sariel Har-Peled. https://sarielhp.org/book/chapters/lp.pdf
the fastest deterministic algorithm for this problem [8]
my slides on Seidel’s \(O(d!n)\) algorithm

References

[1]

M. Grohe, K. Kersting, M. Mladenov, E. Selman, Dimension Reduction via Colour Refinement, in: Algorithms - ESA 2014, Springer Berlin Heidelberg, Berlin, Heidelberg, 2014: pp. 505–516.

[2]

A. Cardon, M. Crochemore, Partitioning a graph in O(AlogV), Theoretical Computer Science. 19 (1982) 85–98 10.1016/0304-3975(82)90016-0.

[3]

R. Paige, R.E. Tarjan, Three Partition Refinement Algorithms, SIAM Journal on Computing. 16 (1987) 973–989 10.1137/0216062.

[4]

C. Berkholz, P. Bonsma, M. Grohe, Tight lower and upper bounds for the complexity of canonical colour refinement, Theor. Comp. Sys. 60 (2017) 581–614 10.1007/s00224-016-9686-0.

[5]

S. Kiefer, B.D. McKay, The Iteration Number of Colour Refinement, in: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020: pp. 73:1–73:19 10.4230/LIPIcs.ICALP.2020.73.

[6]

M.E. Dyer, On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem, SIAM Journal on Computing. 15 (1986) 725–738 10.1137/0215052.

[7]

S. Das, A. Nandy, S. Sarvottamananda, Linear time algorithms for Euclidean 1-center in \(\R^d\) with non-linear convex constraints, Discrete Applied Mathematics. 280 (2020) 71–85 10.1016/j.dam.2019.09.009.

[8]

T.M. Chan, Improved deterministic algorithms for linear programming in low dimensions, ACM Trans. Algorithms. 14 (2018) 10.1145/3155312.

Minimizing Sum of PWL Convex Functions